复杂多边形的凸分解？

Question

我使用的2D物理引擎（box2D）和OpenGL都要求将复杂的多边形分解为凸多边形。确保模型符合此要求很容易。但是，我还希望在模拟过程中编辑这些多边形，因此我需要一种动态的方法将现有多边形分解为更多仍然是凸多边形的多边形。

我希望这张图能够描述我的需求：

我的问题是，是否存在可以实现这一功能的现成库？如果没有，自己实现最少出错的方法是什么？

（我正在查阅Boost文档，它有Geometry和Polygon两个模块，但是文档对我来说有点晦涩，不知道它们是否可以满足我的需求。）

- Anne Quinn

---

绝对不理解你的公式 - B-A 应该是 B 中与 A 没有重叠部分，而我不知道 A*B 可能意味着什么，当然也不知道它如何等于 C3。 - Matt Phillips

@Matt - 抱歉，我的方程式是反过来的。A * B 应该找到交集，而 B - A 应该找到 A 的非重叠部分。我只是为了需要运算符而随意添加了这些运算符，我不确定这种情况的实际运算符是什么。 - Anne Quinn

传统上，交集用倒置的u形表示，^可能是您可以使用ascii的最佳选择。 A的非重叠部分是A-B，这恰好不是B_A！相当令人困惑。此外，找到由A和B相交边形成的顶点的方法是否符合您的要求？ - Matt Phillips

@Clairvoire 我认为你正在寻找交集运算符∩。要进行差异操作，您需要一个补集：在集合符号中，B-A是B∩!A，而交集只是B∩A。 - Ozzah

@Matt - 我想这可能是其中的一部分，但让我困扰的主要问题是找到合适的现有顶点将它们连接起来，形成凸多边形。 - Anne Quinn

Answer 1

我认为这个是你要找的。

至于如何找到交点，那只需要一点代数就可以了；对于任意两条线段，很容易导出相应的线（“上升下降”，等等），

y = a1*x + b1

y = a2*x + b2

然后交点(x'，y')为：

x' = (b2 - b1) / (a1 - a2)

y' = a1*x' + b1

当然，这是直线的交点，要确定线段是否相交，您需要用x、y坐标进行简单的范围检查。

- Matt Phillips