基于平衡二叉树的三角网快速生成算法

Algorithm of delaunay triangulation generation based on AVL tree

为了研究更好的三角网构建的方法,对不规则三角网构建算法进行了研究,提出了一种基于平衡二叉树的Delaunay三角网生成算法,采用分割合并的思想,提高了搜索效率,将离散点集进行划分,通过对各个所分小块子网的合并,完成所论区域的三角剖分。分析了该算法涉及的相邻子网公切线查找、凸壳生成等关键问题。通过具体实验和同其他经典算法效率的比较,该方法具有明显的优越性。

The algorithm of irregular triangulated network generation is researched and a new algorithm based on AVL Tree is proposed .Based on division-merging thinking ,scattered points are divided and delaunay triangulation is completed in study area .Some key problems are analyzed ,such as the finding on common tangent of adjacent sub-network, protruding polygon generation ,etc. Experiment result data is deduced by Compared with other irregular ways, the algorithm shows its superiority.