Поворот многоугольника на минимальную высоту

Мне нужно вращать вогнутый многоугольник, чтобы минимизировать его высоту. Я думал о том, чтобы найти линию, которая является минимальным диаметром этого многоугольника, а затем повернуть ее так, чтобы линия была параллельна оси Y.

Мой вопрос, как найти такую ​​линию? Или есть какой-нибудь другой алгоритм, чтобы повернуть многоугольник так, чтобы его высота была минимальной?

Заранее спасибо.

1 ответ

Решение
 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.

Другими словами, вы просто удаляете вогнутые части:)

Другие вопросы по тегам