如何分区定向边界框？

Question

我正在编写代码,为2维的(不一定是凸的)多边形构建一个定向边界框(obb)树.

到目前为止,我能够通过找到它的凸包并在船体上使用旋转卡尺来找到多边形的面积最小的obb.

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

(编辑)根据要求:交互式版本 - 仅在chrome中测试

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

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

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

Answer 1

以下是我们要为其创建 OBB 树的凹多边形示例：

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

:

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

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

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

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