sho*_*hit 4 algorithm graphics topology tesselation
我有一组形成闭合多边形的 2D 点坐标。我需要生成一组完全分布多边形的二维三角形。
除了三角形应完全填充多边形区域之外，没有任何限制。如果它是我可以实现的标准算法，那就更有帮助了。
对一般多边形进行三角剖分的最佳方法是计算受约束的Delaunay 三角剖分- 这是多边形顶点的标准 Delaunay 三角剖分，并施加附加约束以确保多边形边明确出现在三角剖分中。这种类型的方法可以处理任何类型的多边形 - 凸多边形、凹多边形、带孔多边形等。
Delaunay 三角剖分是使网格中的最小角度最大化的三角剖分，这意味着这种三角剖分在单元形状质量方面是最佳的。
编写约束 Delaunay 三角剖分算法是一项棘手的任务，但存在许多优秀的库，特别是CGAL和Triangle。这两个库都实现了（最佳）高效的O(n*log(n))算法。