多边形分区与三角测量

Question

我最近问过这个问题,关于如何将凹多边形切割成凸多边形,我建议做三角剖分或多边形分区.

我正在使用的库(SFML\Box2D)只采用凸形.

这就是我想知道的:

1. 多边形分区或多边形的三角测量更快吗？

2. Polygon Partitioning如何工作/你是如何做到的？

---

不要忘记三角测量不需要凸起的形状......

Answer 1

不是您问题的完整答案，但如果您有一个通用多边形（凹面、凸面等）并且您希望对其进行三角剖分（也许用于后续的 openGL 样式渲染），您可以查看“约束 Delaunay 三角剖分”包。Triangle包就是这样的一个例子，它被认为是快速且强大的。

据我了解，Triangle 中使用的算法表现出O(nlogn)运行时复杂性。