一种平面点集三角剖分算法

摘要

提出平面点集三角剖分的一种新算法，该算法首先将点集连成一个特殊的简单多边形，三角剖分这个简单多边形；然后不断地删去简单多边形的凹点，扩大多边形区域以及三角剖分增加的区域，直到简单多边形扩大为凸多边形，即为点集的凸壳；最后按最小内角最大的三角化准则，通过局部变换调整三角形的形态。论文对算法的正确性做出了严格的证明，并给出了时间复杂度分析和实例。在保证三角剖分结果中三角形形态质量的前提下，算法的时间复杂度为O(nlogn)（其中为平面点集中点的个数）。