Delaunay三角剖分的快速重建算法

潘荣丽

山东省劳动厅服务技工学校 山东 济南

0 引言

平面点集的Delaunay 三角剖分是计算几何的一个重要问题，有着广泛的应用背景，在虚拟现实、地理信息系统（GIS）等许多方面都有着很重要的意义。 实际应用中经常包含几百万个点和三角形， 必须进行数据压缩才能适应现有的网络传输技术， 特别是进行实时处理时更需要压缩技术的支持。 在网络环境下把模型从服务器传送到客户端，一般有两种方法：1）只传送点集，在客户端对点集进行Delaunay三角化。 这一般需要O(nlogn)的时间。这方面的研究主要集中在提高Delaunay三角剖分算法的时间复杂性上。2） 传送点集和连接关系。 这样传输数据量大，因此需要进行压缩处理，以减少传输时间。这方面的研究主要集中在对点集和三角网格连接关系进行压缩［2-5］。

最近，Snoeyink 和van Kreveld 提出了第三种可能的方法［6］：找出点集的一种特殊排序，按这种序列传输点集，在O(n)的时间内重建Delaunay三角剖分。 具体算法是首先根据已经生成的Delaunay三角剖分，分成O(nlogn)个阶段计算点集序列，在每个阶段删除一个独立点集，对产生的空洞进行三角化， 按DFS或BFS遍历新产生的三角剖分，输出点集序列。 整个计算过程可以在O(n)的时间内完成。重建算法与计算点集序列的算法相对应，也分成O(nlogn)个阶段，在每个阶段进行点定位、局部插入调整，重建过程也可以在O（n）的时间内完成。 1999年Christian Sohler 对算法进行了改进。

上述计算点集序列和重建算法都比较复杂，而且不能在Delaunay三角化过程中直接计算点集序列，重建时需要进行点定位、局部插入调整等操作，影响了重建速度。 我们提出了一种新的Delaunay三角剖分的快速重建算法，在基于均匀网格的Delaunay三角化过程中，直接生成点集序列。这种方法也可以应用到其他Delaunay三角剖分方法的输出结果上，在O（n）的时间内生成点集序列。 重建时不需要插入调整就可以在O（n）的时间内生成Delaunay三角剖分。

1 计算点集序列算法

基于均匀网格的Delaunay三角化算法运算速度非常快，具有近似线性的时间复杂性［10］，是一种比较成熟、稳定、实际的Delaunay三角化算法。 这个算法的主要步骤如下：

1）预处理数据

把数据点分布的平面区域划分成网格，使网格单元数和点数大致相同。 根据点的坐标值，把所有的点放进相应的网格单元中。在靠近中间的网格单元中找到一个初始点，然后找一个距离初始点最近的点，把这两个顶点填加到一个链表Q中

2）找一个三角形

取链表的头结点Qs、 链表的尾结点Qe形成一条有向边，方向为从Qs到Qe。在这条边的右边寻找与这条边的两个端点角度最大的点。 然后扫描通过这条边的两个端点与该点所形成的圆的区域，如果圆内存在一个点，用那个点重新形成一个圆，再扫描直到圆内没有点为止。 这样就找到一个Delaunay三角形。

3）连接三角形

按“右接触”、“左接触”、“洞”、“边界边”等情况分别进行处理、调整链表。

4）重复步骤（2）、（3），直到链表中的点全为边界点为止，结束三角化过程。

下面对基于均匀网格的Delaunay三角化算法进行修改，在生成过程中输出点集序列。

算法1

（1） 找到靠近平面区域中间的初始点P1以及距离P1最近的点P2，构成初始边P1P2，把这两个顶点填加到一个链表Q中：输出P1、P2

（2）取链表的头结点Qs、链表的尾结点Qe，形成一条有向边，方向为从Qs到Qe。 在QsQe的右边寻找与QsQe两个端点角度最大的点。 然后扫描通过Qs、Q e与该点所形成的圆的区域，如果圆内存在一个点，用那个点重新形成一个圆，再扫描直到圆内没有点为止。 这样就找到一个Delaunay三角形的第三点P，并按“右接触”、“左接触”、“洞”、“边界边”等情况分别进行处理、调整链表。

①如果QsQe属于“边界边”的情况（不存在P），则把Qs移到Q的末尾，输出标志F3

②如果P属于“右接触”的情况（P已经出现过，且等于Qs.next），则删除Qs，输出标志F1

③如果P属于“左接触”的情况（P已经出现过，且等于Qe.previous），则删除Qe，输出标志F2

④如果P属于“洞”的情况（P已经出现过，但不等于Qs.next和Qe.previous），则把Qs移到Q的末尾，输出标志F3

⑤否则（P没有出现过），把P追加到队列Q中，输出P

（3）重复（2），直到链表中结点全为边界点为止。

例如：

图1 测试数据点

图2 初始点P1、初始边P1P2，输出P1、P2

图3 第一个三角形P1P2P3 ，输出P3

图4 第二个三角形P1P3P4 ，输出P4

图5 第五个三角形P1P6P7 ，输出P7

图6 “右接触”的情况，输出标志F1

图7 “洞”的情况，输出标志F3

图8 “右接触”的情况，输出标志F1

图9 “左接触”的情况，则输出标志F2

图10 “边界边”的情况，输出标志F3

图11 三角形P10P9P18 ，输出P18

图12 三角化结束

根据上述算法，在生成过程中输出的点集序列为：P1、P2、P3、P4、P5、P6、P7、F1、F1、P8、P9、P10、F1、P11、P12、P13、P14、F1、P15、P16、F1、F3、F1、F2、P17、F3、F3、P18、F1、P19、P20、F1、F3、F3、F1、F2、F3、F1、F3、F1、F3

显而易见，增加的标志大部分位于点集序列的最后（边界边的情况）。 点越多，点集序列中出现的标志所占比例就越小。

上述算法也可以推广到其他Delaunay三角剖分方法的输出结果，输出点集序列。

算法2

（1） 找到靠近平面区域中间的初始点P1以及初始边P1P2，把这两个顶点填加到一个链表Q中：输出P1、P2

（2） 取链表的头结点Qs、链表的尾结点Qe，形成一条有向边，方向为从Qs到Qe。 寻找QsQe右三角形［12］的第三点P，并按“右接触”、“左接触”、“洞”、“边界边”等情况分别进行处理、调整链表。

①如果QsQe属于“边界边”的情况（不存在P），则把Qs移到Q的末尾，输出标志F3

②如果P属于“右接触”的情况（P已经出现过，且等于Qs.next），则删除Qs，输出标志F1

③如果P属于“左接触”的情况（P已经出现过，且等于Qe.previous），则删除Qe，输出标志F2

④如果P属于“洞”的情况（P已经出现过，但不等于Qs.next和Qe.previous），则把Qs移到Q的末尾，输出标志F3

⑤否则（P没有出现过），把P追加到队列Q中，输出P

（3） 重复（2），直到链表中结点全为边界点为止。

在算法1和算法2中都考虑了所有可能出现的五种情况，因此算法是完备。

2 快速重建算法

在重建Delaunay三角化算法中，根据上面生成的点集序列在重建过程中动态维护一个队列Q。

算法3

（1） 初始队列为空

（2） 从点集序列中取第一个点P1和第一个点P2，放入队列Q中，连接边P1P2

（3） 从点集序列中取下一个点P3

①如果P3为标志F1， 则Qs、Qe、P3构成一个三角形，删除队列Q的头结点Qs，连接队列Q新的头结点Qs和尾结点Qe，形成一条边

②如果P3为标志F2， 则Qs、Qe、P3构成一个三角形，删除队列Q的尾结点Qe，连接队列Q的头结点和新的尾结点，形成一条边

③如果P3为标志F3， 则把队列Q的头结点移动到队列Q的末尾

④否则，Qs、Qe、P3构成一个三角形，分别连接Qs和P3，Qe和P3，形成两条边，把P3追加到队列Q中。

（4） 重复（3），直到把点集序列的所有点处理完毕。

3 结论

算法2和算法3具有线性时间复杂性， 而算法1具有近似线性的时间复杂性。这种重建方法实现了三角网格连接关系的高效压缩 （只增加了三种标志），在基于均匀网格的Delaunay三角化过程中，直接生成点集序列，还可以应用于其他Delaunay三角剖分方法的输出结果，并可结合对几何信息(如坐标、颜色等)的其它压缩算法如Huffman编码等，算法简单、使用。

如何利用文中提出的算法对三维点集的Delaunay三角剖分［10］进行重建，是作者下一步研究的方向之一。

［1］武晓波， 王世新， 肖春生.Delaunay三角网的生成算法研究［J］. 测绘学报，1999， 28（1）：28-35.

［2］M. Deering. Geometry Compression. Computer Graphics（Proc. SIGGRAPH），1995：13-20.

［3］G. Taubin， J. Rossignac. Geometric Compression through topological surgery. ACM Trans. on Graphics，1998，17（2）：84-115.

［4］H. Hoppe. Progressive Meshes. Proc. SIGGRAPH ’96，pages 99-108. ACMSIGGRAPH， 1996.

［5］Stefan Gumhold， W. Stra?er： Real Time Compression of Triangle Mesh Connectivity.SIGGRAPH ’98： 133-140.

［6］J. Snoeyink， M. van Kreveld. Linear-time reconstruction of Delaunay triangulations with applications， European Symposium on Algorithms， 1997.

［7］Christian Sohler， Fast Reconstruction of Delaunay Triangulations， Proceedings of the 11th Canadian Conference on Computational Geometry，1999：142-145.

［8］Tsung-Pao Fang， Les A. piegl. Delaunay triangulation using a uniform grid ［J］. IEEE Computer Graphics and Applications 1993，13（3）， 36-47.

［9］潘荣江，屠长河等.基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用 ［J］. 中国图象图形学报，2002，7A（5）：495-500.

［10］Tsung-Pao Fang， Les A. piegl. Delaunay triangulation in three dimensions， IEEE Computer Graphics and Applications， September 1995,15（5）.