摘要
本文描述了一种Delaunay三角剖分的快速重建算法,用以节省三角网格存储和传输时间。该算法既可以在基于均匀网格的Delaunay三角化过程中,直接生成点集序列,也可以推广到其他Delaunay三角剖分方法的输出结果,在O(n)的时间内生成点集序列。简单遍历这个点集序列就可以在O(n)的时间内重建Delaunay三角剖分。与以前的算法相比,该算法具有重建操作简单、执行速度快、拓扑信息完全隐藏在点集序列中、不需要增量插入操作等特点。
We present a new algorithm to compute a good order for the point set of a Delaunay triangulation of n points in the plane in 0 （n） time. The order can be obtained during the Delaunay triangulation using a uniform grid or after other Delaunay triangulation methods. Such a good order makes reconstruction of the Delaunay triangulation in 0 （n） time with a simple algorithm possible. In contrast to the previous algorithms, the topology information is included in the order and the reconstruction algorithm is much simpler and faster and need not any incremental insertion.
出处
《山东电力高等专科学校学报》
2012年第3期70-74,共5页
Journal of Shandong Electric Power College
