空间散乱点集Delaunay三角剖分的算法优化及实现

本文在详细研究和分析了典型的Delaunay三角剖分算法的思想后，针对增量算法中的关键问题提出改进的方法，从降低算法的时间复杂度的角度出发，以点定位搜索这一关键问题为切入点，提出新的改进搜索的方法，该算法利用四面体三角面的法矢与该面的点到插入点之间形成的向量的夹角来确定定位方向，不需额外的搜索数据结构，且对于每个搜索四面体只需三个面的法矢和夹角的计算，减少了搜索过程中的计算量，且定位的路径较优，有效提高了算法的效率，使整个Delaunay三角剖分算法的时间复杂度约为O(N‘·‘2)，接近线性时间。