潘荣丽

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

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三角化过程中直接计算点集序列，重建时需要进行点定位、局部插入调整等操作，影响了重建速度。……