CODEWITHSUNDEEP
algorithm
Mark
Mark

Reputation: 31

Minimum bounding rectangle of polygon

Let's say we have a class/struct Point

class Point
{
 int x;
int y;
}

and a class Polygon that contains list of Points

class Polygon
{
  List<Point> points;

  Path(List<Point> points)
  {
  //some implementation
  }
}

I am interested in finding the Minimal bounding rectangle points of the Polygon(https://en.wikipedia.org/wiki/Minimum_bounding_rectangle). The found minimal bounding rectangle sides might not be parallel to both axis , so I am trying to find an algorithm written in Java,C#,C++ .Can anyone propose or link such a solution, thanks!

Upvotes: 1

Views: 3946

Answers (2)

trincot
trincot

Reputation: 350272

You can do this as follows:

  1. Find the convex hull of the polygon points. A popular method is the Graham scan.

  2. For each edge of the convex hull, find the minimum bounding rectangle that must have one side overlapping with that edge, so that the convex hull's edge is a subsegment of that rectangle's side.

    • Find the two perpendicular sides of the rectangle by walking along the convex hull vertices, and projecting the vertex to the first side, retaining the two that have all other projections between them. The final opposite side can be found in a similar manner. The vertices that lie on the rectangle, should be the starting point for when this step is executed again for the next edge on the convex hull (step 2).

  3. Calculate the size of these rectangles, and retain the minimal one.

The complexity of this algorithm is determined by the first step, which is O(nlogn). The second step is O(n), as you have a selection of one edge and 3 vertices that rotates around the convex hull, visiting each edge once, and each vertex 3 times.

Upvotes: 0

MBo
MBo

Reputation: 80187

It is possible to construct minimal bounding box (both min-area and min-perimeter) using Rotating Calipers approach.

enter image description here

You can find description at this wayback archive page

The minimum area rectangle enclosing a convex polygon P has a side collinear with an edge of the polygon.

The above result dramatically restricts the range of possible rectangles. Not only is it not necessary to check all directions, but only as many as the polygon's number of edges.

Illustrating the above result: the four lines of support (red), with one coinciding with an edge, determine the enclosing rectangle (blue).

A simple algorithm would be to compute for each edge the corresponding rectangle collinear with it. But the construction of this rectangle would imply computing the polygon's extreme points for each edge, a process that takes O(n) time (for n edges). The entire algorithm would then have quadratic time complexity.

A much more efficient algorithm can be found. Instead of recomputing the extreme points, it is possible to update them in constant time, using the Rotating Calipers. Indeed, consider a convex polygon, with a two pair of lines of support through all four usual extreme points in the x and y directions. The four lines already determine an enclosing rectangle for the polygon. But unless the polygon has a horizontal or vertical edge, this rectangle is not a candidate for the minimum area. However, the lines can be rotated until the above condition is satisfied. This procedure is at the heart of the following algorithm. The input is assumed to be a convex polygon with n vertices given in clockwise order.

Compute all four extreme points for the polygon, and call them xminP, xmaxP, yminP ymaxP.

Construct four lines of support for P through all four points. These determine two sets of "calipers".

If one (or more) lines coincide with an edge, then compute the area of the rectangle determined by the four lines, and keep as minimum. Otherwise, consider the current minimum area to be infinite.

Rotate the lines clockwise until one of them coincides with an edge of its polygon.

Compute the area of the new rectangle, and compare it to the current minimum area. Update the minimum if necessary, keeping track of the rectangle determining the minimum.

Repeat steps 4 and 5, until the lines have been rotated an angle greater than 90 degrees. Output the minimum area enclosing rectangle. Because two pairs of "calipers" determine an enclosing rectangle, this algorithm considers all possible rectangles that could have the minimum area. Furthermore, aside from the initialization, there are only as many steps in the algorithm's main loop as there are vertices. Thus the algorithm has linear time complexity.

Upvotes: 2

Related Questions