构建 Delaunay 三角网的一种新型生长法——壳外插入法

摘要

基于逐点插入法中影响域的概念,提出一种新的三角网生长算法——壳外插入法.该算法以三角网外围的凸包生长为基础,通过查找生长边、内蚀既有网、重构三角网3个基本操作,达到既有网在保持Delaunay特性的同时纳入新点,从而实现三角网的生长.该算法克服了传统生长法需要查找第3点的缺陷,也避免了逐点内插法大量三角形定位的操作,因而算法的平均复杂度达到O(NlogN).使用了大量的随机散点数据和常吉高速的实测地形点数据对算法进行测试,证实该算法快速有效.