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

详细信息    查看全文 | 下载全文 | 推荐本文 |

• 作者：施建娟岳昊刘国林刘斌
• 会议时间：2007-11-01
• 关键词：三角剖分 ; 简单多边形 ; 凸壳 ; 时间复杂度 ; 计算几何 ; 平面点集 ; 凸多边形
• 作者单位：施建娟,岳昊(山东科技大学信息科学与工程学院,山东青岛,266510)刘国林,刘斌(山东科技大学地球科学与工程学院,山东青岛,266510)
• 会议名称：中国测绘学会大地测量专业委员会2007年综合性学术年会
• 会议地点：青岛
• 主办单位：中国测绘学会
• 语种：chi

摘要

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