摘  要： 三角网生长法具有独特的优势，但将其扩展到三维的研究远远少于逐点插入法、分治法以及二者的合成算法，研究扩展三角网生长法实现三维DT剖分的算法。引入k近邻思想优化了原始算法，时间复杂度可达O（NlogN），且改进对二维、三维算法都有效。通过AE二次开发完成了数据操作、算法实现和二维、三维显示等功能，后续能够较方便地添加和扩展ArcGIS相关功能以及其他数据挖掘算法模块。用两组6个点集数据进行实验分析，网格构建时间对比验证了算法性能。

　　关键词： 三维DT剖分；三角网生长法；k近邻思想；AE

　　空间剖分是实现空间索引与邻近查找的重要途径，与映射法、四叉树/八叉树法以及推进波前法（Advancing Front Technique）等针对离散点集实现的其他剖分方法相比，狄洛尼三角化DT（Delaunay Triangulation）剖分[1]具有数据结构简单、描述能力强大、唯一的、兼具全局和局部最优等特性，因而被广泛运用于地学、计算机图形学和地理信息系统等领域。

　　DT剖分算法方面，目前国内外研究集中在逐点插入法改进、分治法与逐点插入法集成以及分布并行处理等方面[2]。逐点插入法改进一般从初始三角形构建、点定位和局部优化3个方面入手，其中局部优化是决定算法效率的关键，数据量大时优化过程极为耗时。分割合并思想是分治法的核心，子网构建可以采用任意算法（包括逐点插入法与生长法）实现[3]。分布并行处理相当于省去了分治法中向下递归的分割步骤[4]，在海量数据场合更具优势[4-6]。

　　但生长法思路简单、算法设计容易实现、构网精度高、占内存小，生长过程直接生成Delaunay三角形，无需分割、合并、点定位、局部优化等前期和后续操作。近年来，由于其在点集较小时也有较好性能，分布并行方式和分治法结合生长法的研究也开始出现[6-7]。随着计算机硬件性能的改善以及分布并行处理方面的进步，算法设计在时空复杂度方面的约束越来越小，但对生长法原始算法改进点搜索策略[8]以极大提高算法效率也是必要的。

　　相比二维DT剖分已有大量成熟的研究和应用成果，三维DT剖分仍在发展之中，但由于四面体网格具有很多优秀特性，已经引起许多领域的重视[9-10]。现有文献中的研究成果表明，虽然通过扩展3种经典的二维DT剖分算法都可以完成该任务，但在三维情况下集成分治法和逐点插入法、实现二者优势互补的难度远远高于二维情况，而生长法（空间复杂度优于分治法，时间复杂度在一般情况下与逐点插入法持平）思路简单、容易实现的优势更加明显。现有文献中对此研究较少，但采用生长法实现三维DT剖分是合理的选择。

　　本文将针对二维离散点集提出的生长法扩展到三维，通过优化改进提高其效率，并在AE（ArcGIS Engine）开发环境中实现。

1 算法设计

　　1.1 算法基础

　　不同于二维DT剖分得到二维Delaunay三角形网格D-TIN（Delaunay Triangulation Irregular Network），三维DT剖分得到的是三维Delaunay四面体网格D-TEN（Delaunay Tetrahedron Network），它能保存原始数据，有精确表示目标和复杂空间拓扑关系的能力，已有一些基于  D-TIN的邻近研究[11]，这方面的应用潜力还很大。  D-TEN是三维表达的工具，与之对应的算法设计与实现是三维数据处理分析需要解决的重要问题。D-TIN的网格单元三角形由点-线-面的结构构成，D-TEN的网格单元四面体由点-线-面-体的结构构成，其数据结构和数据模型是设计二维、三维DT剖分算法的基础。

　　DT剖分算法的核心内容和关键步骤是Delaunay准则的运用，二维DT剖分算法的Delaunay准则包括“空圆准则”与“最大最小角准则”由二维扩展到三维，就得到三维DT剖分算法的“空球准则”（D-TEN中任一四面体的外接球内无其他点）与“最大最小立体角准则”（重置D-TEN中任何两个相邻四面体的公共面，最小立体角不会增大）。

　　需要注意两点：若不存在4点共圆和5点共球的情况，则点集DT剖分唯一[12]；二维情况下，“空圆准则”与“最大最小角准则”等价[13]，但三维情况下，“空球准则”和“最大最小立体角准则”不等价[14]，由于“空球准则”的实现难度较小，目前实际应用中多被采用。

　　1.2 算法思路

　　生长法构建D-TEN的思路与构建D-TIN类似。参考二维情况是先构建一个起始三角形作为种子，然后以它的边为基准向外生长；所以三维情况则是先构建一个起始四面体作为种子，然后以它的面为基准向外生长。

　　具体步骤为：（1）将点集中距离最近的两点连线作为基线，根据空圆法则搜索第三点，连线成三角形作为基准面；（2）根据空球法则，在基准面的外侧（基准面的顶点按逆时针顺序排列，并把面的法向指向定为面的外侧）找寻第4点来构建四面体，并且使构成四面体4个面的三角形的顶点，从四面体外向里看时总是按逆时针顺序排列，即面的法向都朝外（和基准面重合的面法向恰好和基准面反转）；（3）以四面体的3个新面（除基准面外）作为新的基准面。重复步骤（2）、（3）直至所有的点连线完毕。

　　1.3 优化改进

　　生长法最重要也是最耗时的环节在于以基准线（面）根据空圆（球）准则找寻第3（4）点的过程，原始算法需要遍历点集中所有点，效率很低。1.2节的算法步骤中通过顶点逆时针排序定出线（面）的方向性，据此限定在基准线的右侧（基准面的外侧）搜索点，一定程度上减少了需要遍历的点数，提高了算法效率，但还可以进一步改进。

　　无论是构网前预先分割区域[15]还是构网时限定搜索范围[16]，甚至两种方式结合采用[17-18]，都是通过限定搜索范围来间接限制搜索点数；还可以用“距离最近”来直接限制搜索点数。参考文献[4]用并行方式构建Delaunay三角网，子网构建方法之一采用改进的生长法。生长法第3点搜索实际上是寻找最近点问题，以最近点搜索算法找到最近点作为第3点连接为三角形，但以最近点算法直接代替准则判断有些欠妥。参考文献[19]中也用距离最近的概念来描述算法准则：以所选点与基准线（面）端点构成圆（球）的中心和基准线（面）的距离最近作为选点依据，此时显然不会有其他点在圆（球）内，其实还是空圆（球）准则的变形。

　　Delaunay准则不是简单地直接找距离基准线（面）或其端点最近点就可以代替的，以当前基准找点生成当前三角形（四面体）时不是简单地连接与基准或者其端点距离最近的点就行。只能说距离基准线（面）较近的点对生成三角形（四面体）贡献较大[18]，还需要对这些点进行准则判断。距离最近的思路可取，但应该是距离基准线（面）的端点的“综合距离”最近的点。也就是说，距离基准端点“都比较近”的点才可能是合适点；反过来，合适点肯定在距离基准端点“都比较近”的点中，这个“都比较近”有点难以用数学精确定义，但可以借鉴k近邻思想。找到一个基准线（面）端点的k近邻点集，再在该点集中以准则判断来找到最终合适点，这种做法相当于直接限定搜索点数。由k近邻的含义可知，如果在近邻点集中找到某点满足准则：近邻点集中的其他点都在基线（面）和该点构成的三角形（四面体）的外接圆（球）外，那么对整个点集显然也能满足。

　　1975年，SHAMOS M I等人[20]研究了最近点问题，指出允许预处理时找到点集中加入新点的k个最近点时间下限为logN，并给出了k=1的算法实例和详细论证[21]。因此构网前先对点集排序预处理，以二维为例，可以按先X后Y的规则定义点间大小关系直接用归并排序，也可以用Hash表将空间点映射到一维再进行排序，时间复杂度均为O（NlogN），但会提高算法的空间复杂度。每次搜索先找出基准线（面）的每个端点的k个近邻点，然后在这些近邻点中按准则找点，k取值从1开始直到找到合适点。找近邻点集时间复杂度为O（logN），在数量很少的近邻点中找满足准则的点时间复杂度为O（1）。所以，每次找第3（4）点的时间复杂度为O（logN），算法总时间复杂度为O（NlogN）。SHAMOS M I和HOEY D指出对N个点构建Delaunay三角网时间复杂度至少为O（NlogN），生长法原始算法时间复杂度最坏情况为   O（N2），最好情况为O（N3/2）[20]，经过优化，算法时间复杂度可达到该下限。

2 程序实现

　　综合考虑算法实现的难度以及与已经实现的三维地理空间数据分析功能的兼容性，本文用C#在Visual Studio 2012中开发AE程序实现生长法用于二维和三维DT剖分，包括D-TIN、D-TEN的网格构建和图形绘制，其中三维图形绘制通过ArcGIS 3D分析扩展部分的核心模块ArcScene[22]实现。开发环境为：联想G530笔记本电脑，主频2.13 GHz的Intel酷睿双核CPU，2 GB内存，250 GB硬盘，Windows 7系统。D-TIN的2维、2.5维及D-TEN的3维网格图形如图1、图2所示。

3 实验分析

　　由于D-TIN、D-TEN数据模型的不同，采用两组不同性质的空间离散点集数据分别测试D-TIN和D-TEN的构建与绘制，每组3个点集间具有同样性质但是数据规模不同。5次重复实验花费时间取平均值，构建时间与绘制时间分开统计，因为主要是为了对比构建时间。表1、表2分别为D-TIN、D-TIN的构建和绘制时间。

　　随着点数的成倍增加，构建时间接近线性对数增长，偏差约为5%~6%，这里没有列出做过的大于10万数据量的实验，但小数据量也能得出这一增长规律，说明二三维DT剖分算法复杂度接近O（NlogN），对二三维算法的改进都有效，算法高效生成网格的性能得到了验证。绘制方式为一次性绘制整个网格图形，但网格的绘制速度仍然远远小于构建速度，三维网格绘制更慢，说明AE在三维可视化图形快速绘制方面还有待改进。

　　二维情况下，生长法的空间复杂度优于分治法，时间复杂度在一般情况下与逐点插入法持平，思路简明、算法容易设计与实现是其主要优势。三维情况下，集成分治法和逐点插入法、实现二者优势互补的难度远远高于二维情况，而生长法简单易实现等优势更加明显。

　　本文研究表明，将生长法扩展到三维用于三维DT剖分，经改进优化后算法复杂度可降低至O（NlogN），已经具备处理大数据量点集的能力。此外，计算机性能的不断改善，结合分治法或通过并行处理，生长法生成 D-TEN完全能够满足处理海量数据的需求。

　　选择ArcEngine开发程序实现算法，可以方便地添加和扩展ArcGIS的相关功能，如三维空间查询、分析和运算，促进三维DT剖分的理论研究和实际应用相结合。D-TEN能表示复杂的空间拓扑关系，往往在与其他领域的应用结合中很有作用，比如由聚类等传统数据挖掘算法发展出来空间聚类、时空聚类等。接下来的工作是根据三维DT剖分得到的点间拓扑关系编写聚类算法，进而对空间离散点进行三维层次上的聚类分析等。

　　参考文献

　　[1] 陈定造.空间离散点集Delaunay三角剖分的算法优化及实现[D].广州：广东工业大学，2008.

　　[2] 余杰，吕品，郑昌文.Delaunay三角网构建方法比较研究[J].中国图像图形学报，2010，15（8）：1158-1167.

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

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

　　[5] BLANDFORD D K， BLELLOCH E G， KADOW C. Engineering a compact parallel Delaunay algorithm in 3D[C].Proceedings of the 22th ACM Symposium on Computational Geometry， New York： ACM， 2006：292-300.

　　[6] 袁舒，杨烜.基于Delaunay三角网生长法的并行图像插值方法[J].计算机应用与软件，2012，29（3）：62-68.

　　[7] 向传杰，朱玉文.一种高效的Delaunay三角网合并生成技术[J].计算机应用，2002，22（11）：34-36，39.

　　[8] 吴佳奇，徐爱功.Delaunay三角网生长法的一种改进方法[J].测绘科学，2012，37（2）：103-104，187.

　　[9] Li Yanbo， Zhang Tianchi， Zhang Jing， et al. Almost-Good delaunay tetrahedron modeling for surgery simulation[C]. Proceedings of 2010 Second International Asia Symposium on Intelligent Interaction and Affective Computing and 2010 Second International Conference on Innovation Management （ASIA-ICIM 2010）， Wuhan：ASIA-ICIM， 2010：611-621.

　　[10] 李丽.三维空间Delaunay三角剖分算法的研究及应用[D].大连：大连海事大学，2010.

　　[11] 闫超德，赵艳坤，郭王，等.基于Delaunay三角网的邻近区域测度及其应用[J].地理与地理信息科学，2013，29（2）：125-126.

　　[12] CAVENDISH J C， FIELD D A， FREY W H. An approach to automatic three-dimensional finite element mesh generation[J]. International Journal for Numerical Methods in Engineering，1985，21（2）：329-347.

　　[13] LEE D T， SCHACHTER B J. Two algorithms for constructing a delaunay triangulation[J]. International Journal of Computer and Information Sciences， 1980，9（3）：219-242.

　　[14] 崔凌国.约束Delaunay四面体剖分及其相关算法的研究[D].西安：西北工业大学，2006.

　　[15] 闫超德，郭王，白建军，等．最大空圆约束下的最邻近计算方法[J]．测绘科学，2012，37（6）：157-159.

　　[16] 韦文杰，周振红，彭记永，等.一种改进的Delaunay三角网生长算法[J].气象与环境科学，2008，31（2）：80-82.

　　[17] 王会然.一种生长法快速构造三角网的算法研究[J].城市勘测，2010（2）：146-149.

　　[18] 刘刚，李永树，张永舰.基于不规则三角网构建的网格生长算法[J].计算机工程，2011，37（12）：56-58，61.

　　[19] 郭际元，龚君芳.由三维离散数据生成四面体格网算法研究[J].地球科学-中国地质大学学报，2002，27（3）：271-273.

　　[20] SHAMOS M I， HOEY D. Closest-point problems[C]. Proceedings of the 16th Annual Symposium on the Foundations of Computer Science（FOCS），1975：151-162.

　　[21] SHAMOS M I. Geometric complexity[C]. Proceedings of the Seventh ACM Symposium on the Theory of Computing，1975.

　　[22] 王晓利，马大喜.基于ArcScene的遥感影像三维可视化技术研究与应用[J].计算机与现代化，2012（6）：54-57.