基于格网和方向法索引的Delaunay三角网生成算法

姜志伟，王山东，王伶俐，毛泽红

（1.河海大学 地球科学与工程学院，江苏 南京210098；2.徐州市贾汪区国土资源局，江苏 徐州221000）

1 逐点插入法的点定位问题

近年来有许多学者对Delaunay三角网的构建算法进行了研究，基于离散点的三角网的构建算法目前较为常用的有生长法［1］、分治法［2］和逐点插入［3］法及两种算法的结合。逐点插入法构建Delaunay三角网的思想是把集中的点依次插入一个已知的三角网中，每插入一个点都会构建新的三角形，对新生成的三角形需要进行局部优化［4］，最后使得三角网符合Delaunay规则。逐点插入法［5］思想简单、灵活，这种算法比起生长法效率高很多、比起分治法占用更少的内存且容易实现。但是这种算法构网时，当随着插入的点数增加时，三角形链表中的三角形也会成倍增加。算法耗时很多都浪费在目标三角形的查找上，即点定位。一般将在三角网中查找包含插入点的三角形算法称为点定位问题［6］。

常见的对逐点插入法改进的算法中，最终目的都是对点定位的改进。如：李小秋等人在Delaunay三角网关键技术探讨中提出使用方向法搜索技术进行快速定位［7］。赵岩等人选择适当的格网大小对三角网进行存储从而减小点定位时遍历次数［8］。方向法利用三角网本身的拓扑关系进行点定位，可以有效减少判断点是否在三角形内的次数。然而，当三角网过多时，还是会进行许多拓扑关系的运算。格网对三角形存储的目的同样是减少判断点是否在三角形内的次数。然而，当单个网格过大时，遍历格网中的三角形也需要大量的耗时；单个格网过小时，格网数量会很大，对三角网在格网中的存储、内存的占用都会有影响。

本文在结合以上两种方法的优点的基础上，实现了一种新的基于格网的三角网生成。首先，在三角网的数据结构上做了改善，只利用拓扑关系存储三角网。其次，在虚拟格网上加上辅助三角形，作为方向法点定位的起始三角形。最后，方向法点定位中使用跨立实验和快速排斥实验结合的方法。

2 虚拟格网索引建立和方向法算法描述

2.1 虚拟格网方向法构建三角网概述

常见的逐点插入法构建三角网时，对于点定位的算法是遍历三角形链表，找出点所在的三角形。这种算法对于大量点插入时，三角形的数量会随着点插入的数量的增加而增加。大量点插入时，效率变得很低。虚拟格网是将点集分块管理，格网中心有一个辅助元三角形，元三角形的外接圆内不包含点集中的任何点。当点插入的时候，根据点坐标确定点属于哪个格网，再用格网中的元三角形作为起始三角形，利用方向法确定目标三角形。通过以上两个步骤寻找包含插入点的三角形，提高点定位的效率。

2.2 虚拟格网索引的建立

虚拟格网是把点数据分成长方形的区域，当插入点到三角网中时，通过点坐标计算出格网的数组位置。每个格网中都有一个处于中心位置的元三角形，如图1所示。

图1 2×2虚拟格网

虚拟格网的元三角形是在格网中央包含格网中心点的辅助三角形。在点定位时都是以元三角形作为起始三角形。元三角形的外接圆内中不包含任何点数据。在实际程序中，如果计算精度不是很高时，可以选择合适大小的元三角形，先移除少量的元三角形外接圆内的点。

虚拟格网索引的建立原则为：

1）所有三角网和点的数据均包含在格网内。

2）格网中三角形不能太多，格网不能太大。如果三角形太多，在格网中用方向法检索三角形效率会变低。

3）格网中三角形不能太少，格网不能太小。如果三角形太少，建立过多的格网，处理元三角形会占用大量资源和算法耗时。且在格网中元三角形删除时耗时会更多。

2.3 方向法点定位算法简述

2.3.1 跨立实验

跨立实验［9］和快速排斥实验结合可以有效快速地判断出两条线段的位置关系。在格网内索引目标三角形点定位时会用到判断三角形边的相交情况，从而判断三角形的走向。快速排斥法是判断线段是否相交的必要条件。根据以两条线段为对角线的两个矩形是否相交判断两条线段相交的可能性。如果矩形不相交则两条线段肯定不相交，如果矩形相交再进行跨立实验，如图2（a）所示。

图2 快速排斥实验和跨立实验

跨立实验原理是：如果一个线段跨立另一个线段，则另一线段的一个顶点与这条线段的两个顶点连成的两个矢量分别与原线段的矢量叉积符号相反，如图2（b）所示。

2.3.2 跨立实验判断线段和三角形的关系

如图4所示，根据线段和三角形的关系可以分为9种关系。用跨立实验判断线段的顶点和三角形的顶点是否是同一点可以准确判断出线段和三角形的位置关系。实际在程序中不需要对这9种结果一一做出判断。在这9种结果中只有上面3个是线穿越三角形，其他6种线没有穿越三角形，即要么目标点在三角形内，要么目标点在三角形边或顶点上。所以，可以根据跨立实验简单地判断两种结果：①三角形被线段穿越；②三角形没有被三角形穿越。

图3 线段之间的关系

图4 线段和三角形的关系

2.3.3 方向法点定位

如图5（a）所示，A点所在的三角形是起始元三角形，插入点是P点。在起始元三角形中的格网中心点作为起始点（A点），使用跨立试验得出起始三角形的一条边和线段AP相交，作为起始方向边。根据起始方向边得出第一个方向三角形。再利用跨立实验得出下一个方向边和方向三角形。

当线段AP可能出现如图5（b）和图5（c）所示的情况时，没有方向边和线段AP相交时取积极跨立AP的边作为方向边。

当线段AP穿越方向边进入方向三角形时，如果没有与三角形的另两个边出现跨立或积极跨立，则出现了线段和三角形关系中的第②种关系即点在三角形内或点在三角形边或顶点上。此时点定位完成。

2.4 算法流程

2.4.1 算法概述

1）根据点的密度和点边界划分合适大小的格网，并计算格网编号、生成格网数组、格网元三角形。

2）用外边界的格网4个角点和各元三角形的点建立初始三角网。

图5 方向法索引

3）找出初始三角形的元三角形的地址，记录在格网数组里。

4）插入其余的点，在格网内使用方向法索引到点定位的三角形，与一般插入法算法一样构建三角网。

5）对插入点的所有影响三角形进行局部优化。

6）重复上面的4）和5），直到所有的点插入完毕。

7）移除所有的辅助点。

2.4.2 算法流程

算法流程见图6。

图6 算法流程

3 实验结果

本文的算法要用配置为：CPU：E2160 1.80GHZ，内存2G，基于 Windows XP操作系统.net框架实现Delaunay三角网的构建。采用一般的逐点插入法和本文的基于虚拟格网的点插入法进行比较如表1所示。

从表1中测试的数据可以看出：利用虚拟格网法构建三角网的效率较一般的插入法效率大大提高，且虚拟格网构建三角网效率和点的个数几乎成线性关系。从表1中分析得出：当密度大时，格网分得越多，效果越理想。但是密度小时，格网太多却效率差。

表1 两种算法结果比较

15 000个点构建出的三角网效果如图7所示。

图7 两种方法生成的三角网

4 结束语

本文提出一种对逐点插入法构建三角网的改进算法。通过虚拟格网管理每一个插入点，根据格网内的元三角形作为起始三角形进行方向法索引，较大程度上缩小了搜索目标三角形的范围。方向法索引很巧妙地利用三角网的联系性和三角网元素之间的拓扑关系，大量提高点定位的速度。实验证明该算法效果理想。但是使用该算法时需要注意网格的大小不是越小越好，网格过小时，初始三角网的构建、三角网生成后辅助点的删除会影响构建效率，同时内存使用也会增大。在构建带约束条件的三角网时，同样可以根据本文中的点定位方法，快速找到约束线段的影响三角形。

［1］魏向辉，夏春林，鲁庆伟.一种基于凸包的Delaunay三角网算法设计［J］.测绘科学，2010，35（5）：152-153.

［2］SHAMOS M，HOEY D.Closet-point problem［A］.Processing of the 16th Annual Symposium on Foundations of Computer Science［C］.1975：151-162.

［3］LAWSON C L.Software for C1surface interpolation［A］.Mathematical SoftwareⅢ［C］.New York：Academic Press，1977：161-194.

［4］俞亚磊，罗永龙，郭良敏，等.Delaunay三角网中任意约束线段嵌入的算法［J］.测绘科学，2013，38（4）：61-63.

［5］邵春丽，胡鹏，黄承义，等.Delaunay三角网的算法详述及其应用发展前景［J］.测绘科学，2004，29（6）：68-70.

［6］陈定造，林奕新，刘东峰.三维Delaunay三角剖分快速点定位算法研究［J］.计算机工程与科学，2009，31（5）：79-81.

［7］李小秋，许民献，尹志勇.Delaunay三角网关键技术探讨［J］.测绘工程，2011，20（6）：61-63.

［8］赵岩，张子平.一种动态构建Delaunay三角网的算法［J］.测绘工程，2008，17（3）：24-27.

［9］吴立新，史文中.地理信息系统原理与算法［M］.北京：科学出版社，2003.

［10］LAWSON C L.Generation of a triangular grid with application to contour plotting［A］.In：Technical Memorandum［C］.Institute of Technology，Jet Pollution Laboratory，California，1972：299.