Вычисление ограничивающего прямоугольника под углом многоугольника

Question

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

альтернативный текст http://kevlar.net/RotatedBoundingRectangle.png

Розовый прямоугольник - это то, что мне нужно определить под разными углами для простых 2D-полигонов.

Любые решения очень ценятся!

Edit:

Спасибо за ответы, я заработал, как только правильно установил центральные точки. Вы, ребята, потрясающие!

Answer 1

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

Answer 2

Чтобы получить наименьший прямоугольник, вы должны получить правильный угол. Это может быть достигнуто с помощью алгоритма, используемого при обнаружении столкновений: ориентированные ограничивающие рамки. Основные шаги:

Получить все вершины кординаты
Построить ковариационную матрицу
Найти собственные значения
Спроецировать все вершины в пространстве собственных значений
Найти максимальное и минимальное значения в каждом пространстве собственных значений.

Для получения дополнительной информации просто Google OBB "Обнаружение столкновения"

Ps: Если вы просто проецируете все вершины и находите максимум и минимум, вы создаете AABB (ограничивающий прямоугольник по оси). Это проще и требует меньше вычислительных усилий, но не гарантирует минимальную коробку.

Answer 3

Я интерпретирую ваш вопрос как «Для данного 2D многоугольника, как вы рассчитываете положение ограничивающего прямоугольника, для которого задан угол ориентации?»

И я бы сделал это, повернув многоугольник против угла ориентации, а затем использовал бы простой поиск его максимальных и минимальных точек в двух основных направлениях, используя любой алгоритм поиска, подходящий для структуры, в которой хранятся точки многоугольника. в. (Проще говоря, вам нужно найти самое высокое и самое низкое значения X, а также самое высокое и самое низкое значения Y).

Тогда минимумы и максимумы определяют ваш прямоугольник.

Вы можете сделать то же самое, не поворачивая многоугольник, но ваш поиск минимальных и максимальных точек должен быть более сложным.

Answer 4

Чтобы получить прямоугольник с минимальной площадью, охватывающей многоугольник, вы можете использовать алгоритм вращающихся штангенциркулей .

Ключевое понимание заключается в том, что (в отличие от вашего образца изображения, поэтому я предполагаю, что вам на самом деле не требуется минимальная площадь?), Любой такой минимальный прямоугольник является коллинеарным по крайней мере с одним краем (выпуклой оболочки) многоугольника.