基于逐点插入法的Delaunay三角网快速生成算法

• 作者: 王解先 王龙浩
• 来源期刊: 工程勘察
• 学科: 工学
• 关键词: Delaunay三角网 逐点插入法 点定位算法
• 年，卷（期）: 2013,（10）
• 所属期刊栏目: 论文
• 页码范围: 75-79
• 分类号: TP391
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1433.2013.10.016

摘要

为满足由海量离散点数据快速生成Delaunay三角网,提出了一种基于传统的逐点插入法生成Delaunay三角网的算法,对传统逐点插入算法的点定位以及LOP算法进行优化.首先对离散点进行分块排序,按行依次插入各点,采用方向搜索技术,以最新生成的三角形作为初始三角形,可大幅缩短点定位过程的搜索路径,快速定位到插入点所在的三角形.通过确定插入点的影响范围,只更新影响范围内的三角形,避免重复计算.运用合理的数据结构,简化计算过程,可进一步提高效率.实验证明,改进后的算法可大幅提高三角网的生成速度和质量.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王解先	同济大学测绘与地理信息学院	169	1946	25.0	36.0
2	王龙浩	同济大学测绘与地理信息学院	1	25	1.0	1.0