algorithm - 如何将多边形转换为非重叠三角形上的集合？

Question

我有一个二维点的坐标集，它们形成一个封闭的多边形。我需要生成一组完全分布多边形的二维三角形。

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

Answer 1

对一般多边形进行三角剖分的最佳方法是计算受约束的Delaunay 三角剖分- 这是多边形顶点的标准 Delaunay 三角剖分，附加约束以确保多边形边明确出现在三角剖分中。这种类型的方法可以处理任何类型的多边形——凸面、凹面、带孔的多边形等。

Delaunay 三角剖分是最大化网格中最小角度的三角剖分，这意味着这种三角剖分在单元形状质量方面是最佳的。

编写一个受约束的 Delaunay 三角剖分算法是一项棘手的任务，但存在许多优秀的库，特别是CGAL和Triangle。这两个库都实现了（最佳）高效O(n*log(n))算法。

Answer 2

如上所述，Delaunay 三角剖分是一项相当复杂的算法。如果您接受 O(n^2) 运行时间，您可以尝试更容易理解和编码的 Ear Clipping 算法。基本思路如下。每个具有 >= 4 个顶点且没有孔的多边形（即其边界是一条没有自相交和自相切的单折线）至少有一个“耳朵”。耳朵是三个连续的顶点，因此建立在它们上的三角形位于多边形内部，并且不包含多边形内部的其他点。如果你“剪掉一只耳朵”（在答案中添加一个三角形并替换删除这三个点的中间点），你将任务减少到一个顶点更少的多边形，等等。耳朵可能在 O(n^2) 中很容易（根据定义）找到，从而导致 O(n^3) 三角测量算法。

此外，如果您需要更快的算法，您应该了解单调多边形三角剖分并将多边形拆分为单调多边形。甚至还有一种线性时间三角剖分算法，但它和 Delaunay 三角剖分一样复杂。

您可以考虑Wikipedia 文章并在那里查看现有方法的小概述。

Answer 3

如果您不要求三角形的顶点是多边形的顶点，请尝试基于梯形分解的三角剖分，如基于 Seidel 算法的快速多边形三角剖分。