基于分治策略的快速构建Delaunay三角网算法 (2007年)

目的降低构建Delaunay三角网的时间复杂度，提高构建Delaunay三角网的速度。方法首先递归分割点集，然后按照构网条件以分割线为轴线对其两侧的点进行构造三角网的操作，直至每个点都被包含进所构建的三角网，最后使其成为Delaunay三角网。结果通过1000-5000个点的测试，表明基于分治策略的快速构建Delaunay三角网的生成速度要快于传统基于分治策略生成Delaunay三角网的速度。结论该方法能够到边建网边优化，使程序一次成型，提高了建网速度，本算法的设计思想还可以推广到三维空间。