javascript - 如何划分定向边界框？

Question

我正在编写代码，为二维(不一定是凸的)多边形构建定向边界框 (obb) 树。

到目前为止，我可以通过找到凸包并在凸包上使用旋转卡尺来找到多边形的面积最小 obb。

下图就是一个例子。带有红线和红点的黄色填充多边形描绘了原始多边形。凸包显示为蓝色和黑色线条，obb 显示为紫色线条。

(编辑)按要求:Interactive Version - 仅在 chrome 中测试

现在我想扩展我的代码来构建一个 OBB 树，而不仅仅是一个 OBB。这意味着我必须切割多边形，并为多边形的每一半计算新的 OBB。

执行此操作的推荐方法似乎是通过将 OBB 切成两半来切割多边形。但是，如果我将 obb 从它的任一轴的中间切开，看起来我必须在多边形上创建新的顶点(否则我如何找到该分区的凸包？)。

1. 有没有办法避免像这样添加顶点？
2. 如果不是，最简单的方法是什么(关于实现难度)？运行时效率最高的方法是什么？

Answer 1

这是我们要为其创建 OBB 树的凹多边形示例:

为了将其拆分为一组新的凹多边形，我们可以通过从中间切割边界框并适当添加新的“相交”顶点来简单地切割当前多边形:

:

这可以在 O(vertices) 时间内完成，因为我们可以简单地遍历所有边，并在边穿过红色分割线时添加一个相交顶点。

然后可以根据这些相交顶点划分多边形以获得一组新的更小(但仍可能是凹的)多边形。至少会有两个这样的多边形(红线的每一侧一个)，但可能会有更多。在下一张图片中，新的多边形已被着色以强调:

递归计算这些较小多边形的定向边界框可得到所需的结果。例如，这里是递归深度 2 的框:

希望这足够清楚，可以帮助那些和我一样挣扎的人!