How to find minimum possible projection of a polygon on X axis, after rotating at an arbitrary angle?

5
votes

Given the vertices of a 2D polygon, I have to find the minimum possible projection of the polygon on X axis.

I am allowed to rotate the polygon at arbitrary angle.

At first I thought for the minimum case, at least one of the polygon's sides will be aligned to the X axis, which is not true.

The polygon can be concave or convex.

3
c++algorithmrotationgeometrycomputational-geometry
Please be clearer. "The minimum projection of a polygon" doesn't mean anything. – Kerrek SB
Intuition tells me that at least one pair of vertices will be aligned to the X axis Could be wrong of course. – john
Why the downvote? Seems the question is pretty clear to quite a number of people. – cdoubleplusgood
I suspect that OP's minimum possible projection is the same as the minimum width of the polygon. If the polygon is convex then I suspect rotating calipers would help. If the polygon is non-convex then I suspect that its convex hull has the same minimum possible projection. – High Performance Mark
Not an answer, but a simplification: You need to look at convex polygons only. Because any vertex that has an inner angle > 180° between the previous and next vertex (that means, an "indentation") can never be one of the outer vertices in any projection. You can skip them and construct a convex polygon from the remaining "outer" vertices. – cdoubleplusgood

3 Answers

2
votes

As noted in comments, the answer will not chnage if you replace the polygon with its convex hull. So let' s think polygon is already convex. Now assume we found the minimal angle. It means we have a strip parallel to Y bounding the body. Easy to see that one of polygon sides can lie on the strip boundary (if it is not, we can rotate the body slightly without increasing the strip width).

Summarizing, we get an algorithm: compute the convex hull, then for each side of the hull select an angle which makes it parallel to Y and test the width. Take the min. 0

6
votes

What you are looking for is called the "Rotating Calipers Algorithm".

https://en.wikipedia.org/wiki/Rotating_calipers

The Wikipedia page about this algorithm has even pseudo-code for your problem.

https://en.wikipedia.org/wiki/Rotating_calipers#Minimum_width_of_a_convex_polygon

0
votes

Let X(i, alpha) be the X-coodrinate of vertex i after rotation by angle alpha.

We always assume -PI <= alpha <= PI .

Let i=rightmost(alpha) if X(i, alpha)>=X(j, alpha) for all j. Let i=second_rightmost(alpha) if X(i, alpha)>=X(j,alpha) for all j except one. Similarly define leftmost() and second_leftmost().

Let us prove the following: if X(i, alpha) >= X(j, alpha), and X(i, beta) >= X(j, beta), and beta-alpha < PI, then X(i, gamma) >= X(j, gamma) for all gamma in [alpha, beta]. Indeed, X(i, alpha)=x[i]*cos(alpha)-y[i] * sin(alpha), where (x[i], y[i]) are initial position of the vertex i. Therefore, X(i, a) - X(j, a) = c1*cos(a)-c2*sin(a), where c1=x[i]-x[j],c2=y[i]-y[j]. Let f(a)=X(i,a)-Y(i,a). The function f is continuous, and changes its sign when tan(a)=c1/c2, that is, a=atan2(c1,c2)+PI*n. If beta-alpha

Now we have:

  • if rightmost(alpha)=rightmost(beta) and beta-alpha < PI, then rightmost(x)=rightmost(alpha) for all alpha < x < beta.
  • if i=rightmost(alpha)=second_rightmost(beta), and j=rightmost(beta)=second_rightmost(alpha), and beta-alpha < PI, then for all x between alpha and beta, rightnost(x) is either i or j, and the point of change is atan2(y[i]-y[j], x[i]-x[j]).

This is enough to obtain with binary search at which interval which point is the rightmost. By sign inversion of angles, we get the leftmost point intervals. Since we know at which interval each point is leftmost, and each is rightmost, we can calculate the values at the borders between intervals, and select the minimal one.