CODEWITHSUNDEEP
calgorithmgeometrymathematical-optimizationbounding-box
user2317873
user2317873

Reputation: 21

Maximum-perimeter bounding rectangle for a set of points

I've been struggling for quite a while with this seemingly simple problem. I am given a set of points (which I have further simplified down to a convex hull) and my task is to find a rectangle (not necessarily axis-aligned) that encompasses all of them, has no extra space around (so that it is tight-fitting around the points) and has the maximum possible perimeter. It was no trouble for me to find the minimal one, but this has proven to be a tougher nut to crack. When searching for the minimal bounding rectangle, I was able to use the assumption that one of the rectangle's sides was always aligned with one of the hull's sides, but here I don't see any such case here. Am I missing something painfully obvious? The only way I could come up so far is to test antipodal pairs of points if they can project onto the sides of the rectangle and use some trig to maximize the function, but I just lost myself in the calculations.

Thanks in advance!

Upvotes: 2

Views: 1125

Answers (1)

tmyklebu
tmyklebu

Reputation: 14205

First, compute the convex hull of your point set.

Now, think about spinning the polygon around and computing the smallest enclosing axis-aligned rectangle. Notice that the top point, the left point, the right point, and the bottom point will proceed clockwise around the convex hull from one vertex to the next.

You can't try every possible angle explicitly. You can, however, do a sweep-line trick. Given an angle, though, you can compute the top, left, bottom, and right points after spinning the polygon by that angle as well as the first of the top, left, bottom, and right points to change identity as you continue rotating the polygon. So you get a range of angles for which your current choices of top, left, bottom, and right are correct; further, you know what the next correct choice of top, left, bottom, and right is.

For each legitimate choice of top, left, bottom, and right, You wind up having to compute the maximum value of a*sin(theta) + b*cos(theta) for fixed a and b over some range of theta. Recall from trig that a*sin(theta) + b*cos(theta) = sqrt(a^2+b^2) cos(theta - arctan(b/a)). You evaluate the function at the boundaries of your interval and where the derivative is zero (at arctan(b/a) plus any integer times pi) and you're golden.

Upvotes: 1

Related Questions