一种并行计算的流数据Delaunay构网算法  

A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing

作　　者：李坚[1] 李德仁[1] 邵振峰[1] 

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号430079

出　　处：《武汉大学学报（信息科学版）》2013年第7期794-798,共5页Geomatics and Information Science of Wuhan University

基　　金：国家973计划资助项目(2010CB731800);国家863计划资助项目(2009AA121404);国家自然科学基金资助项目(61172174)

摘　　要：提出了一种流数据算法进行Delaunay三角网构网,用来处理上十亿的LiDAR点云数据。该算法基于并行多核处理器架构,将三角网构网的分治算法与流数据处理相结合。一种四叉树结构用来自适应地划分点云数据文件,并将分割构网和合并子网工作动态调度分布到不同处理器,以提高负载均衡。算法通过并行计算,充分利用多核处理器平台的计算能力,取得了高运行效率和低内存占用。This paper presents a streaming data algorithm to execute Delaunay triangulations with large LiDAR point clouds （a billion data points） based on multi-core processor architec- ture. The algorithm combines divide-and-conquer triangulation with streaming data. A quad- tree structure is used to partition the LiDAR data into subnets adaptively, and schedules tri- angulation and merging of the subnet data into different processors for load balancing. Paral lel computing on multi-core processor architecture makes this algorithm highly efficient with a low memory footprint.

关 键 词：Delaunay构网 并行计算 流数据 LIDAR点云 四叉树 

分 类 号：P208[天文地球—地图制图学与地理信息工程] P237.3[天文地球—测绘科学与技术]