Поворот многоугольника на минимальную высоту
Мне нужно вращать вогнутый многоугольник, чтобы минимизировать его высоту. Я думал о том, чтобы найти линию, которая является минимальным диаметром этого многоугольника, а затем повернуть ее так, чтобы линия была параллельна оси 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.
Другими словами, вы просто удаляете вогнутые части:)