我有一个由二维点组成的闭合多边形坐标集。我需要生成一组二维三角形，使得多边形被完全覆盖。
除了要求三角形填满多边形的区域之外，没有其他限制。如果这是一个标准算法，那就更好了，我可以直接实现它。
除了要求三角形填满多边形的区域之外，没有其他限制。如果这是一个标准算法，那就更好了，我可以直接实现它。
3个回答
5
最佳的三角剖分通用多边形方法是计算受限Delaunay三角剖分 - 这是多边形顶点的标准Delaunay三角剖分，附加了额外的约束条件以确保多边形边缘明确出现在三角剖分中。这种方法可以处理任何类型的多边形 - 凸多边形、凹多边形、带孔多边形等。
Delaunay三角剖分是使网格中的最小角度最大化的剖分，这意味着这种三角剖分在元素形状质量方面是最优的。
编写受限Delaunay三角剖分算法是一项棘手的任务，但有许多好的库可供使用，特别是CGAL和Triangle。这两个库都实现了一个（最优）高效的
Delaunay三角剖分是使网格中的最小角度最大化的剖分，这意味着这种三角剖分在元素形状质量方面是最优的。
编写受限Delaunay三角剖分算法是一项棘手的任务，但有许多好的库可供使用，特别是CGAL和Triangle。这两个库都实现了一个（最优）高效的
O(n*log(n))算法。- Darren Engwirda
4
如上所述，Delaunay三角剖分是一个相当复杂的算法。如果您可以接受O（n ^ 2）的运行时间，可以尝试更容易理解和编码的Ear Clipping算法。其基本思想是，每个具有> = 4个顶点且没有孔（即其边界是没有自交和自切的单个折线）的多边形都至少有一个“耳朵”。耳朵是三个连续的顶点，使得建立在它们上面的三角形位于多边形内部并且不包含多边形内的其他点。如果您“剪下一只耳朵”（向答案添加一个三角形并替换这三个点中间的点），则可以将任务减少到具有较少顶点的多边形，依此类推。耳朵可以轻而易举地（按定义）以O（n ^ 2）找到，从而得到O（n ^ 3）的三角剖分算法。还有O（n）的耳朵查找算法，虽然它不是非常复杂，但描述起来相当冗长。
此外，如果您需要更快的算法，则应了解一些关于单调多边形三角剖分和将多边形分割为单调多边形的内容。甚至存在一种线性时间三角剖分算法，但它与Delaunay三角剖分一样复杂。
你可以考虑维基百科文章，并在那里看到现有方法的简要概述。- Ivan Smirnov
3
如果您不要求三角形的顶点必须是多边形的顶点，可以尝试基于梯形分解的三角剖分，例如在Fast Polygon Triangulation based on Seidel's Algorithm中。
- lhf
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接