摘要
随着现代数据获取技术(如机载LIDAR)的不断发展,D-TIN构建算法所面对的数据量不断激增,动辄上亿规模的海量点集数据对现有的D-TIN构建算法提出了新的挑战.传统的D-TIN构建算法多基于纯内存模式(In-Core),即将所有数据一次性全部读入内存,处理完毕后再全部释放. 为了满足海量点集数据快速构建D-TIN的应用需求,本文在串行逐点插入法的基础上提出一种面向海量点集数据的并行D-TIN构建算法。该算法以D-TIN的空外接圆法则为依据,将逐点插入法执行过程中生成的三角形,根据后续插入点是否在该三角形的外接圆内而判断该三角形是否是最终D-TIN的组成部分,并依据此将插入过程中生成的三角形分为稳定三角形和待定三角形。算法执行过程中首先构建一系列由稳定三角形所组成的三角形条带,利用这些三角形条带根据动态负载均衡原则将二维点集在空间划分为若干独立的子区域,然后同时对各子区域采用Iseburg等提出的Streaming Delaunay进行D-TIN构建,最终D-TIN构建结果由用于划分子区域的三角形条带和各子区域的D-TIN构建结果直接合并而成。