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

摘要：

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

关键词：Delaunay三角网、逐点插入法、点定位算法

所属期刊栏目：41

分类号：TP391(计算技术、计算机技术)

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

页数：共5页

页码：75-79