一种Delaunay三角网数模快速定位算法

An Algorithm for Fast Locating Delaunay Triangular Digital Terrain Model

逐点插入法是构建Delaunay三角网的主流算法之一,在众多三角形中快速定位目标三角形是影响逐点插入法构网速度的一个重要因素,同时也是影响高程内插速度的关键。在分析多种已有定位法特点的基础上提出区域定位法,给出了详细的判断条件,并加以证明。通过对几种定位方法进行分析比较,在两种投点方式下用逐点插入法对四种算法进行了TIN的构网实验,结果表明均匀投点的构网速度都要快于任意投点的构网速度,区域定位法搜索方向唯一,算法稳健,具有较快的定位速度。

The incre mental insertion algorithm is one of main algorithms in constructing Delaunay triangular net.The fast locating destination triangle in multitudinous triangles has great effect on efficiency of constructing Delaunay triangular net by incre mental insertion algorithm as well as on the speed of interpolation elevation.In this paper,regional locating algorithm are presented based on analyzing the characteristic of multi-aglorithm,detailed judge conditions are advanced and proved.Analytical compare with locating algorithms of above mentioned and conduct constructing TIN test of four algorithms by incre mental insertion algorithm in two way point distributions.It is shown that the constructing speed of equidistribution points is faster than maldistribution points,the search direction of oriented locating algorithm is unique and algorithmic is steady with fast locating speed.