|
This program assumes that its m_Points array contains the points in a convex polygon in counter-clockwise order. See these related articles:
This example demonstrates the Rotating Calipers method for finding a minimal bounding rectangle around the polygon. The algorithm is a bit tricky to visualize so you may want to run the program a few times while you read the following description. Each time you click the Step button, the program performs one iteration of the algorithm and examines one candidate bounding rectangle.
First note that any minimal bounding rectangle has at least one edge that coincides with one of the polygon's edges. The three other sides of the rectangle pass through at least one point on the polygon. (If another rectangle edge also coincides with a polygon edge, then that side will pass through more than one polygon point.)
To find all of the candidate bounding rectangles, you can build bounding rectangles for each of the polygon's edges. Unfortunately the most straightforward way to find these bounding rectangles is relatively slow. For each edge, you would examine each of the polygon's points to see which three can form edges that bound the polygon. Finding those points is an O(N) operation and you perform it for each of the polygon's N points so the total run time behavior is O(N*N). Furthermore the calculations are non-trivial.
The rotating caliper algorithm uses a trick to make finding the candidate bounding rectangles easier. It starts by building a bounding rectangle with edges parallel to the X and Y axes. This takes O(N) time: the program simply finds the points with the largest and smallest X and Y coordinates.
Next the program begins "rotating" the sides of this rectangle around the polygon. The next edge that it considers is adjacent to one of the four control points that determine the sides of the rectangle.
The program examines the polygon's edges that follow the four control points and determines which one has the smallest angle of rotation from the previous edge. The next candidate bounding rectangle uses this edge to determine one of its sides. Its other three sides pass through the three other control points.
The program uses the selected edge to calculate the slopes of the rectangle's sides, finds the rectangle's corners, and calculates the rectangle's area.
It then moves the control point before the selected edge to the following control point and repeats the process.
The program continues this series of steps: find the edge following a control point with smallest angle of change, build rectangle, move selected control point to next point. If the polygon has N points, it also has N edges so repeating this process N times makes the program consider every possible bounding rectangle.
Download the example and see the code for the Visual Basic details.
References
| 
