Вычисление ограничительного прямоугольника под углом полигона
4 ответа
Чтобы получить ограничивающую рамку с определенным углом, поверните многоугольник в обратную сторону на этот угол. Затем вы можете использовать координаты min / max x / y, чтобы получить простую ограничивающую рамку и повернуть ее на угол, чтобы получить окончательный результат.
Из вашего комментария кажется, что у вас проблемы с получением центральной точки многоугольника. Центр многоугольника должен быть средним значением суммы координат каждой точки. Итак, для точек P1, ..., PN рассчитайте:
xsum = p1.x + ... + pn.x;
ysum = p1.y + ... + pn.y;
xcenter = xsum / n;
ycenter = ysum / n;
Чтобы закончить, я также добавляю несколько формул для задействованного вращения. Чтобы повернуть точку (x, y) вокруг центральной точки (cx, cy), сделайте следующее:
// Translate center to (0,0)
xt = x - cx;
yt = y - cy;
// Rotate by angle alpha (make sure to convert alpha to radians if needed)
xr = xt * cos(alpha) - yt * sin(alpha);
yr = xt * sin(alpha) + yt * cos(alpha);
// Translate back to (cx, cy)
result.x = xr + cx;
result.y = yr + cx;
Я интерпретирую ваш вопрос как означающий: «Для данного двумерного многоугольника, как вы вычисляете положение ограничивающего прямоугольника, для которого заранее определен угол ориентации?»
И я будет делать это, вращая многоугольник против угла ориентации, а затем использовать простой поиск его максимальной и минимальной точек в двух основных направлениях с использованием любого алгоритма поиска, подходящего для структуры, в которой хранятся точки многоугольника. (проще говоря , вам нужно найти наивысшее и наименьшее значения X, а также наибольшее и наименьшее значения Y.)
Затем минимумы и максимумы определяют ваш прямоугольник.
Вы можете сделать то же самое, не вращая сначала многоугольник, но выполняя поиск для минимальных и максимальных точек должен быть более сложным.
Чтобы получить самый маленький прямоугольник, вы должны получить прямой угол. Это может быть выполнено с помощью алгоритма, используемого при обнаружении столкновений: ориентированных ограничивающих рамок. Основные шаги:
Получить координаты всех вершин
Постройте ковариационную матрицу
Найдите собственные значения
Проецировать все вершины в пространстве собственных значений
Найдите максимальное и минимальное значения в каждом пространстве собственных значений.
Для получения дополнительной информации просто Google OBB "обнаружение столкновений"
Ps: Если вы просто проецируете все вершины и находите максимум и минимум, вы создаете AABB (ограничивающая рамка, выровненная по оси). Это проще и требует меньших вычислительных затрат, но не гарантирует минимальную коробку.
Чтобы получить прямоугольник с минимальной площадью, охватывающий многоугольник, вы можете использовать алгоритм вращающихся измерителей .
Ключевой вывод состоит в том, что (в отличие от вашего примера изображения, поэтому я предполагаю, что вам на самом деле не нужна минимальная площадь?), Любой такой минимальный прямоугольник коллинеарен по крайней мере с одним краем (выпуклой оболочкой) многоугольника.