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

J4 ›› 2013, Vol. 35 ›› Issue (4): 37-41.

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

周琛，陈振杰，张帅

（南京大学地理与海洋科学学院，江苏南京 210023）

收稿日期:2012-05-31 修回日期:2012-08-23 出版日期:2013-04-25 发布日期:2013-04-25
基金资助:
国家863计划资助项目（2011AA120301）

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

ZHOU Chen,CHEN Zhenjie,ZHANG Shuai

(School of Geographic and Oceanographic Sciences,Nanjing University,Nanjing 210023,China)

Received:2012-05-31 Revised:2012-08-23 Online:2013-04-25 Published:2013-04-25

摘要/Abstract

摘要：

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

关键词: 矢量栅格化, 边界代数法, 并行算法

Abstract:

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.

Key words: rasterization;boundary algebra filling;parallel algorithm

周琛，陈振杰，张帅. 基于边界代数法的矢量栅格化并行算法设计与实现[J]. J4, 2013, 35(4): 37-41.

ZHOU Chen,CHEN Zhenjie,ZHANG Shuai. Design and implementation of rasterization
parallel algorithm based on boundary algebra filling [J]. J4, 2013, 35(4): 37-41.

[1]	肖调杰, 周峰, 郑翾宇, 刘剑, 陈琳, 刘杰, 易明宽, 陈旭光, 龚春叶, 杨博, 甘新标, 李胜国, 左克, . 大规模三维频率域电磁积分方程法数值模拟[J]. 计算机工程与科学, 2023, 45(11): 1901-1910.
[2]	许晓阳, 王斯棋. 基于粒子分解的SPH并行算法研究与应用[J]. 计算机工程与科学, 2022, 44(06): 964-970.
[3]	刘杰, 龚春叶, 杨博, 郭晓威, 甘新标, 李胜国, 李超, 陈旭光, 肖调杰, 穆利安, 宋敏, 赵冬勇, 鞠羽中. YH-ACT：热工流体力学并行应用程序[J]. 计算机工程与科学, 2021, 43(01): 58-69.
[4]	李雯, 迟利华, 张会, 张哲, 刘杰, . 潜艇使用自航式声诱饵防御鱼雷模型并行计算方法研究[J]. 计算机工程与科学, 2020, 42(12): 2163-2168.
[5]	王俊吉1,2,朱朝艳1,2,4,陈建军1,2,郑澎3，5,徐权3. 基于无锁原子操作的多线程并行Delaunay三角化算法[J]. 计算机工程与科学, 2018, 40(05): 773-779.
[6]	章子凯，武继刚，姜文超，刘竹松. 容错处理器阵列的多逻辑列并行重构算法[J]. 计算机工程与科学, 2018, 40(01): 24-33.
[7]	李娟1，汤德佑1，傅娟2，3. 一种基于蚁群算法的生物序列并行比对方法[J]. 计算机工程与科学, 2017, 39(09): 1610-1616.
[8]	宋威，吉红蕾，李晋宏. 一种高效用项集并行挖掘算法[J]. J4, 2015, 37(03): 422-428.
[9]	杨菊，吴卓锋，王刚，刘晓光. 多核平台PAML并行算法研究[J]. J4, 2013, 35(9): 15-19.
[10]	王多雷，龙汉，陈璇. 组合打击下一类面目标易损性的并行计算研究[J]. J4, 2013, 35(4): 42-46.
[11]	刘立国，莫锦军，袁乃昌. 基于“天河一号”的并行电磁计算求解器[J]. J4, 2013, 35(3): 43-47.
[12]	焦善飞1,2，何晨2，豆育升2，唐红1,2. 短程力分子模拟在Hadoop上的实现及优化[J]. J4, 2013, 35(2): 26-31.
[13]	龚春叶1,2,3,包为民1,闵昌万1,张烨琛1，刘杰3. 分数阶微分方程的一种细粒度数据级并行算法[J]. J4, 2013, 35(11): 76-79.
[14]	徐莹，徐磊，姜恺. 三维NavierStokes方程分步法的并行算法在异构平台上实现初探[J]. J4, 2012, 34(9): 33-39.
[15]	徐莹，徐磊. 三维Navier-Stokes方程的差分-谱方法混合法在GPU上的实现与优化[J]. J4, 2012, 34(8): 53-58.