我有一个由二维点组成的闭合多边形坐标集。我需要生成一组二维三角形,使得多边形被完全覆盖。
除了要求三角形填满多边形的区域之外,没有其他限制。如果这是一个标准算法,那就更好了,我可以直接实现它。
除了要求三角形填满多边形的区域之外,没有其他限制。如果这是一个标准算法,那就更好了,我可以直接实现它。
O(n*log(n))
算法。此外,如果您需要更快的算法,则应了解一些关于单调多边形三角剖分和将多边形分割为单调多边形的内容。甚至存在一种线性时间三角剖分算法,但它与Delaunay三角剖分一样复杂。
你可以考虑维基百科文章,并在那里看到现有方法的简要概述。