一种矢栅结合的三维点集Delaunay剖分方法  

3D Point Set Delaunay Subdivision Method Based on Vector-raster Integration

作　　者：殷宗林 胡海[1] YIN Zonglin;HU Hai

机构地区：[1]武汉大学资源与环境科学学院

出　　处：《地理空间信息》2020年第1期61-66,76,共7页Geospatial Information

基　　金：国家自然科学基金资助项目(41571395、41471328、41271443);国家重点研发计划资助项目(2017YFB0503500)

摘　　要：不规则四面体网格是3DGIS中一种重要的数据结构,其本质是三维Delaunay剖分。总结了现有矢量算法和栅格算法的特点;在当前计算机存储容量极大提高、GPU并行处理技术蓬勃发展、支持栅格三维运算的计算机软硬件条件已成熟的条件下,提出了一种矢栅结合的三维点集Delaunay剖分方法。该方法以距离变换为基础获取初始Delaunay剖分结果,同时针对栅格方法中无法区分同一栅格中的密集点问题,引入矢量中Delaunay增量算法加以解决。实验表明,该方法能以较低的时间复杂度计算三维点集的Delaunay四面体剖分;且由于其面向空间的特性,计算效率几乎不受点集中元素数量的影响,因而能满足海量数据的计算需求。Irregular tetrahedral mesh is an important data structure in 3D IS, and its essence is 3D Delaunay subdivision. In this paper, we summarized the characteristics of the existing vector algorithm and raster algorithm. And then, under the condition that the current computer storage capacity is greatly improved, the GPU parallel processing technology is flourishing, and the computer hardware and software conditions supporting the raster 3D operation are mature, we proposed a 3D point set Delaunay subdivision method based on vector-raster integration. This method obtains the initial Delaunay subdivision result based on the distance transform, and introduces the Delaunay incremental algorithm in the vector into solve the problem that the grid method cannot distinguish the dense points in the same grid. The experiments show that the method can calculate the Delaunay tetrahedral subdivision of the 3 D point set with low time complexity. In addition, due to the space-oriented nature of the method, its computational efficiency is almost unaffected by the number of elements in the point set, and thus can meet the computational requirements of massive data.

关 键 词：三维Delaunay剖分 距离变换 矢栅结合 并行计算 地图代数 

分 类 号：P208[天文地球—地图制图学与地理信息工程]