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

摘要

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