Title: Find a minimal bounding rectangle for a polygon in C#

This program assumes that its Points array contains the points in a convex polygon in counterclockwise order. If you have some other group of points, first find their convex hull and then orient the resulting polygon counterclockwise. See these related articles:

• Determine whether a polygon is oriented clockwise or counterclockwise in C#
• Reverse the orientation of a polygon in C#
• Determine whether a polygon is convex in C#
• Find the convex hull of a set of points in C#

This example demonstrates the "rotating calipers" algorithm for finding a minimal bounding rectangle around the polygon. The algorithm is fairly involved, so I won't show the code here. Instead I'll describe the ideas.

The algorithm is also 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.

Before I describe the algorithm, 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. It's even possible that all four rectangle edges lie along polygon edges.)

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 edges, so the total run time behavior is O(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 an initial 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 current rectangle.

The program examines the polygon's edges that follow the four current control points and determines which one has the smallest angle of rotation from the previous edge. The next candidate 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 that comes before the selected edge to the following control point and repeats the process.

The program continues this series of steps:

• Find the edge following one of the current control points that has the smallest angle of change.
• Build a rectangle using the selected edge.
• Move the control point before the selected edge to the 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. Each iteration takes a constant number of steps, so the total run time is only O(N).

Download the example to experiment with it and to see additional details.