留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种采用流计算的Delaunay三角网切块剖分算法

张春亢 赵学胜 王洪斌

张春亢, 赵学胜, 王洪斌. 一种采用流计算的Delaunay三角网切块剖分算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
引用本文: 张春亢, 赵学胜, 王洪斌. 一种采用流计算的Delaunay三角网切块剖分算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
ZHANG Chunkang, ZHAO Xuesheng, WANG Hongbin. A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
Citation: ZHANG Chunkang, ZHAO Xuesheng, WANG Hongbin. A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375

一种采用流计算的Delaunay三角网切块剖分算法

doi: 10.13203/j.whugis20150375
基金项目: 

国家自然科学基金 41171306

高等学校博士学科点专项科研基金 20130023110001

详细信息
    作者简介:

    张春亢, 博士生, 主要从事LiDAR点云数据处理与3D GIS建模方面的研究。chkang.chd@163.com

    通讯作者: 赵学胜, 博士, 教授。zxs@cumtb.edu.cn
  • 中图分类号: P208

A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

Funds: 

The National Natural Science Foundation of China 41171306

the Specialized Research Fund for the Doctoral Program of Higher Education 20130023110001

More Information
    Author Bio:

    ZHANG Chunkang, PhD candidate, specializes in LiDAR point cloud data processing etc. E-mail:chkang.chd@163.com

    Corresponding author: ZHAO Xuesheng, PhD, professor. E-mail:zxs@cumtb.edu.cn
图(8) / 表(2)
计量
  • 文章访问数:  1444
  • HTML全文浏览量:  120
  • PDF下载量:  402
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-10-13
  • 刊出日期:  2017-07-05

一种采用流计算的Delaunay三角网切块剖分算法

doi: 10.13203/j.whugis20150375
    基金项目:

    国家自然科学基金 41171306

    高等学校博士学科点专项科研基金 20130023110001

    作者简介:

    张春亢, 博士生, 主要从事LiDAR点云数据处理与3D GIS建模方面的研究。chkang.chd@163.com

    通讯作者: 赵学胜, 博士, 教授。zxs@cumtb.edu.cn
  • 中图分类号: P208

摘要: 针对海量LiDAR点云Delaunay三角网剖分的时间与空间性能的矛盾问题,提出了一种采用切块的流计算Delaunay构网算法。首先利用三角网墙(DeWall)从点云上切割特定大小与形状的独立数据块,避免分治算法的深度递归与内存溢出;然后运用分治算法对切块剖分,并给出了切块边界错误三角形删除算法;重复上述过程完成子网剖分,并依据非耦合区域分解模式合并为最终三角网。引入流计算的思想,以进一步提高算法的空间性能。分析与实验表明:该算法占用了较低内存,并取得了接近为Onlg(δ))(δ为一个切块点数,且δn)的时间复杂度。

English Abstract

张春亢, 赵学胜, 王洪斌. 一种采用流计算的Delaunay三角网切块剖分算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
引用本文: 张春亢, 赵学胜, 王洪斌. 一种采用流计算的Delaunay三角网切块剖分算法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
ZHANG Chunkang, ZHAO Xuesheng, WANG Hongbin. A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
Citation: ZHANG Chunkang, ZHAO Xuesheng, WANG Hongbin. A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
  • 激光雷达能够在短时间内获取大量的点云,并在GIS、计算机图形学等领域得到了广泛应用,但海量LiDAR点云对Delaunay三角网剖分算法的性能提出了更高的要求[1]。传统的构网算法因不能同时兼顾算法的时间与空间性能,不适合较大点云的三角网剖分。目前在PC机上实现千万级以上的点云剖分仍然依赖于并行计算,但对研究者的编程能力要求较高,不易实现。如何平衡和处理传统算法在剖分海量点云时面临的时间与空间性能之间的矛盾,成为海量点云建模需要首先解决的关键问题之一。

    为了兼顾算法的时间与空间性能并对海量数据进行构网,有研究者提出了分治算法与逐点插入算法(或扫描线算法)相结合的合成算法[2-5]、改进的分治算法[6, 7]、改进的内插算法[8]和数学形态学算法[9]。文献[10-11]对扫描线算法的时间效率进行了改进,均取得了O(nlg(n))时间复杂度与O(n)空间复杂度。流计算是一种在内存中进行线性有序数据处理的运算方式,其在内存使用上具有高效性,适合大数据处理。Isenburg[12]提出了一种基于流计算的海量三角网构建算法。本文基于三角网分治算法时间性能的高效性和流计算空间性能的高效性,利用切块的方式实现一种新的Delaunay构网算法,以期在进行海量点云建模时能同时兼顾算法的时间与空间性能。

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

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

      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,长为δ/wPR约为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) 分界线的确定。依据切块大小与形状,在切割区选择一点P1和其最近点P2,经过P1P2之间一点作X(Y)轴的垂线,作为分界线α(图 3中虚线)。

      2) DeWall构建。以P1P2为初始基线,利用第三点查找的动态实现方法查找第三点P3,以穿过α的新边(P2P3)作为新基线,查找第三点P4,再以穿过α的新边(P3P4)作为新基线,直至这一条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(图 4V1V6V7V8V11V12V13V15V1),HCH之间的三角形即为要删除的三角形。具体删除过程如下。

      图  4  切块边界三角形删除

      Figure 4.  Triangles Deletion of the Cutting Block Boundary

      1) 从CH中取出一条边CHE(如V8V11),令其为E

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

      3) WN>0时,判断T中另外两条边,若其两端点不是切块内WP上相邻的两点(如边V8V10),令其为E,转到步骤4);否则(如边V10V11),结束该边判断。WN=0时,说明CHEH之间的错误三角形删除完毕或CHEH之间没有错误三角形,转到步骤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

      表 1  DeWall构建效率

      Table 1.  Time Efficiency Test of Constructing DeWall

      三角形数/个消耗时间/s效率/(个/s)
      17 3910.9019 323
      43 8002.1120 758
      53 1992.6819 850

      将本文算法(不计格网划分时间)与文献[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

      表 2  算法效率对比

      Table 2.  Efficiency Comparison Between Different Triangulation Algorithms

      块数(点数)连续1块(96万)连续2块(188万)连续3块(277万)连续4块(358万)连续5块(447万)
      本文算法/s25.7049.2471.4990.88113.34
      分治算法/s24.1251.6280.30107.82139.24

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

      图  8  算法占用内存变化

      Figure 8.  Footprint Change of Triangulation

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

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

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

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

参考文献 (15)

目录

    /

    返回文章
    返回