我想三角化一个多边形（没有自相交，但有孔，多边形也可以是concav）。在这个问题中（例如）：带孔的二维多边形的Delaunay三角剖分提出了一种约束Delaunay三角剖分方法。我想知道的是：这是最好的方法吗？还是像"用大锤敲坚果"？另一种选择是使用一种算法来创建"正常"三角测量（例如，将多边形拆分为y单调部分并对这些部分进行三角测量），然后翻转边。但令人惊讶的是，（几乎）没有人接受这个解决方案。有原因吗？其中一种解决方案的优点和缺点是什么？（多边形可以有任意大小）
与其他方法相比，有几个原因更喜欢（受约束的）Delaunay三角测量：
-
在
R^2中，可以证明这种三角测量是对给定几何体进行三角测量的"最佳"方式，从而产生最大化最小角度的三角测量。这相当于在没有任何"瘦"元素的情况下生成质量最佳的三角形。 -
形成Delaunay三角测量是有效的（即
R^2中的O(n*log(n))）。 -
Delaunay三角剖分算法在实践中是稳健有效的。存在许多非常高质量的实现，例如Triangle和CGAL。
-
Delaunay三角剖分推广到高维问题（即
R^3中的四面体和R^d中的一般单纯形）。 -
Delaunay三角剖分导出正交对偶复形（即Voronoi图）。这对于某些类型的数值方法可能很重要。
根据你想要实现的目标，你可能会发现其中一个或多个标准很有说服力。其他选项，如耳朵修剪或单调平板三角测量，在某些领域可能具有竞争力，但IMO没有表现出相同的整体性能。
您可以尝试alpha形状。它被定义为没有超过alpha的边的delaunay三角测量。