使用单调多边形的多边形三角网

我有一个没有孔的简单多边形，它需要被三角化为用于物理引擎的凸多边形，并且还可以使用这些凸多边形通过三角形条进行渲染。使用单调多边形的多边形三角网

This百科文章显示了如何使用单调多边形来对多边形进行三角测量。它提供了它如何工作的简短描述，但没有足够的细节让我理解。这种方法似乎对我所需要的完美，而它链接到的Flash Demo显示该算法完全符合我的需求。

我一直在寻找谷歌寻找更好的解释算法，我只能找到库或源代码做三角测量。我宁愿学习它是如何工作的，并编写我自己的方法，但如果我需要使用预先编写的库，它将不得不这样做。

任何人都可以提供一个解释，或资源如何我可以了解这种类型的三角测量工作？

2012-02-07 Brad

是否有编程语言的要求？（请标记是否存在）是否有硬件限制 - cpu/gpu允许？ – mfa 2012-02-07 02:35:33

的CGAL库提供简单多边形的凸分解的几种实现无孔。看看这个chapter

2012-02-07 07:15:58 sloriot

我建议你看看Delaunay三角剖分：Wikipedia。 QHull是标准实现。（作为一个参考点，MATLAB依靠Qhull：link

如果Qhull是不是你的东西，尝试这个collection

2012-02-07 05:59:57 Throwback1986

旧帖子，但无论如何。值得指出的是， Delaunay三角测量用于一组点，而不是多边形 - 这只是一个轮廓 – Croolman 2017-05-09 22:38:56

回答