基于凸壳技术的Delaunay三角网生成算法

An Algorithm of Building Delaunay Triangulation Based on Convex Hull

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。

The paper presents an algorithm of building Delaunay triangulation of scattered point set.Firstly all scattered points are stored in angle.Secondly the sorted points are added to triangular mesh which has created using convex hull technology.Finally triangular mesh is optimized into Delaunay triangulation using topological structures.In process of adding point to triangular mes.h,a few points should be test for the fully using the character of convex hull. Experimental results show that the method is robust and efficient in computation.