我最近问了一个关于如何把一个凹多边形切成凸多边形的问题，有人建议我做三角剖分或多边形剖分。
我使用的库(SFMLBox2D)只接受凸形状。
这就是我想知道的:
是多边形分区，还是多边形三角剖分更快?
Polygon Partitioning是如何工作的?
别忘了三角剖分也不需要做凸形…
对你的问题没有完整的回答，但如果你有一个一般的多边形(凹的，凸的，无论什么)，你正在寻找三角测量它(可能是为了随后的openGL风格渲染)，你可以看看"约束Delaunay三角测量"包。一个这样的例子是Triangle包，它被认为是快速和健壮的。
据我所知，Triangle中使用的算法具有O(nlogn)运行时复杂度。
多边形分割将多边形分割成凸多边形。
三角剖分法把它分成三角形。据我所知，划分三角形需要首先执行多边形划分，因为将凸多边形划分为三角形相对来说比较简单。
将多边形分割成凸多边形是难点。我已经写了一个程序，可以为一个类做这两件事，如果你想的话，我可以把它找出来。
我已经10年没碰过了，所以小心。