基于边界代数法的矢量栅格化并行算法设计与实现

Design and implementation of rasterization parallel algorithm based on boundary algebra filling

在遥感地学分析、空间决策分析等领域,常需要将大量的矢量数据转换为栅格数据。面对海量数据快速转换的现实需求,现有的以串行算法为主、基于传统单机单进程的矢量栅格化算法已难以满足要求。在分析现有的矢量栅格化算法的基础上,考虑到边界代数法算法简单、可靠性高、运算速度快的特点,选取边界代数法作为研究对象。在此基础上,设计了基于边界代数法的矢量栅格化并行算法,并通过MPI、GDAL、C++等工具实现,利用不同规模的矢量数据进行并行效率的测试。测试结果表明,该算法结果正确,计算效率得到明显的提升,对于大数据量转换效率的提升更显著。

Rasterization is often required in many fields, such as geo-science analysis of remote sensing and analysis of spatial decision. Faced with the reality demand of rapid conversion of mass data, the existing serial rasterization algorithms based on the traditional single machine and single process are difficult to meet the requirements. In this paper, on basis of the analysis of the existing rasterization algorithms, the boundary algebra filling method is studied since it is simple, reliable and fast operational. The rasterization parallel algorithm based on boundary algebra filling was designed and implemented by MPI, GDAL and C＋＋. In order to evaluate the parallel efficiency of the algorithm, different scale data were applied in the experiment. Experimental results show that this algorithm is right and improves the calculating efficiency. What＇s more, when the data is larger, the advantage of the algorithm is greater.