直接剖分法可以避免平面投影法中出现的狭长三角形，并且执行的速度也比较快，但是受到点云拓扑结构复杂性的影响，在很多情况下会出现自交现象.为了发挥直接剖分方法的优势，本文提出一种基于分治策略的三角剖分方法，通过点云数据的区域分割、在区域内完成剖分，有效降低点云数据总体结构复杂性的影响，以避免自交问题的出现.整个方法的实现分为3个步骤：

第一步，对点云数据进行区域分割.将已知的点云数据按照预定规则进行区域划分，这样分割成的区域将成为后续剖分的基础.因为每个区域内的点云数据量大为降低，其拓扑结构复杂性也大为降低，不会形成自交问题.

第二步，在第一步分割出的各个区域内独立进行三角剖分，剖分过程按照一定的剖分准则进行，充分发挥直接剖分方法速度快的优势.

第三步，将各个区域的剖分结果进行连接.因为各个区域内的剖分形成了相互独立的边界，为了实现各剖分区域之间的连接，将按照空间Delaunay方法进行边界处的剖分连接.

点云数据呈现三维形态空间分布.因此，为了进行有效的区域分割，需要先将这些点云数据投影到二维平面，在二维平面上进行区域分割.但是，投影过程中可能会出现两种情况，第一种情况就是所有点云数据在xyz坐标系下的x投影和y投影均无重叠现象，故只需按照各点的x坐标和y坐标排序后进行区域分割即可；第二种情况就是一部分点云数据在xyz坐标系下的x投影和y投影有重叠现象.这两种情况如图 1所示.

在实际操作中，如果出现第一种情况，即所有点云数据无重叠的情况，就直接向平面进行投影然后进行区域分割就可以了.如果出现第二种情况，即部分点云数据有重叠的情况，加入一个分割面β，将点云数据划分为两个子集合，再对每一个子集合内的数据进行分别投影，然后再各自进行区域划分.

在实际情况中，可能会出现更为复杂的局面，如点云数据为褶皱式闭合曲面，这就需要加入更多的分割平面，避免出现重叠.

区域分割的标准，应该确保每个区域内的点云数据量，其拓扑结构的复杂性不足以在直接剖分过程中产生自交现象.

经过区域分割后，原始点云数据被划分为一个个独立的区域，接下来的工作就是按照直接剖分方法的策略，在每一个区域内进行三角剖分.首先在区域中心选择2个点进行连线，条件是这2个点的距离比其他点近，其后就按照4个剖分准则逐步加入新点，完成剖分工作.这4个剖分准则的示意情况如图 2所示.

所谓异侧剖分准则，就是确定了一个三角形以后，再次寻找新点连接新的三角形时，必须使新点满足和剖分边所对应的第三顶点在剖分边的两侧，这一准则的效果如图 2(a)所示.在图 2(a)中，三角形△ABC中AB边为待剖分边，根据空间解析几何的基本方法，就可以求得三角形△ABC的法向量n1，并且这个法向量的方向是从顶点A指向顶点B的右手螺旋定则方向.如果点P和点P′为可能加入的2个新点，那么可以计算出三角形△ABP的法向量n2，这个过程一样要保证这个法向量的方向是从顶点A指向顶点B的右手螺旋定则方向.至此，就可以计算出2个法向量之间的夹角余弦值cosα₁.如果cosα₁ < 0，那么就表明P点和C点分别位于AB这条边的两侧；如果cosα₁>0，那么就表明P点与C点位于AB这条边的同侧.

所谓法向量夹角最大剖分准则是指，三角剖分过程中为了使得剖分后的空间曲面尽可能地光滑连续，需要满足剖分得到的新三角形和原三角形之间的法向量夹角最大.对照图 2(b)，在边AB进行新三角形引入时，如果P点和P′点都满足异侧准则，需要进一步根据法向量夹角最大剖分准则完成新点的选择，也就是分别计算法向量n2与法向量n1、法向量n3与法向量n1所成的角度.可见，法向量n2与法向量n1所成的角度较大，这就表明P点优于P′点，因此应选择P点作为新点进行剖分.

所谓阈值距离剖分准则，就是新点和剖分边之间的距离应在一个合理的阈值范围内.如图 2(c)所示，P点位于P′点下方，根据法向量夹角最大剖分准则应该选择P′点进行剖分.可是，P′点到AB边的距离远远超出了设定阈值，如果选择此点会出现狭长三角形进而导致曲面细节丢失.因此，这里的新点选择，根据阈值距离剖分准则仍然要选择P点.

所谓最小内角最大剖分准则，就是要新点加入后的剖分结果，形成的三角形最小内角应该尽可能地大.如果2个待选新点都满足向量夹角最大剖分准则和阈值距离剖分准则，那么就需要进一步执行最小内角最大剖分准则完成选点.在图 2(d)中，∠1是三角形△ABP的最小内角，∠2是三角形△ABP′的最小内角，经过比较可以看出∠1＞∠2，故选择P点完成剖分优于P′点.

按照前述的处理，空间点云数据已经被分割成多个区域并在区域内完成了三角剖分.接下来，需要将这些区域的剖分结果连接起来.由于各区域剖分结果都形成了既定边界，无法继续按照前面的准则进行区域间连接.因此，选择空间Delaunay空圆准则进行区域间的连接剖分.需要注意的是，Delaunay剖分会产生新点，从而在一定程度上改变原有区域内剖分结果，但效果是使得剖分结构更加光滑连续，重建后曲面的视觉效果更好.

验证本文提出的基于分治策略的三角剖分方法对于点云数据的剖分效果和重建效果，分别展开2组实验研究，①规则曲面点云数据的三角剖分实验，②非规则曲面点云数据的三角剖分实验.

规则曲面的实验点云分别选择了三维球面点云、Z曲面点云和LOG算子曲面点云.经过本文剖分方法获得的剖分结果如图 3所示.

从图 3中的结果可知，按照本文提出的三角剖分方法完成点云数据剖分，形成的三角网格均匀连续，视觉效果逼真生动，较好地复原出了点云数据所对应的曲面.进一步观察3个曲面剖分重建完成的时间，如表 1所示.

从表 1中的数据可知，本文提出的三角剖分方法对于规则曲面点云数据的剖分重建速度也是比较快的.

第一组实验结果充分表明了本文提出的基于分治策略的三角剖分方法，对于规则曲面的点云数据具有理想的重建效果，不仅剖分和重建的视觉效果好，而且执行速度快.

为了验证本文提出的剖分方法所具有的鲁棒性，进一步对非规则曲面、数据量较大的点云数据进行剖分实验，实验结果如图 4所示.

从图 4可知，这组点云的重建结果清晰地显示出一个人头像的形状.这组点云不仅数量大，而且同第一组实验相比是明显的非规则点云，同时表现出水平方向系数、垂直方向稠密的特征.经过本文方法的处理，获得了比较理想的三角剖分结果和重建结果.此组点云中点的数据量为4 822个，经过本文方法处理，剖分时间仅仅为5.634 s.

在点云数据的三角剖分方法中，平面投影法会导致大量狭长三角形出现，直接剖分法会因点云拓扑结构的复杂性出现自交现象.为此，本文提出了一种基于分治策略的三角剖分方法.通过投影将复杂点云进行区域分割，之后在各个区域内按照四大准则进行三角剖分，最后执行Delaunay空圆准则完成区域之间的连接.针对规则曲面点云和非规则曲面点云分别执行剖分实验，实验结果表明，本文的剖分方法对于两类点云数据均具有理想的剖分效果，剖分重建出的曲面具有逼真的视觉效果，并且剖分速度快.