单调多边形三角剖分

4
我有一个简单的多边形,没有洞,需要将其三角剖分为凸多边形以供物理引擎使用,并且使我可以通过三角形条带进行渲染。
这个维基百科文章(链接)展示了如何使用单调多边形来三角剖分一个多边形。它提供了一个简短的描述,但不足以让我理解。这种方法似乎非常适合我的需求,而它链接到的Flash演示表明该算法完全符合我的需求。
我一直在谷歌上搜索更好的算法解释,但只能找到执行三角剖分的库或源代码。我更愿意学习如何工作并编写自己的方法,但如果我需要使用预先编写的库,则必须使用它。
有人能提供解释或资源,以便我可以学习这种类型的三角剖分是如何工作的吗?

有编程语言要求吗?(如果有,请标记)是否有硬件限制 - 允许使用哪些CPU / GPU? - mfa
2个回答

3

CGAL库提供了几种无洞简单多边形的凸包分解实现。请参阅此章节


0

我建议你看一下德劳内三角剖分: WikipediaQHull是标准的实现。(作为参考,MATLAB 依赖于 Qhull: link

如果 Qhull 不适合你,可以试试这个 collection


旧帖子,但无论如何。值得指出的是,Delaunay三角剖分是用于一组点,而不是多边形——它只是一个轮廓。 - Croolman

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接