Graphics Reference
In-Depth Information
of
O
(
n
2
) for the algorithm as a whole. This algorithm can be implemented as
follows:
// Compute the center point, 'c', and axis orientation, u[0] and u[1], of
// the minimum area rectangle in the xy plane containing the points pt[].
float MinAreaRect(Point2D pt[], int numPts, Point2D &c, Vector2D u[2])
{
float minArea = FLT_MAX;
// Loop through all edges; j trails i by 1, modulo numPts
for(inti=0,j=numPts - 1; i < numPts;j=i,i++) {
// Get current edge e0 (e0x,e0y), normalized
Vector2D e0 = pt[i] - pt[j];
e0 /= Length(e0);
// Get an axis e1 orthogonal to edge e0
Vector2D e1 = Vector2D(-e0.y, e0.x);
// = Perp2D(e0)
// Loop through all points to get maximum extents
float min0 = 0.0f, min1 = 0.0f, max0 = 0.0f, max1 = 0.0f;
for(intk=0;k<numPts; k++) {
// Project points onto axes e0 and e1 and keep track
// of minimum and maximum values along both axes
Vector2D d = pt[k] - pt[j];
float dot = Dot2D(d, e0);
if (dot < min0) min0 = dot;
if (dot > max0) max0 = dot;
dot = Dot2D(d, e1);
if (dot < min1) min1 = dot;
if (dot > max1) max1 = dot;
}
float area = (max0 - min0) * (max1 - min1);
// If best so far, remember area, center, and axes
if (area < minArea) {
minArea = area;
c = pt[j] + 0.5f * ((min0 + max0) * e0 + (min1 + max1) * e1);
u[0] = e0; u[1] = e1;
}
}
return minArea;
}
