如何将多边形转换为非重叠三角形上的一组？

Question

我有一个坐标组的2D点，形成一个封闭的多边形。我需要生成一组完整分布多边形的二维三角形。

除了三角形应完全填充多边形区域外，没有限制。如果它是我可以实现的标准算法，那将会更有帮助。

Answer 1

如上所述，Delaunay三角测量是一项相当复杂的算法。如果您接受O（n^2）的运行时间，您可以尝试更容易理解和编码的耳廓修剪算法。基本思想是以下几点。每个> = 4个顶点且没有孔的多边形（即其边界是没有自交和自相位的单条多段线）至少有一个“耳朵”。耳朵是三个连续的顶点，使得它们上的三角形位于多边形的内部，并且不包含其中的多边形其他点。如果您“切耳朵”（在答案中添加一个三角形并替换移除这三个点的中点），则将任务减少为顶点较少的多边形，依此类推。在O（n^2）中发现的耳朵可能是微不足道的（根据定义），导致O（n^3）三角测量算法。有O（n）耳朵发现算法，虽然它不是很复杂，但用几个短语来描述它是相当长的。此外，如果您需要更快的算法，您应该查看一些关于单调多边形三角剖分和将多边形分成单调多边形的内容。甚至还存在线性时间三角测量算法，但它与德劳内三角测量一样复杂。

您可能会考虑Wikipedia article并查看当前现有方法的简要概述。

Answer 2

对一般多边形进行三角剖分的最佳方法是计算约束条件Delaunay triangulation - 这是一个标准的多边形顶点Delaunay三角剖分，施加了额外约束以确保多边形边缘明确显示在三角剖分中。这种类型的方法可以处理任何类型的多边形 - 凸形，凹形，具有孔多边形等

Delaunay三角是那些最大化的最小角度在网格，这意味着这样的三角测量是在最佳元件形状方面质量。

对约束Delaunay三角测量算法进行编码是一项棘手的任务，但存在许多好的库，特别是CGAL和Triangle。这两个库实现（最佳）高效的算法。

Answer 3

如果您不要求三角形的顶点是多边形的顶点，请尝试基于梯形分解的三角测量，如Fast Polygon Triangulation based on Seidel's Algorithm。