Delaunay三角形网络逐点插入法的优化算法

摘要：

Delaunay三角形网络逐点插入法虽简单易行,但效率低下.针对其效率低下原因,提出一种改进的Delaunay三角形网络逐点插入生成算法.将已知插入点X坐标大小排序,当X坐标相等时,以Y坐标大小顺序排序构建新的插入点顺序,并得到插入点坐标集合中的最大值和最小值.适当放大插入点坐标中最大值、缩小坐标最小值后,得到X、Y坐标新的两个最大值和两个最小值,用4个值构建4个临时新插入点,可以构建出Delaunay三角形网络矩形的凸壳.按照新的插入点顺序逐点插入构建三角形网络,只判断插入点与以X坐标最大的两个边界矩形顶点为顶点的三角形位置关系.生成三角形网络后删除与4个临时顶点相关的三角形,就是所需要的三角形网络.通过证明每个插入点必定落在X坐标最大的两个边界矩形顶点为顶点构成的三角形上,可以减少插入点与已生成三角形位置关系的判断次数,较大程度提高逐点插入法的效率.将新算法与常规算法计算复杂度比较,结果表明,改进的算法能提高逐点插入效率,运算量稳定,达到逐点插入法的最好水平.

关键词：Delaunay三角化、逐点插入、凸壳构建、优化算法

所属期刊栏目：37

分类号：TP301.5;TP301.6(计算技术、计算机技术)

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

页数：共5页

页码：112-116