我正在编写代码，它将为2维中的(不一定是凸的)多边形构建定向的边界框(obb)树。
到目前为止，我可以找到多边形的凸包并在 shell 上使用旋转卡尺来找到多边形的最小面积的对象。
下图是一个示例。带红线和红点的黄色填充多边形表示原始多边形。凸包显示为带有黑色线条的蓝色，而obb显示为紫色线条。
(编辑)根据要求:Interactive Version-仅在chrome中测试
现在，我想扩展代码以构建OBB树，而不仅仅是OBB。这意味着我必须切割多边形，并为多边形的每一半计算新的OBB。
推荐的方法似乎是通过将OBB切成两半来切掉多边形。但是，如果我在任意一个轴的中间切开obb，则看起来必须在多边形上创建新的顶点(否则如何找到该分区的凸包？)。
最佳答案
这是我们要为其创建OBB树的凹面多边形的示例:
为了将其拆分为一组新的凹面多边形，我们可以简单地通过在中间向下切割边界框并适本地添加新的“交集”顶点来剪切当前多边形。
:
这可以在O(顶点)时间内完成，因为我们可以简单地遍历所有边缘，如果边缘与红色分割线交叉，则可以添加相交顶点。
然后可以根据这些相交顶点对多边形进行划分，以获得一组新的较小(但仍可能是凹形)多边形。至少会有两个这样的多边形(红线的每一侧一个)，但可能会更多。在下一张图片中，为强调起见，对新的多边形进行了着色:
递归计算这些较小多边形的定向边界框可得到所需的结果。例如，这是递归深度2中的框:
希望这很清楚，可以帮助那些像我一样挣扎的人!
关于javascript - 如何对定向边界框进行分区？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10790593/