Data decomposition method for parallel polygon rasterization considering load balancing

• Published in: Computers & geosciences 2015-12, Vol.85, p.196-209
• Main Authors: Zhou, Chen, Chen, Zhenjie, Liu, Yongxue, Li, Feixue, Cheng, Liang, Zhu, A-xing, Li, Manchun
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity; Computational efficiency; Computing time; Data decomposition; Decomposition; Geo-processing; Load balancing; Load balancing (computing); Parallel computing; Parallel processing; Polygon rasterization; Polygons
• ISSN: 0098-3004; 1873-7803
• DOI: 10.1016/j.cageo.2015.09.003

It is essential to adopt parallel computing technology to rapidly rasterize massive polygon data. In parallel rasterization, it is difficult to design an effective data decomposition method. Conventional methods ignore load balancing of polygon complexity in parallel rasterization and thus fail to achieve high parallel efficiency. In this paper, a novel data decomposition method based on polygon complexity (DMPC) is proposed. First, four factors that possibly affect the rasterization efficiency were investigated. Then, a metric represented by the boundary number and raster pixel number in the minimum bounding rectangle was developed to calculate the complexity of each polygon. Using this metric, polygons were rationally allocated according to the polygon complexity, and each process could achieve balanced loads of polygon complexity. To validate the efficiency of DMPC, it was used to parallelize different polygon rasterization algorithms and tested on different datasets. Experimental results showed that DMPC could effectively parallelize polygon rasterization algorithms. Furthermore, the implemented parallel algorithms with DMPC could achieve good speedup ratios of at least 15.69 and generally outperformed conventional decomposition methods in terms of parallel efficiency and load balancing. In addition, the results showed that DMPC exhibited consistently better performance for different spatial distributions of polygons. •A novel data decomposition method based on polygon complexity (DMPC) is presented.•DMPC can effectively parallelize different polygon rasterization algorithms.•Large-scale vector polygon data can be favorably addressed with this method.•DMPC can perform consistently well with different spatial distributions of polygons.