1

我需要旋转一个凹多边形以最小化它的高度。我正在考虑找到一条该多边形的最小直径的线，然后将其旋转以使该线与 Y 轴平行。

我的问题是如何找到这样的线？或者，是否有任何其他算法可以旋转多边形以使其高度最小化？

提前致谢。

4

1 回答 1

3 
 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;

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

另请查看： http: //www.mathworks.com/matlabcentral/fileexchange/7844-geom2d/content/geom2d/polygons2d/minimumCaliperDiameter.m

注意：这两个问题都解决了凸情况。要解决凹面情况，您只需通过执行以下操作将输入从凹面转换为凸面：

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.

凸包在 Python 中很常见。您可以使用：http ://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.ConvexHull.html

如果你不习惯使用这个库，你可以使用这个算法将你的凹形转换为凸形：（这不是要使用的，只是非常糟糕的伪代码让你了解凸包是如何计算的）

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.

换句话说，您只需去除凹入部分 :)

于 2014-05-14T01:51:39.247 回答