Find a minimal bounding rectangle for a polygon in C#

Minimal bounding rectangle

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:

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(N2). 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 program to see see the C# details. For a slightly more detailed description of the algorithm, see The minimum area enclosing rectangle for a convex polygon, which has a pretty good description.

Download Example   Follow me on Twitter   RSS feed

About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

6 Responses to Find a minimal bounding rectangle for a polygon in C#

  1. Pingback: Perform geometric operations on polygons in C# |

  2. Pingback: 最近demo 模块 算法总结 | ov智商捉急

  3. lin says:

    Dear Rod,
    I test this polygon, at the last step of the button “step”, the program make an error.
    Could you help me, please.

    Points = new PointF[]
        new PointF(114.75f*100-11000, 45.25f*100-3800),
        new PointF(115.75f*100-11000, 45.25f*100-3800),
        new PointF(116.25f*100-11000, 44.75f*100-3800),
        new PointF(116.75f*100-11000, 44.25f*100-3800),
        new PointF(117.25f*100-11000, 42.75f*100-3800),
        new PointF(116.25f*100-11000, 39.75f*100-3800),
        new PointF(114.75f*100-11000, 38.75f*100-3800)
    • RodStephens says:

      Sorry but I don’t have time to look into this right now. I think it doesn’t like the fact that the final segment is vertical.

    • Roger Cabo says:

      Hi Rod, thanks for the code.

      It doesn’t matter if segments are parallel in FindIntersection();

      if (Math.Abs(da * dy - db * dx) < 0.001) return false;

      FindIntersection(px0, py0, px0 + dx0, py0 + dy0, px1, py1, px1 + dx1, py1 + dy1, ref pts[0]);
      if (pts[0] == null) return;
      FindIntersection(px1, py1, px1 + dx1, py1 + dy1, px2, py2, px2 + dx2, py2 + dy2, ref pts[1]);
      if (pts[1] == null) return;
      FindIntersection(px2, py2, px2 + dx2, py2 + dy2, px3, py3, px3 + dx3, py3 + dy3, ref pts[2]);
      if (pts[2] == null) return;
      FindIntersection(px3, py3, px3 + dx3, py3 + dy3, px0, py0, px0 + dx0, py0 + dy0, ref pts[3]);
      if (pts[3] == null) return;

      One rectangle is found anyway.

      • RodStephens says:

        I think it doesn’t matter in this example. The FindIntersection method only returns false if the segments do not intersect, but the dx and dy values are chosen so the segments are perpendicular and therefore always intersect.

        Also note that the point pts[0] etc. cannot be null because a PointF is a structure and structures cannot be null. To make this test, you would need to do this:

        if (!FindIntersection(px0, py0, px0 + dx0, py0 + dy0, px1, py1, px1 + dx1, py1 + dy1, ref pts[0])) return;

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.