对于基于区域分解的三角网剖分算法，如果子网组合成整体时不需要复杂的界面缝合操作，仅需简单的合并，则称为非耦合区域分解模式算法^[13]。在Delaunay三角网的剖分过程中，若存在由最终三角形构成的三角形墙DW_i(1＜i≤SN)，将待剖分点集DP切割为点集DP_j (1＜j≤BN)，则点集DP_j可独立剖分为Delaunay三角网DT_j；并且对于DT_j，删除其边界错误三角形得到三角网DDT_j，则所有子网(DDT_j、DW_i)简单合并即为DP最终构建的三角网DPT，即$\sum\nolimits_{i = 1}^{SN} {D{W_i}} + \sum\nolimits_{j = 1}^{BN} {DD{T_j}} = DPT$。其中，SN为分解DP所需的三角形墙条数; BN为DP分解的块数。

本文通过对数据切块并剖分，避免分治算法的深度递归，并改善算法的整体时间复杂度；同时引入流计算进一步提高内存的利用率；然后运用切块边界错误三角形删除算法和非耦合区域分解模式性质，实现各子网简单合并和最终三角网的生成。其算法具体步骤如下。

1) 点云粗排序。根据点云数量，确定数据读取次数m，沿X(Y)方向将点云划分到m个数据集中。

2) 数据读入。按顺序读入一个数据集V，并进行等格网划分。若非第一次读取数据，与上一次读入数据集的最后一纵块合并拼接。

3) 纵向切块。如图 1所示，根据确定的切块大小与形状，利用切块方法，在V上切下一个纵块Ⅰ。点云的分割以分界线为界，分界线为图 1中虚线。

图  1  切块剖分算法示意图

Figure 1.  Schematic Diagram of the Cutting Block Algorithm

4) 横向切块。根据确定的切块大小与形状，利用切块方法，在Ⅰ上横向切下一个切块1。

5) 切块剖分和边界错误三角形删除。对切块1利用分治算法进行剖分，并利用切块边界三角形删除算法删除边界错误三角形，输出存储正确的三角形，释放三角形占用内存。重复步骤4)~步骤5)，直至纵块Ⅰ完成剖分。

6) 如果m次数据已经全部读入，则重复步骤3)~步骤6)，直至V剖分完成，结束算法；如果m次数据未全部读入，重复步骤3)~步骤6)，直至余下最后一个纵块，以便于下一次读入的数据合并，释放点云V与格网划分占用内存，执行步骤2)~步骤6)。

7) 子网合并。将各切块三角网与各条DeWall简单相加即为最终构建的三角网。

分析图 1中的分界线，在切块分割时每一个点仅被分到一个切块中，各切块之间交集为零，且并集为DP，即$\sum\nolimits_{j = 1}^{BN} {D{P_j}} = DP$。通过切块边界错误三角形删除算法可实现切块三角网与DeWall的无缝无覆盖拼接，该算法是一个非耦合区域分解模式算法。下面对算法中使用的关键方法与技术作详细阐述。

假设点云分布均匀，一个切块的点数为δ，切块宽为w，长为δ/w。PR约为2(w+δ/w)/2δ≥2δ^1/2/δ，当w=δ^1/2时，即切块为正方形时，PR最小，PR=2δ^1/2/δ；同时可知，切块越大，PR越小，但切块越大，递归对计算机内存要求越高，普通PC机利用分治算法可以实现十万至百万级点云的三角网剖分。

将等格网划分与动态三角网生长算法结合提高Delaunay三角形第三点的查找效率。对于待扩展的基线BC，动态确定第三点过程如图 2。

图  2  动态搜索第三点

Figure 2.  Finding the Third Point Dynamically

1) 作BC的垂直平分线，M为垂直平分线与BC的交点。相对于线段BC，在与A点异侧的垂直平分线上取一点O，令MO=R。

2) 以O为圆心，过BC两点作圆。相对于线段BC，在与A点异侧的圆内，以格网为索引，寻找符合Delaunay三角网准则的第三点。

3) 如果在圆内有符合条件的第三点，则以BC为基线的三角形构建完成; 否则，令R=R+△R。

4) 迭代步骤2)~步骤3)，直至寻找到符合条件的第三点。

Cignoni^[14]提出了DeWall构建算法，并基于该算法实现了Delaunay三角网剖分，但其是一个递归的过程，不适合较大数据三角网的构建。本文对文献[14]中的图进行简化(图 3)，并对DeWall构建算法中的DeWall结束判断部分进行了改进，使其适合海量数据处理。

图  3  DeWall构建

Figure 3.  Construction of DeWall

1) 分界线的确定。依据切块大小与形状，在切割区选择一点P₁和其最近点P₂，经过P₁P₂之间一点作X(Y)轴的垂线，作为分界线α(图 3中虚线)。

2) DeWall构建。以P₁P₂为初始基线，利用第三点查找的动态实现方法查找第三点P₃，以穿过α的新边(P₂P₃)作为新基线，查找第三点P₄，再以穿过α的新边(P₃P₄)作为新基线，直至这一条DeWall构建完成。

3) DeWall结束判断。文献[14]利用数据集凸包作为结束标志，但较大数据构建凸包消耗较大。本文算法通过添加辅助点，作为DeWall在数据集边界的结束标志。具体方法为：对于各行，首先从左端开始遍历，若格网G(i, j)有点，则在格网G(i-1, j)中心添加辅助点；然后从右端遍历，若G(i, j)有点，则在格网G(i+1, j)中心添加辅助点。对于各列采用类似方法。最后删除以辅助点为顶点的三角形。该方法不仅简单高效，同时可以避免边界狭长三角形的生成，并对不规则形状点集生成的三角网边界具有一定的约束作用。在数据集的内部，以已构建的DeWall关联的点作为结束标志。

如图 1，每一个待剖分的切块，其包含的点集由DeWall的分界线α或数据集DP的边界辅助点连线围成。DeWall在构建过程中按顺序记录其关联的点WP和未被α穿过的边WE，切块内的WE或边界辅助点连接成的线段构成切块点集的外壳H(图 4中实线)。在利用分治算法独立完成切块点集剖分后，H内部的三角形为正确的最终三角形，其外部为需要删除的错误三角形。利用切块内的WP或边界辅助点构建数据集凸包CH(图 4中V₁、V₆、V₇、V₈、V₁₁、V₁₂、V₁₃、V₁₅、V₁)，H与CH之间的三角形即为要删除的三角形。具体删除过程如下。

图  4  切块边界三角形删除

Figure 4.  Triangles Deletion of the Cutting Block Boundary

1) 从CH中取出一条边CHE(如V₈、V₁₁)，令其为E。

2) 若E的两端点不是切块内WP上相邻的两点，删除E所在的三角形T，则为WN-1；否则，WN=0。其中，WN为E两个端点在切块内WP上间隔的点数，可以证明，WN即为E与H之间需要删除的三角形个数。

3) WN>0时，判断T中另外两条边，若其两端点不是切块内WP上相邻的两点(如边V₈、V₁₀)，令其为E，转到步骤4)；否则(如边V₁₀、V₁₁)，结束该边判断。WN=0时，说明CHE与H之间的错误三角形删除完毕或CHE与H之间没有错误三角形，转到步骤5)。

4) 执行步骤2)~步骤3)。

5) 重复步骤1)~步骤4)，遍历CH中的每一条边，即完成该切块边界错误三角形的删除。

算法消耗的时间主要包括DeWall构建和各个切块剖分及边界三角形删除时间。n为总点数，δ为每个切块的点数，n/δ为切块数。

在构建DeWall时，每个三角形消耗时间大致相等，与点云数据量无关。由§1.2可知，每个切块DeWall关联的点数约为4δ^1/2，全部切块关联的点数为n/δ×4δ^1/2=4n/δ^1/2，即为DeWall含有的三角形个数，则构建DeWall的时间复杂度为O(4n/δ^1/2)= O(n/δ^1/2)。

对于每一个独立的切块，分治算法的时间复杂度为O(δlg(δ))，则所有切块为(n/δ)O(δlg(δ))= O(nlg(δ))，即为各独立切块分别剖分的时间和。显然，其时间复杂度优于全部点云直接剖分的时间复杂度O(nlg(n))。

由于一个切块内DeWall关联的点已经按顺序记录，并构成多边形，则利用Graham算法构建CH的时间复杂度为O(4δ^1/2)^[15]；对于删除三角形的个数，极端情况为CH是一个三角形，需要删除的三角形的个数为4δ^1/2-3，时间复杂度为O(4δ^1/2-3)= O(4δ^1/2)。所有切块边界三角形删除的时间复杂度为(n/δ) (O(4δ^1/2)+O(4δ^1/2-3))= O(n/δ^1/2)。

综上所述，总的时间复杂度为O(n/δ^1/2)+ O(nlg(δ))+ O(n/δ^1/2)= O(nlg(δ))+O(n/δ^1/2)。

一次读入点云V需要O(V)内存空间，每一个格网大概4个点，格网划分需要O(V/4) 内存空间，一个切块生成三角形需要O(2δ)内存空间。对于一次读入的点云V，每一个切块剖分完成后，释放三角形占用内存O(2δ)，算法占用内存降至O(V)+O(V/4)，因此，在逐块剖分过程中，以每一块剖分结束为节点，算法占用内存基本不变，为O(V)+O(V/4)。V剖分完成后，释放空间O(V)+O(V/4)，算法占用内存降到接近为零的值，再进行下一次点云的读入与剖分。所以，以每一次读入点云剖分完成为节点，算法占用内存也基本不变，接近为零。

实验环境为Intel(R) Core(TM) CPU(i3-2120 3.30 GHz), 8 G内存。试验数据为美国海岸线的变形监测数据，共6 200万机载LiDAR点云，分3次读入内存并剖分，各块的剖分利用文献[6]提出的分治算法。第一次读入1 890万点云，切割为三个纵块，对前两个纵块进行横向切割并剖分，第三个纵块与第二次读入数据合并拼接再剖分。前两个纵块共切割为14块(图 5)，各块大小在79~96万之间，构建的DeWall共含有53 199个三角形，消耗时间2.68 s。测试了DeWall的构建效率(表 1)，验证了以三角形数量为单位时，其时间复杂度为线性。

图  5  DeWall构建结果(逆时针旋转90°后)

Figure 5.  Experiment Result of Constructing DeWall

将本文算法(不计格网划分时间)与文献[6]提出的分治算法的时间效率进行了对比(表 2)。其中，每个切块边界三角形删除消耗时间均不超过0.2 s。不计I/O时间，测试了全部点云剖分的效率，如图 6所示。实验表明，因DeWall构建与切块边界三角形删除过程中关联的点云很少，且具有较好的效率与时间复杂度，在整个构网过程中消耗时间较少。所以，基于流计算的切块剖分算法的时间复杂度接近为O(nlg(δ))；本文算法时间性能较非线性的分治算法更适合大数据的剖分。图 7为构建的Delaunay三角网三维模型。

图  6  切块剖分算法效率

Figure 6.  Time Efficiency Test of the Cutting Block Algorithm

图  7  Delaunay三角网三维模型

Figure 7.  3D Model of Delaunay Triangulation

本文测试了14个切块剖分时算法占用的内存大小(图 8)。每一切块剖分时，算法占用内存达到一个较大的值，切块剖分结束后，存储三角形，释放内存，内存降到该切块剖分前的值。以每一块剖分结束为节点，算法占用内存基本不变。第一次读入点云剖分完成后，释放点云与格网划分占用内存，算法占用内存降到6.75M(不含最后纵块占用内存)，再进行下一次点云的读入与剖分。每次读入点云剖分完成后，算法占用内存均降到10 M以下。算法具有优异的空间性能。

图  8  算法占用内存变化

Figure 8.  Footprint Change of Triangulation

1) 利用DeWall通过切块实现了对待剖分数据的分而治之，算法不但保证了各切块剖分时具有分治算法的时间性能，并且算法的整体时间复杂度接近为O(nlg(δ))，优于非线性的分治算法，适合千万级以上点云的处理。

2) 运用切块策略控制切块大小与形状，避免了分治算法的深度递归与内存溢出。同时通过有序切块，并对切块进行线性组合模拟流计算，进一步提高了内存利用率。算法获得了处理较大数据所需的优异空间性能。

3) 利用切块边界错误三角形删除算法对切块三角网边界进行处理，并根据非耦合区域分解模式的性质，使数据最终构建的三角网为各子网简单相加的和。

基于流计算的切块剖分思想不但适用于水平分布的二维与三维点云剖分，并且可以推广到含有垂直点云的三维三角网的建模，这是下一步要进行的研究工作。