Delaunay三角网的并行构建和更新

崔水军 尹文亭

摘 要：文章提出一种Delaunay三角网并行构建和更新算法。该算法中先将点数据进行格网划分，然后将每块区域作为一个工作单元进行构网，当相邻区域的三角网构建完毕，就将相邻区域进行合并，最终生成一个完整的三角网。

关键词：Delaunay三角网；并行；动态更新；加速比

引言

随着测量技术的发展和新型测量设备的出现，空间数据的获取变得更加容易和快捷，与此同时，数据量也呈爆炸性的增长。如何利用这些海量的空间数据实现数字地面模型DTM的高效构建是当前空间分析及应用领域亟需解决的问题之一。Delaunay三角网以其唯一性、空圆性、能以不同分辨率表达地形、适合各种分布的数据等诸多优点而被广泛地应用于DTM建模中。长久以来，国内外学者对Delaunay三角网的构建提出了多种算法[1-3]。这些算法按实现过程大致可以分为三类：逐点插入法、分治法和扫描线法。陈楚江等[4]提出了实现三角网局部更新的方法。陈少勤等[5]提出利用多源数据实现不规则三角网的动态更新。但这些算法都是基于串行程序实现，不支持点并行的插入和删除。随着多核计算机的普及，并行为解决大数据量的不规则三角网（TIN）构建和更新提供了新的思路。不少学者也对此做了研究，李坚等[6]提出将分治算法与流数据处理方法相结合，利用多核处理器平台进行并行运算。张真[7]提出一种适用于并行计算的归并构网方法。这些算法满足于Delaunay三角网的并行构建，但不适用于三角网的并行动态更新。因为在这些算法在开始之前，点集必须是确定的，而三角网更新时，被插入（删除）点是不确定的。文章提出一种单机多核环境下Delaunay三角网并行构建算法，该算法将数据进行格网划分，每一个数据块作为一个工作单元。同时为解决内存共享带来的问题，可以为各工作单元分配独立的内存空间，工作单元之间相对独立，因此可以很好的实现三角网的并行构建和更新。

并行算法采用数据分块[8]的思想，首先将点数据按给定阈值（实验中发现阈值选择受实验环境影响）进行格网划分，每一个数据块形成一个独立的工作单元。每一个工作单元只负责所属区域内三角网的构建更新。利用计算机单机多核的优势，可以同时将多个工作单元分配给计算机进行处理。最后将相邻的区域进行合并，最终完成三角网的构建。每一个工作单元所负责的工作主要有三方面：初始三角网的构建、点的插入和删除，下面将分别阐述。

1 初始三角网构建

主线程对队列中的所用点进行扫描，如果点位于某一个工作单元负责的区域，则将点移动到该工作单元的私有队列中。工作单元根据负责区域的四个角点坐标形成两个初始三角形，然后从自己的私有队列中取点进行插入构网。主要步骤如下：（1）先找到包含点集中所有点的初始三角形，即将数据块的边界线向外扩大某个值d，然后连接任意一条对角线，形成两个超三角形，并对其进行标号；（2）取点集中的任意一点v，查找v点所在的三角形，如果v在三角形内则连接v和三角形的三个顶点，如果点v在三角形边上，则连接该边相对的一个或两个顶点，如果该点与三角形顶点重合则放弃该点；（3）调用Lop优化算法，判断点的影响区域，对局部三角网进行更新；（4）重复（2）到（3）步，直到所有点插入三角网；（5）删除包含超三角形顶点的所有三角形，算法结束。

2 点的插入或删除

对生成的初始三角网进行更新，主要是通过插入和删除点来完成。对于需要插入的点集P，主线程首先对其进行扫描，将点分配到所属区域的私有队列P1、P2、P3…中。然后将工作单元分配到各个处理器上进行执行。单点插入过程主要步骤如下：（1）找到包含插入点v的三角形t；（2）检索所有与t关联的三角形，找到外接圆中包含点v的三角形集D （v）；（3）D （v）的外边界相连形成一个多边形P（v）；（4）将P（v）内的三角形边删除；（5）连接P（v）的顶点和v形成新的Delaunay三角网D （v）；（6）用D （v）取代D （v）形成新的Delaunay三角网，完成一点插入。删除点时只需要找到对应的点，然后将与之关联的点重新構造三角网即可。

3 内存管理

在多线程程序中，多个线程同时对内存进行访问，在创建（删除）三角形或点时，每一个线程都需要调用内核进行内存的分配（释放）。这时会因为存在大量的锁竞争而花费很高比例的时间，这对于追求高效率的并行目的是不符的。为了避免这种情况的发生，可以为每一个线程分配独立的内存空间，线程在其中创建数据块，如果数据被删除，则把它还给自己的内存池。当内存池中空间不足时，线程才会调用内核申请新的内存块。

4 实验和分析

由于点集中数据点的分布状态对一个算法的速度和精度都有很大的影响，所以我们采用三种典型的数据分布对算法进行测试，分别为：线性分布、标准分布和均匀分布。

实验环境为6核12线程Intel Core i7 4930k CUP（3.4GHz）、16G内存。分别将15M不同分布状态的点数据在多个线程上运行，测试结果如表1所示。用加速比来衡量并行程序的性能和效果。

表1 不同情况下运行时间（秒）

结果表明并行算法能很大的提高构网的速度，且并行数越多，速度越快。分布状态不同的数据对于串行算法执行时间影响更大，而对于并行算法，随着并行数增加，这种影响就越小。这也说明并行算法对于复杂地形的数据有很好的适应性。

5 结束语

Delaunay三角网对DTM模型建立和分析的一种重要手段。文章针对海量数据并行构建三角网的要求，提出一种基于数据分块的并行构网方法。该方法构网前不需要对元数据进行删重、排序等预处理，实现点的并行插入和删除，而且对不同分布状态的数据有很好的适应性。由于算法可以动态的对三角网进行更新，因此可以方便的对模型进行实时编辑，并用于工程计算和分析，如土石方量计算、建立DTM模型、等高线绘制等。

参考文献

[1]芮一康，王结臣.Delaunay三角网构网的分治扫描线算法[J].测绘学报，2007，36（3）：358-362.

[2]袁正午，侯林，彭军还.点集收集分配的Delaunay三角网快速生成算法及实现[J].测绘科学，2011，36（5）：223-225.

[3]谭仁春，杜清运，杨品福，等.地形建模中不规则三角网构建的优化算法研究[J].武汉大学学报·信息科学版，2006，31（5）：436-439.

[4]陈楚江，王德峰.海量数据CDT快速建立及其实时更新[J].测绘学报，2002，31（3）：262-265.

[5]陈少勤，张骏骁，陈捷，等.地形特征约束的不规则三角网动态更新方法[J].地理信息世界，2014，21（4）：71-75.

[6]李坚，李德仁，邵振峰.一种并行计算的流数据Delaunay构网算法[J].武汉大学学报·信息科学版，2013，38（7）：794-798.

[7]张真.海量数据Delaunay三角网的并行构建算法[J].计算机工程与科学，2013，35（4）：1-7.

[8]李小丽，陈花竹.基于格网划分的Delaunay三角剖分算法研究[J].计算机与数字工程，2011（7）：57-59.

作者简介：崔水军（1987-），男，硕士研究生，主要从事地理信息系统应用开发等方面研究。