javascript - 查找具有旋转轴的旋转多边形的边界框

Question

我在这里查看了其他一些接近的答案，但找不到任何解决我的问题的方法。

我有一个绕轴位置旋转的多边形，我需要找到多边形的边界框。本质上，边界框对象应该有左上角的 x 和 y 位置，以及 width 和 height 框本身。我可以使用此代码在不旋转的情况下计算多边形的框，但它也没有考虑旋转。红色方 block 是当前没有旋转的边界框，绿色圆圈是旋转轴，多边形是多边形本身。

理想情况下，我不想在每次调用时重新计算每个顶点位置以获取边界框，我希望它在数学本身中。这是一个没有旋转的多边形和边界框的示例: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
};

多边形对象结构:

• 位置是多边形的中心
• rotationAxis 是一个相对于多边形中心(位置)的向量
• vertices 数组是相对于多边形中心的向量列表

边界框结构:

如何计算旋转多边形的边界框？

Answer 1

如果您不想在任何旋转/平移之后从多边形的所有顶点重新计算与BBOX 对齐的轴，那么请从OBB 开始计算那只有 4 个顶点 ...

1. 计算未旋转/未平移多边形的 OBB

   这个操作很慢，但只完成一次(除非你的多边形正在改变形状或大小)

2. 任意多边形变换

   也以相同的方式转换OBB 顶点。然后从转换后的 OBB 顶点计算轴对齐的 BBOX(就像现在一样找到最小/最大坐标)。

通过这种方式，您只需从 4 个顶点而不是 N 来计算内容，将复杂度从 O(N) 转换为 O(1).

还有 OBB 以后可能会派上用场，因为它可以加快某些操作甚至提高碰撞测试的精度等......