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

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

A new growth algorithm for creating delaunay triangulation: outside insertion algorithm

The influential area which was a concept of incremental insertion algorithm was introduced and a new growth algorithm was presented.The method of fast creating Delaunay triangulation was named as outside insertion algorithm.The algorithm bases on the growth of convex hull,and through finding growth edges,eroding the existing net and restructuring these three essential operations to keep Delaunay character while bringing a new point into the net during the process.Using the algorithm,the disadvantages of finding the third point in the traditional growth algorithm was avoided and the mass operations that locate the triangles in the incremental insertion algorithm.So the average complexity of the algorithm is O(NlogN).The algorithm was tested with mass random points data and the real terrain points data from Chang-Ji expressway.The result proves that the algorithm is fast and efficiency.