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

摘要：

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

关键词： 三角剖分 简单多边形 凸壳 时间复杂度 计算几何 平面点集 凸多边形

作者: 施建娟 岳昊 刘国林 刘斌

作者单位: 山东科技大学信息科学与工程学院，山东青岛,266510 山东科技大学地球科学与工程学院，山东青岛,266510

会议类型: 国内会议

会议名称: 中国测绘学会大地测量专业委员会2007年综合性学术年会

会议地点: 青岛

会议语种:中文

在线出版日期: 2007-11-01（万方平台首次上网日期，不代表论文的发表时间）