基于逐点插入法的Delaunay三角网快速生成算法

为满足由海量离散点数据快速生成Delaunay三角网,提出了一种基于传统的逐点插入法生成Delaunay三角网的算法,对传统逐点插入算法的点定位以及LOP算法进行优化。首先对离散点进行分块排序,按行依次插入各点,采用方向搜索技术,以最新生成的三角形作为初始三角形,可大幅缩短点定位过程的搜索路径,快速定位到插入点所在的三角形。通过确定插入点的影响范围,只更新影响范围内的三角形,避免重复计算。运用合理的数据结构,简化计算过程,可进一步提高效率。实验证明,改进后的算法可大幅提高三角网的生成速度和质量。