Parallel scanline algorithm for rapid
rasterization of vector geographic data
Yafei Wang, Zhenjie Chen, Liang Cheng n
, Manchun Li nn, Jiechen Wang
Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology, Nanjing University, 22 Hankou Road, Nanjing 210097, China
Computers & Geosciences Volume 59, September 2013, Pages 31-40 :
Abstract
With the expansion of complex geographic calculations and the increase of spatial data types involved in the spatial analysis of large areas, the need becomes urgent for fast rasterization of massive multi-source geographic vector data. A parallel scanline algorithm is proposed for rapid rasterization. It provides a systematic solution to solve the complicated situation in parallel processing (cross-processor boundaries, common boundaries, and tiny polygons), thus ensuring the accuracy of the parallel scanline algorithm. The relationship of parallel speedup with the number of processors, the data partition pattern, and the raster grid size is discussed. Massive vector geographic data (approximately 0.7 million polygons) used in the experiment were effectively processed, thereby dramatically reducing the processing time and getting good speedup.
Keywords: Vector geographic data Rasterization Parallel processing Scanline Speedup
1. Introduction
Vector data and raster data are the two basic geographic data types used in the Geographic Information System (GIS) (Maguire et al., 1991), and the latter is more suitable for spatial analysis and spatial simulation (Goodchild, 2011). As satellite technologies advance forward, raster data have become increasingly more popular than vector data. At present, raster data is already the most dominant format used by data sources. With the expansion of complex geographic calculations and the increase of spatial data types involved in the spatial analyses on large areas (Lee et al., 2011), the need for rasterization of massive multi-sourced vector geographic data becomes more and more urgent. However, due to the sequential architecture of existing rasterization algorithms and the traditional desktop computer platform, current solutions cannot meet the strong demand of fast rasterization on massive vector geographic data. In recent years, the gradual popularity of the new parallel hardware architecture, such as computer clusters and multi-core processors, offers a new opportunity to improve the conversion speed of massive geographic data, which had been restricted by the limited computing performance of older technologies (Kenneth et al., 2003; Gong and Xie, 2009). To achieve the requirements of rapid rasterization on massive vector data, it is necessary to combine geographic data conversion technology with parallel hardware architecture by developing new parallel algorithms, thereby reducing processing time through parallel computing (Mariethoz, 2010; Schiele et al., 2012).
Parallel rasterization of vector geographic data includes parallel rasterization of point data, of line data, and of polygon data. Among these three, parallel rasterization of polygon data is relatively complex. Therefore, this paper focuses on the study of parallel rasterization algorithms on polygon data. Based on the analysis of the limitations of the existing researches, a new parallel scanline algorithm for rapid rasterization of vector polygon data is proposed. Its main procedures include: (1) Executing particle-sized partitions on vector polygon data, according to the number of processors and the spatial location of the vector polygon data, so as to adapt to different-sized grid blocks, and (2) Fusing partition parts, in which a parallel strategy using pixel-center scanlines is proposed to solve the complicated situation, including cross-processor boundaries, common boundaries, and tiny polygons.
The algorithm was implemented for multi-core processors. The land use data of Changsha City, China was used to check the performance of this algorithm, and the results were compared with those derived from the commercial software ArcGIS. Meanwhile, this research measures the operating time and speedup of this parallel algorithm, and this paper discusses the relationship of the parallel speedup with the number of processors, the data partition pattern, and the grid cell size.
Fig. 2. Parallel scanline processing of the cross-processor boundaries. (a) Vector Polygon A and B operated in parallel by Processors 0 and 1 (the blue and red boundaries named as cross-processor boundaries), (b) Scanline operation performed to two polygons in Processor 0 and 1, simultaneously, (c) The corresponding rasterization results (gray and pink area) to Polygon A and B (green area not involved in rasterization based on pixel center-based scanline algorithm). (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.)
6. Conclusion
This paper proposes a parallel scanline algorithm for rapid rasterization of massive geographic vector data. The following conclusions were reached based on our experimental analysis
(a) Massive geographic vector data (about 0.7 million polygons) used in the experiment were effectively processed, dramatically reducing the data transformation time and achieving good speedup.
(b) In comparison to the rasterization results from the ArcGIS software, the parallel algorithm leads to almost identical results, thus ensuring a high accuracy.
(c) The speedup of this algorithm can be optimized by selecting the number of processors, the data partition pattern, and the raster grid size.
However, the parallel efficiency of this algorithm is related to the spatial distribution of the vector polygons. A better scheduling strategy might achieve greater parallel efficiency; therefore, this requires further study and experiment. Further research is needed on finding the right balance among raster grid size, number of processors, and speedup, in order to make full use of the existing hardware architecture to meet the specific application requirements.
References
Congalton, R.G., 1997. Exploring and evaluating the consequences of vector-toraster and raster-to-vector conversion. Photogrammetric Engineering & Remote Sensing 63 (4), 425–434.
Correa, W.T., Klosowski, J.T., Silva, C.T., 2003. Out-of-core sort-first parallel rendering for cluster-based tiled displays. Parallel Computing 29 (3), 325–338.
Goodchild, M.F., 2011. Scale in GIS: an overview. Geomorphology 130 (2), 5–9.
Guan, Q.F., Clarke, K.C., 2010. A general-purpose parallel raster processing programming
library test application using a geographic cellular automata model. International Journal of Geographical Information Science 24 (5), 695–722.
Gong, J.Y., Xie, J.B., 2009. Extraction of drainage networks from large terrain datasets using high throughput computing. Computers & Geosciences 35 (2), 337–346.
Healey, R., Dowers, S., Gittings, B., Mineter, M., 1998. Parallel Processing Algorithms for GIS [M]. Taylor and Francis, London, UK, pp. 253–263.
Hollander, M., Ritschel, T., Eisemann, E., Boubekeur, T., 2011. ManyLoDs: parallel many-view level-of-detail selection for real-time global illumination. Computer Graphics Forum 30 (4), 1233–1240.
Hormann, K., Agathos, A., 2001. The point in polygon problem for arbitrary polygons. Computational Geometry 20 (3), 131–144.
Jiménez, J.J., Feito, F.R., Segura, R.J., 2009. A new hierarchical triangle-based pointin-polygon
data structure. Computers & Geosciences 35 (9), 1843–1853.
Kenneth, A.H., Coddington, P.D., James, H.A., 2003. Distributed frameworks and parallel algorithms for processing large-scale geographic data. Parallel Computing 29 (10), 1297–1333.
Lee, C.A., Gasster, S.D., Plaza, A., Chein-I, C., Bormin, H., 2011. Recent developments in high performance computing for remote sensing: a review. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing 4 (3), 508–527.
Liao, S.L., Bai, Y., 2010. A new grid-cell-based method for error evaluation of vectorto-raster conversion. Computational Geoscience 14 (4), 539–549.
Maguire, D.A., Goodchild, M.F., Rhind, D.W., 1991. Geographical Information Systems: Principle. 1. Longman Group UK Limited, Essex, U.K, pp. 45–54.
Mariethoz, G., 2010. A general parallelization strategy for random path based geostatistical simulation methods. Computers & Geosciences 36 (7), 953–958.
McManus, D., Beckmann, C., 1997. Optimal static 2-dimensional screen subdivision for parallel rasterization architectures. Computers & Graphics 21 (2), 159–169.
Pineda, J., 1988. A parallel algorithm for polygon rasterization. Computer Graphics
22 (4), 17–20.
Popescu, V., Rosen, P., 2006. Forward rasterization. ACM Transactions on Graphics
25 (2), 375–411.
Roca, J., Moya, V., Gonzalez, C., Escandell, V., Murciego, A., Fernandez, A., Espasa, R., 2010. A SIMD-efficient 14 instruction shader program for high-throughput microtriangle rasterization. The Visual Computer 26, 707–719.
Schiele, S., Möller, M., Blaar, H., Thürkow, D., Müller-Hannemann, M., 2012. Parallelization strategies to deal with non-localities in the calculation of regional land-surface parameters. Computers & Geosciences 44, 1–9.
Subhlok, J.M., Stichnoth, J.M., O'Hallaron, D.R., Gross, T., 1993. Exploiting task and data parallelism on a multicomputer. ACM SIGPLAN Notices 28 (7), 13–22.
van der Knaap, W.G.M., 1992. The vector to raster conversion: (Mis)use in geographical information systems. International Journal of Geographical Information Systems 6 (2), 159–170.
Wang, X.L., Sun, Q.H., Jiang, C.S., 2006. An optimization algorithm for transferring vector to raster data based on minimized area error. Acta Geodaeticaet Cartographica Sinica 35 (3), 273–277. [in Chinese].
Xie, J.B., 2012. Implementation and performance optimization of a parallel contour line generation algorithm. Computers & Geosciences 49, 21–28.
Yang, S., Yong, J.H., Sun, J.G., Gu, H.J., Paul, J.C., 2010. A point-in-polygon method based on a quasi-closest point. Computers & Geosciences 36 (2), 205–213.
Zhou, C.H., Ou, Y., Yang, L., Qin, B., 2007. An equal area conversion model for rasterization of vector polygons. Science in China Series D: Earth Science 50
(S1), 169–175.
ليست هناك تعليقات:
إرسال تعليق