ORIENTEDBOX Minimum-width oriented bounding box of a set of points.
OBOX = orientedBox(PTS)
Computes the oriented bounding box of a set of points. Oriented box is
defined by a center, two dimensions (the length and the width), and the
orientation of the length axis. Orientation is counted in degrees,
counter-clockwise.
Example
% Draw oriented bounding box of an ellipse
elli = [30 40 40 20 30];
pts = ellipseToPolygon(elli, 120);
obox = orientedBox(pts);
figure; hold on;
drawEllipse(elli);
drawOrientedBox(obox, 'm');
See also
drawOrientedBox, orientedBoxToPolygon0001 function obox = orientedBox(points) 0002 %ORIENTEDBOX Minimum-width oriented bounding box of a set of points. 0003 % 0004 % OBOX = orientedBox(PTS) 0005 % Computes the oriented bounding box of a set of points. Oriented box is 0006 % defined by a center, two dimensions (the length and the width), and the 0007 % orientation of the length axis. Orientation is counted in degrees, 0008 % counter-clockwise. 0009 % 0010 % Example 0011 % % Draw oriented bounding box of an ellipse 0012 % elli = [30 40 40 20 30]; 0013 % pts = ellipseToPolygon(elli, 120); 0014 % obox = orientedBox(pts); 0015 % figure; hold on; 0016 % drawEllipse(elli); 0017 % drawOrientedBox(obox, 'm'); 0018 % 0019 % See also 0020 % drawOrientedBox, orientedBoxToPolygon 0021 % 0022 0023 % ------ 0024 % Author: David Legland 0025 % E-mail: david.legland@inrae.fr 0026 % Created: 2012-03-29, using Matlab 7.9.0.529 (R2009b) 0027 % Copyright 2012-2024 INRA - Cepia Software Platform 0028 0029 %% initialisations 0030 0031 % first, compute convex hull of the polygon 0032 inds = convhull(points(:,1), points(:,2)); 0033 hull = points(inds, :); 0034 0035 % if first and last points are the same, remove the last one 0036 if inds(1) == inds(end) 0037 hull = hull(1:end-1, :); 0038 end 0039 0040 % compute convex hull centroid, that corresponds to approximate 0041 % location of rectangle center 0042 center = mean(hull, 1); 0043 hull = bsxfun(@minus, hull, center); 0044 0045 % number of hull vertices 0046 nV = size(hull, 1); 0047 0048 % default values 0049 rotatedAngle = 0; 0050 minWidth = inf; 0051 minAngle = 0; 0052 0053 % avoid degenerated cases 0054 if nV < 3 0055 return; 0056 end 0057 0058 % indices of vertices in extreme y directions 0059 [tmp, indA] = min(hull(:, 2)); %#ok<ASGLU> 0060 [tmp, indB] = max(hull(:, 2)); %#ok<ASGLU> 0061 0062 caliperA = [ 1 0]; % Caliper A points along the positive x-axis 0063 caliperB = [-1 0]; % Caliper B points along the negative x-axis 0064 0065 0066 %% Find the direction with minimum width (rotating caliper algorithm) 0067 0068 while rotatedAngle < pi 0069 % compute the direction vectors corresponding to each edge 0070 indA2 = mod(indA, nV) + 1; 0071 vectorA = hull(indA2, :) - hull(indA, :); 0072 0073 indB2 = mod(indB, nV) + 1; 0074 vectorB = hull(indB2, :) - hull(indB, :); 0075 0076 % Determine the angle between each caliper and the next adjacent edge 0077 % in the polygon 0078 angleA = vectorAngle(caliperA, vectorA); 0079 angleB = vectorAngle(caliperB, vectorB); 0080 0081 % Determine the smallest of these angles 0082 angleIncrement = min(angleA, angleB); 0083 0084 % Rotate the calipers by the smallest angle 0085 caliperA = rotateVector(caliperA, angleIncrement); 0086 caliperB = rotateVector(caliperB, angleIncrement); 0087 0088 rotatedAngle = rotatedAngle + angleIncrement; 0089 0090 % compute current width, and update opposite vertex 0091 if angleA < angleB 0092 line = createLine(hull(indA, :), hull(indA2, :)); 0093 width = distancePointLine(hull(indB, :), line); 0094 indA = mod(indA, nV) + 1; 0095 0096 else 0097 line = createLine(hull(indB, :), hull(indB2, :)); 0098 width = distancePointLine(hull(indA, :), line); 0099 indB = mod(indB, nV) + 1; 0100 0101 end 0102 0103 % update minimum width and corresponding angle if needed 0104 if width < minWidth 0105 minWidth = width; 0106 minAngle = rotatedAngle; 0107 end 0108 end 0109 0110 0111 %% Compute box dimensions 0112 0113 % orientation of the main axis 0114 theta = rad2deg(minAngle); 0115 0116 % pre-compute trigonometric functions 0117 cot = cos(minAngle); 0118 sit = sin(minAngle); 0119 0120 % elongation in direction of rectangle length 0121 x = hull(:,1); 0122 y = hull(:,2); 0123 x2 = x * cot + y * sit; 0124 y2 = - x * sit + y * cot; 0125 0126 % compute extension along main directions 0127 xmin = min(x2); xmax = max(x2); 0128 ymin = min(y2); ymax = max(y2); 0129 0130 % position of the center with respect to the centroid compute before 0131 dl = (xmax + xmin)/2; 0132 dw = (ymax + ymin)/2; 0133 0134 % change coordinate from rectangle to user-space 0135 dx = dl * cot - dw * sit; 0136 dy = dl * sit + dw * cot; 0137 0138 % coordinates of oriented box center 0139 center = center + [dx dy]; 0140 0141 % size of the rectangle 0142 rectLength = xmax - xmin; 0143 rectWidth = ymax - ymin; 0144 0145 % concatenate rectangle data 0146 obox = [center rectLength rectWidth theta]; 0147