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

摘要

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