格网划分的Delaunay三角网快速生成算法

摘要：

针对常见的三角网构建算法效率受查找三角形的约束的问题,该文提出了一种基于格网划分的Delaunay三角网快速生成算法,对传统逐点插入算法的点定位及LOP算法进行了优化.通过对离散点数据进行格网划分,将三角形面积坐标法与直线行走算法相结合,在点定位过程中可大幅度缩短搜索路径,快速定位到插入点所在的目标三角形.实验结果表明,改进后的算法兼顾了时间和空间的性能,执行效率明显提高,定位路径惟一且为最佳路径.

关键词：Delaunay三角网、逐点插入算法、格网划分、点定位、外接圆检测

所属期刊栏目：41

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

资助基金：国家自然科学基金项目61462059;中国博士后科学基金项目2013M542396;人社部留学人员科技活动项目择优资助项目;甘肃省高等学校基本科研业务费项目214142;甘肃省自然科学基金项目1208RJZA243;陇原青年创新人才扶持计划项目201182

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

页数：共6页

页码：109-114