简单的2d多边形三角剖分
Nic*_*uet 10 algorithm geometry 2d triangulation
试图对一组简单的2d多边形进行三角测量,我想出了这个算法:
- 1)对于多边形中的每个顶点,计算两个链接边之间的角度
- 2)通过相对于多边形内部减小角度来对顶点进行排序
- 3)如果集合中的顶点少于3个,我们就完成了
- 4)取出集合中的最后一个顶点,输出由它和它的两个邻居形成的三角形
- 5)从集合中删除顶点
- 6)更新两个邻居的角度
- 7)跳到2
我已经对它进行了测试,发现它甚至可以在非常大而复杂的简单2d多边形上工作(它不适用于带有孔或自相交多边形的多边形).
是否有会产生退化结果的角落案例？
这个算法是否已知？
如果没有,我想确定这个算法是坚如磐石的,但我没有数学背景证明它.
非常感谢.
您正在进行三角测量的"耳夹"方法,请参阅:http: //en.wikipedia.org/wiki/Polygon_triangulation
如果另一个多边形顶点(例如从多边形的另一侧)最终在您形成的三角形"耳朵"内,则算法会失败.考虑这个例子:
您的算法将首先选择A,并使用两个相邻边(与虚线连接)形成三角形.但是这个三角形包括另一个顶点(B),显然不正确.
广义的耳朵剪切方法取决于找到没有任何包含顶点的剪切耳朵.
简单凸多边形的复杂度为 O(n)
当您想要处理简单的多边形（如矩形、五边形、六边形等）时。在这里，您只需选取一个起点并将其连接到所有其他顶点。这个算法很简单，我真正想要的是一个更通用的解决方案，可以处理凹面和带孔的多边形。
为了处理更复杂的多边形，比如佩恩提供的多边形......
任意多边形到三角形的 O(n log n)
虽然有些算法运行得更快，但更快的算法变得非常复杂。柯克帕特里克等人。找到了一种在 O(n log log n) 内运行的算法，而Chazelle在 O(n) 内完成了它。然而，最容易实现的可能是运行时间复杂度为 O(n log n) 的Seidel 算法。
该算法分为 3 步过程
- 将多边形分解为梯形
- 将梯形分解为单调多边形
- 将单调多边形分解为三角形
C源代码
如果您对 C 源代码感兴趣，可以从北卡罗来纳大学教堂山分校获得。一般来说，代码质量很好，可以处理漏洞，但可能需要根据您的需要进行调整。
如果我理解正确的话，你会从最小的内角开始切掉三角形。如果多边形不是凸的，则此操作可能会失败。考虑一个多边形，其顶点（按顺序）位于：(0,0) (10,9) (9,9) (9,10)。最小的角度是原点处的角度，但您无法安全地切断该三角形。
（如果你的多边形是凸的，那么你可以选择任何顶点，删除那里的三角形，然后重复。所以我猜你希望你的算法即使对于非凸多边形也能工作。）