[SOLVED] Rotating a Polygon to its Minimal Height

Rotating a Polygon to its Minimal Height

I need to rotate a concave polygon to minimize its height. I've thinking about finding a line which is the minimal diameter of that polygon, then rotate it so that line is parallel with Y axis.

My question is how to find such a line? Or, is there any other algorithm to rotate a polygon to so that its height is minimized?

Thanks in advance.

Solution

 ARRAY points := {P1, P2, ..., PN};

 points.delete(middle vertices of any collinear sequence of three points);

 REAL p_a := index of vertex with minimum y-coordinate;
 REAL p_b := index of vertex with maximum y-coordinate;

 REAL rotated_angle := 0;
 REAL min_width := INFINITY;

 VECTOR caliper_a(1,0);    // Caliper A points along the positive x-axis
 VECTOR caliper_b(-1,0);   // Caliper B points along the negative x-axis

 WHILE rotated_angle < PI

   // Determine the angle between each caliper and the next adjacent edge in the polygon
   VECTOR edge_a(points[p_a + 1].x - points[p_a].x, points[p_a + 1].y - points[p_a].y);
   VECTOR edge_b(points[p_b + 1].x - points[p_b].x, points[p_b + 1].y - points[p_b].y);
   REAL angle_a := angle(edge_a, caliper_a);
   REAL angle_b := angle(edge_b, caliper_b);
   REAL width := 0;

   // Rotate the calipers by the smaller of these angles
   caliper_a.rotate(min(angle_a, angle_b));
   caliper_b.rotate(min(angle_a, angle_b));

   IF angle_a < angle_b
     p_a++;  // This index should wrap around to the beginning of the array once it hits the end
     width = caliper_a.distance(points[p_b]);
   ELSE
     p_b++;  // This index should wrap around to the beginning of the array once it hits the end
     width = caliper_b.distance(points[p_a]);
   END IF

   rotated_angle = rotated_angle + min(angle_a, angle_b);

   IF (width < min_width)
     min_width = width;

   END IF
 END WHILE

 RETURN min_width;

See http://en.wikipedia.org/wiki/Rotating_calipers

Also check out: http://www.mathworks.com/matlabcentral/fileexchange/7844-geom2d/content/geom2d/polygons2d/minimumCaliperDiameter.m

Note: Both of these problems solve the convex case. To solve the concave case, you merely transform your inputs from conave to convex by doing the following:

1. Compute convex hull of your concave polygon.
2. Run algorithm above on convex polygon.
3. Once minimum height found, rotate.
4. Transform back to concave polygon.

The convex hull is very common in Python. You can use: http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.ConvexHull.html

If you aren't comfortable using this library, you can use this algorithm to convert your concave shape to convex: (this is not meant to be used, just really bad pseudocode for you to understand how convex hull is computed)

Traverse vertices of concave polygon in clockwise order
_prev = starting vertex of traversal
_middle = second vertex in traversal
FOR _next vertex in traversal:
  IF _prev -> _middle -> _next make right turn (i.e. concave part)
     Connect _prev and _next and set _middle = _next
  ELSE
     Shift _prev to _middle and _middle to _next.

In other words, you just remove concave parts :)