一种改进的高效Delaunay三角网的生成算法

Delaunay三角网在GIS／VR中具有很广泛的用途，而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。本在研究了基于这两种算法的合成算法后，对其进行了修改和优化，形成了高效合成算法。高效合成算法中提出了通过确定点线关系来解决点的定位问题，优化了其LOP的算法，提高了算法的稳定性，使其执行效率得到很明显地提高，本算法的设计思想还可推广到三维空间。

An Improved High-efficiency Algorithm of Delaunay Triangulation Generation

Delaunay triangulation has widely application in Geographic Information System and Virtual Reality, and its prevalent two generation algorithms are divide-conquer and incremental insertion algorithms. After study on the compound algorithm which is based on the two mentioned ones, the high- efficiency-compound algorithm is posed in order to modify and optimize the first compound one. A way of locating point in TIN based on the relation of points and line is provided in the high-efficiency compound algorithm,and the LOP algorithm is optimized. So the high-efficiency compound algorithm has better stability and efficiency. The design idea of the generation algorithm can extend to the 3D space.