利用自适应分块的任意多边形三角剖分算法

摘要：

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法.多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接.至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率.利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分.算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性.

关键词：三角剖分、Delaunay三角剖分、自适应分块、任意多边形、约束边

所属期刊栏目：27

分类号：P208;TP391(一般性问题)

资助基金：国家自然科学基金资助项目40671162,40701157;国家863计划资助项目2007AA12Z211;河南省创新型科技人才队伍建设工程资助项目;测绘学院院课题Y0908

在线出版日期：2010-04-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：70-74