c++ - 多边形分区与三角剖分

Question

我最近问了这个关于如何将凹多边形切割成凸多边形的问题，有人建议我进行三角剖分或多边形分区。

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

这是我想知道的：

1. 多边形分区或多边形三角剖分更快吗？

2. 多边形分区如何工作/你是如何做到的？

---

不要忘记三角剖分也不需要制作凸形......

Answer 1

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

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

Answer 2

多边形分区将您的多边形拆分为凸多边形。
三角剖分将其分成三角形。据我了解，划分为三角形需要您首先执行多边形划分，因为将凸多边形划分为三角形相对来说是微不足道的。
将多边形分割成凸多边形是困难的部分。我已经编写了一个程序，它既可以用于课程，也可以根据需要进行挖掘。

这是我的代码： https ://github.com/meshko/triangulator/tree/master/som

我10年没碰过，所以要小心。