简单的二维多边形三角剖分

Question

尝试对一组简单的2D多边形进行三角测量，我想出了以下算法：

• 1）对于多边形中的每个顶点，计算连接的两条边之间的夹角
• 2）按相对于多边形内部递减的角度对顶点进行排序
• 3）如果集合中的顶点少于3个，则完成
• 4）取集合中的最后一个顶点并输出由它及其两个相邻顶点形成的三角形
• 5）从集合中删除该顶点
• 6）更新两个相邻顶点的角度
• 7）跳转到第2步

我已经测试过它，在真正大而复杂的简单2D多边形上运作良好（它不能用于具有孔或自相交多边形）。

还有会产生退化结果的异常情况吗？

这个算法是众所周知的吗？

如果不是，我想确保这个算法非常稳定，但我没有数学背景来证明它。

非常感谢。

- Nicolas Repiquet

---

可能是Tessellating an arbitrary polygon by tiling triangles的重复问题。 - ideasman42

Answer 1

您正在进行“剪耳朵”三角剖分的一种版本，参见：http://en.wikipedia.org/wiki/Polygon_triangulation 如果多边形的另一个顶点（比如来自多边形的另一侧）位于您形成的三角形“耳朵”内，您的算法将失败。考虑以下示例： 您的算法首先选择A，并使用相邻两条边（用虚线连接）构成一个三角形。但是，这个三角形包含另一个顶点B且明显不正确。

常规的剪耳朵方法取决于找到可以切除的没有包含任何顶点的“耳朵”。

- payne

Answer 2

简单的凸多边形是O(n)级别的

这适用于处理诸如矩形、五边形、六边形等简单的多边形。在此，您只需从一个起点开始并将其连接到所有其他顶点。该算法非常简单，但我真正想要的是一种更通用的解决方案，可以处理凹多边形和带孔多边形。

为了处理像Payne提供的更复杂的多边形...

O(n log n)级别的任意多边形转三角形

虽然有更快的算法，但更快的算法变得非常复杂。Kirkpatrick et al.发现了一种算法可以在O(n log log n)内运行，Chazelle使用O(n)完成。但是，最容易实现的可能是Seidel算法，它的运行时间为O(n log n)。

该算法是一个3步过程

1. 将多边形分解为梯形
2. 将梯形分解为单调多边形
3. 将单调多边形分解为三角形

C源代码

如果您对C源代码感兴趣，可以从北卡罗来纳大学教堂山分校获取。总体而言，代码质量良好，处理孔时表现良好，但可能需要根据您的需求进行修改。

- Cameron Lowell Palmer

---

请注意，Seidel算法代码的许可证禁止商业使用。 - Mikko Virkkilä

Answer 3

如果我理解得正确，您正在从具有最小内角的三角形开始削减。如果多边形不是凸多边形，则此方法可能会失败。考虑具有以下顶点（按顺序）的多边形：(0,0) (10,9) (9,9) (9,10)。最小角度在原点处，但您不能安全地切掉该三角形。

（如果您的多边形是凸多边形，则可以选择任何一个顶点，删除那里的一个三角形，并重复此过程。因此，我猜想您希望您的算法也适用于非凸多边形。）

- Gareth McCaughan

Answer 4

尽管耳剪法相对有效，但随着多边形复杂度的增加，缩减每个耳朵时检查整个多边形会变得越来越慢，因此简单的方法会变慢。

来自 libgdx 的耳剪算法是一个很好的起点，因为它非常健壮 - 使用了 FIST (快速工业级多边形三角化)。

我将其用作多边形镶嵌的基础，然后添加了用于点和三角形测试的空间优化 (O(n log n) 而不是 O(n^2))。

参见:

• C 代码、测试。
• Rust 代码、测试
• 来自 libgdx 的原始代码。

---

请注意，虽然该算法并不明确支持孔，但您可以在分离的岛之间使用 钥匙孔边缘，这样就可以正确地三角化了。

- ideasman42

---

钥匙孔链接现已失效。从谷歌上看，似乎只是从每个洞的外部顶点到内部顶点“切”多边形，使拓扑成为单环。 - Simon Buchan