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

Question

Я просмотрел некоторые другие близкие ответы здесь, но не могу найти решения моей проблемы.

У меня есть многоугольник, который вращается вокруг позиции оси, и мне нужно найтиограничительная рамка многоугольника.По сути, ограничивающий прямоугольник должен иметь позицию x и y в верхнем левом углу и width и height самого прямоугольника.Я могу вычислить прямоугольник многоугольника без вращения, используя этот код, но он не учитывает и вращение.Красный квадрат - это текущий ограничивающий прямоугольник без вращения, зеленый круг - это ось вращения, а многоугольник - сам многоугольник.

В идеале,Я не хочу пересчитывать каждую позицию вершины в каждом вызове, чтобы получить ограничивающий прямоугольник, я хочу, чтобы это было в самой математике.Вот пример многоугольника и ограничивающего прямоугольника без вращения: https://i.imgur.com/MSOM9Q1.mp4

Вот мой текущий код для нахождения ограничивающего прямоугольника для не повернутого многоугольника:

const minX = Math.min(...this.vertices.map((vertex) => vertex.x));
const minY = Math.min(...this.vertices.map((vertex) => vertex.y));

return {
    x: minX + this.position.x,
    y: minY + this.position.y,
    width: Math.max(...this.vertices.map((vertex) => vertex.x)) - minX,
    height: Math.max(...this.vertices.map((vertex) => vertex.y)) - minY
};

Структура объекта многоугольника:

• * position - центр многоугольника
• * rotationAxis - вектор относительноцентр многоугольника (позиция)
• Массив vertices представляет собой список векторов относительно центра многоугольника

Структура ограничительной рамки:

Что мне нужно сделать, чтобы вычислить ограничивающую рамку повернутого многоугольника?

Answer 1

, если вы не хотите пересчитывать ось, выровненную BBOX из всех вершин многоугольника после любого поворота / перемещения, тогда сделайте это из OBB , то есть только 4 вершин ...

1. Вычислить OBB не повернутого / непереведенного многоугольника

   эта операция медленная, но выполняется только один раз (если ваш многоугольник не меняет форму или размер)

2. При любом преобразовании многоугольника

   преобразуйте также вершины OBB аналогичным образом.А затем вычислить выровненную ось BBOX из преобразованных OBB вершин (просто находя минимальные / максимальные координаты, как вы делаете сейчас).

Таким образом, выприходится вычислять вещи только из 4 вершин вместо N, преобразуя сложность из O(N) в O(1).

Кроме того, наличие OBB может пригодиться позже, так как оно может ускоритьнекоторые операции или даже улучшить точность тестирования столкновений и т.д ...