CODEWITHSUNDEEP
algorithmcomputational-geometry
firev2
firev2

Reputation: 145

Finding a minimum area rectangle of a convex polygon

I am looking for a efficient way to find a minimum area rectangle of a convex polygon.

running time should be O(n) where n is the number of vertices.

there is a complex algorithm for finind a bounding box of a general polygon, but there should be a easier algorithm for a convex polygon.

How can one do it easily for a convex polygon?

thanks.

Upvotes: 0

Views: 1534

Answers (1)

user1196549
user1196549

Reputation:

Rotating calipers are your best friends.

The tightest bounding rectangle is such that one of its sides coincides with a side of the polygon. So,

  • starting from an arbitrary side, rotate the polygon to make this side horizontal, at the bottom;

  • find the three vertices that maximize Y, -X and X respectively (on the figure, 4, 6, and 3). This way, you obtain a bounding box;

  • then move to the next side, clockwise, and adjust the rotation;

  • find the next three vertices by updating the maxima (follow the outline and stop before Y decreases; same with -X and X; on the figure, 4->5, 6->6 and 3->3);

  • for every position, compute the area and keep the best. Stop after a full turn.

enter image description here

It is important to realize that you don't apply the rotations to all vertices, but only when needed. To obtain the initial bounding box, you process O(N) vertices, but the N-1 updates only take O(N) additional work (amortized), and you don't have to compute both coordinates.

Upvotes: 5

Related Questions