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

• 作者: 郭晓东
• 来源期刊: 气象与环境科学
• 学科: 工学
• 关键词: Delaunay三角化 逐点插入 凸壳构建 优化算法
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 应用技术
• 页码范围: 112-116
• 页数: 5页
• 分类号: TP301.5|TP301.6
• 字数: 3596字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭晓东		6	13	1.0	3.0