生成Delaunay三角网的快速合成算法

合成算法结合了传统的递归分割法和逐点插入法的优点,兼顾空间和时间性能.然而,该算法不可避免地继承了两种传统算法的不足,在执行效率上受到限制.为了解决执行效率问题,提出了快速合成算法,对合成算法进行了改进和优化.该算法基于面积坐标的点定位算法和简化的高效空外接圆判断算法,从而大大提高算法的整体执行效率;同时充分考虑平面点集的任意性,适用于对任意平面点集构建Delaunay三角网.

Improved algorithm for building Delaunay triangulation

Hybridized method takes advantages of incremental insertion and divide-and-conquer algorithm , which gives attention to the capabilities of time and space reasonably. However, this algorithm succeeds to the limitations of the two traditional algorithms, such as computational inefficiency. A new fast hybridized algorithm is proposed to optimize hybridized algorithm. A way of locating points in TIN based on area coordination and a simplified efficient formula of empty circum-circle test are provided in fast hybridized algorithm to improve executing efficiency. This algorithm gives consideration to the arbitrariness of plane point set.