基于包含检验法的多边形栅格化并行算法研究  

Research on Parallel Rasterization Algorithm Based on Containment Test Method

作　　者：周琛[1] 陈振杰[1] 王亚飞[1] 任沂斌 

机构地区：[1]江苏省地理信息技术重点实验室 南京大学,江苏南京210023

出　　处：《地理与地理信息科学》2014年第1期32-36,共5页Geography and Geo-Information Science

基　　金：国家863计划资助项目(2011AA120301)

摘　　要：随着对地观测技术的快速发展和数据规模的急剧增长,矢量数据快速栅格化已成为业界关注的重要研究内容。该文将并行计算技术应用于矢量多边形栅格化中,探索了矢量数据划分方法、边界栅格单元处理方法等关键问题,设计并实现了基于包含检验法的矢量多边形栅格化并行算法。基于土地利用现状数据对并行算法的精度、并行效率等进行了测试与分析。试验证明,在进程数不超过CPU核数时,并行算法的加速比随进程数增长显著;而当进程数达到CPU核数以后,并行算法加速比总体趋于稳定。并行效率与数据的划分方式、数据的存储方式密切相关,划分方式的正确与否将直接关系到算法的并行效率。With the rapid development of earth observation technology and dramatic expansion in data size, rapid rasterization for vector data has become an important issue in GIS （Geographic Information System） field. In this paper, the parallel computing technology is applied into the study of rasterization and a parallel rasterization algorithm is proposed based on containment test method. The primary issues in rasterization, including vector data decomposition and different cases of raster cells on the boundaries of polygons, are also studied. A land use data with large volume is used in experiments. The accuracy and efficiency of the proposed parallel algorithm are studied. Results show that the speedup increases dramatically when the number of processes is less than the number of cores and reaches a plateau when more processes are used. In addition, the parallel efficiency is closely related with the data decomposition strategy and data storage method. An appropriate data decomposition strategy can improve the parallel efficiency.

关 键 词：地理信息系统 栅格化 包含检验法 数据划分 并行计算 

分 类 号：TP751[自动化与计算机技术—检测技术与自动化装置]