A strategy for parallelising polygon rasterisation algorithms using multi-core CPUs

References

• Agarwal, D., et al., 2012. A system for GIS polygonal overlay computation on Linux cluster—an experience and performance report. In: Proceedings of 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, IEEE, 1433–1439.
   Google Scholar
• Armstrong, M.P., Pavlik, C.E., and Marciano, R., 1994. Experiments in the measurement of spatial association using a parallel supercomputer. Geographical Systems, 1 (4), 267–288.
   Google Scholar
• Armstrong, M.P., Cowles, K.M. and Wang, S.W., 2005. Using a computational grid for geographic information analysis: a reconnaissance. The Professional Geographer, 57 (3), 365–375.
   Web of Science ®Google Scholar
• Bohn, C.A. and Lamont, G.B., 2002. Load balancing for heterogeneous clusters of PCs. Future Generation Computer Systems, 18 (3), 389–400.10.1016/S0167-739X(01)00058-9
   Web of Science ®Google Scholar
• Carvers, S.J. and Brunsdon, C.F., 1994. Vector to raster error and feature complexity: an empirical study using simulated data. International Journal of Geographical Information System, 8 (3), 261–270.10.1080/02693799408901999
   Web of Science ®Google Scholar
• Chang, K.T., 2012. Introduction to geographic information systems. New York, NY: McGraw-Hill.
   Google Scholar
• Dobre, C. and Xhafa, F., 2014. Parallel programming paradigms and frameworks in big data era. International Journal of Parallel Programming, 42 (5), 710–738.10.1007/s10766-013-0272-7
   Web of Science ®Google Scholar
• Duckham, M., Goodchild, M.F., and Worboys, M., 2003. Foundations of geographic information science. Florida: CRC Press.
   Google Scholar
• Feito, F., Torres, J.C., and Urena, A., 1995. Orientation, simplicity, and inclusion test for planar polygons. Computers & Graphics, 19 (4), 595–600.
   Web of Science ®Google Scholar
• Gharachorloo, N., et al., 1989. A characterization of ten rasterization techniques. In: Proceedings of the 16th annual conference on Computer graphics and interactive techniques, ACM, 355–368.
   Google Scholar
• Gorobets, A., et al., 2011. Hybrid MPI + OpenMP parallelization of an FFT-based 3D Poisson solver with one periodic direction. Computers & Fluids, 49 (1), 101–109.
   Web of Science ®Google Scholar
• Guan, X.F., Wu, H.Y., and Li, L., 2012. A parallel framework for processing massive spatial data with a split-and-merge paradigm. Transactions in GIS, 16 (6), 829–843.10.1111/tgis.2012.16.issue-6
   Web of Science ®Google Scholar
• Haines, E., 1994. Point in polygon strategies. In: P. Heckbert Editor, eds. Graphics Gems IV. San Diego, CA: Academic Press, 24–46.10.1016/B978-0-12-336156-1.50013-6
   Google Scholar
• He, K.J., et al., 2007. PGO: A parallel computing platform for global optimization based on genetic algorithm. Computers & Geosciences, 33 (3), 357–366.
   Web of Science ®Google Scholar
• Healey, R.G., Dowers, S., and Minetar, M., 1998. Parallel Processing Algorithms for GIS. London: Taylor & Francis.
   Google Scholar
• Hormann, K. and Agathos, A., 2001. The point in polygon problem for arbitrary polygons. Computational Geometry, 20 (3), 131–144.10.1016/S0925-7721(01)00012-8
   Web of Science ®Google Scholar
• Hummel, S.F., Schonberg, E., and Flynn, L.E., 1992. Factoring: a method scheme for scheduling parallel loops. Communications of the ACM, 35, 90–101.10.1145/135226.135232
   Web of Science ®Google Scholar
• Jiménez, J.J., Feito, F.R., and Segura, R.J., 2009. A new hierarchical triangle-based point- in-polygon data structure. Computers & Geosciences, 35 (9), 1843–1853.
   Web of Science ®Google Scholar
• Khan, S.U., Bouvry, P., and Engel, T., 2010. Energy-efficient high-performance parallel and distributed computing. The Journal of Supercomputing, 60 (2), 163–164.
   Web of Science ®Google Scholar
• Lee, C.A., et al., 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.10.1109/JSTARS.2011.2162643
   Web of Science ®Google Scholar
• Li, H., et al., 1993. Locality and loop scheduling on NUMA multiprocessors. In: Proceedings of the 1993 International Conference on Parallel Processing, vol. 2, 140–147.10.1109/ICPP.1993.112
   Google Scholar
• Liao, S.B. and Bai, Y., 2009. A new grid-cell-based method for error evaluation of vector-to-raster conversion. Computational Geosciences, 14 (4), 539–549.
   Web of Science ®Google Scholar
• Meng, L.K., et al., 2007. An improved hilbert curve for parallel spatial data partitioning. Geo-spatial Information Science, 10 (4), 282–286.10.1007/s11806-007-0107-z
   Google Scholar
• Mineter, M.J., 2003. A software framework to create vector-topology in parallel GIS operations. International Journal of Geographical Information Science, 17 (3), 203–222.
   Web of Science ®Google Scholar
• Mineter, M.J. and Dowers, S., 1999. Parallel processing for geographical applications: a layered approach. Journal of Geographical Systems, 1 (1), 61–74.10.1007/s101090050005
   Google Scholar
• Phillips, R.D., Watson, L.T., and Wynne, R.H., 2007. Hybrid image classification and parameter selection using a shared memory parallel algorithm. Computers & Geosciences, 33 (7), 875–897.
   Web of Science ®Google Scholar
• Pineda, J., 1988. A parallel algorithm for polygon rasterization. Computer Graphics, 22 (4), 17–20.10.1145/378456
   Google Scholar
• Qin, C.Z., et al., 2014. A strategy for raster-based geocomputation under different parallel computing platforms. International Journal of Geographical Information Science, 28(11): 2127–2144. doi:10.1080/13658816.2014.911300.
   Web of Science ®Google Scholar
• Ren, F.H.,1989. Theory, method and application of geographical information system. Thesis (PhD). Peking University.
   Google Scholar
• Shekhar, S., et al., 1998. Declustering and load-balancing methods for parallelizing geographic information systems. IEEE Transactions on Knowledge and Data Engineering, 10 (4), 632–655.10.1109/69.706061
   Web of Science ®Google Scholar
• Sun, H.F. and Li, W.B., 2006. The improved algorithm for boundary algebra filling. Software Guide, 11, 64–66 (In Chinese with English abstract).
   Google Scholar
• Tang, G.P., et al., 2010. Application of a hybrid MPI/OpenMP approach for parallel groundwater model calibration using multi-core computers. Computers & Geosciences, 36 (11), 1451–1460.
   Web of Science ®Google Scholar
• Torrens, P.M., 2010. Geography and computational social science. GeoJournal, 75 (2), 133–148.10.1007/s10708-010-9361-y
   Google Scholar
• Tzen, T.H. and Ni, L.M., 1993. Trapezoid self-scheduling: A practical scheduling scheme for parallel compilers. IEEE Transactions on Parallel and Distributed Systems, 4 (1), 87–98.10.1109/71.205655
   Web of Science ®Google Scholar
• Wang, S.W., Cowles, M.K., and Armstrong, M.P., 2008. Grid computing of spatial statistics: using the TeraGrid for Gi*(d) analysis. Concurrency and Computation: Practice and Experience, 20 (14), 1697–1720.10.1002/cpe.v20:14
   Web of Science ®Google Scholar
• Wang, J. and Du, D.S., 2004. An improved algorithm for transferring vector to raster data. Geography and Geo-Information Science, 20 (1), 31–34 [In Chinese with English abstract].
   Google Scholar
• Wang, Y.F., et al., 2013. Parallel scanline algorithm for rapid rasterization of vector geographic data. Computers & Geosciences, 59, 31–40.
   Web of Science ®Google Scholar
• Xia, R.B. and Liu, W.J., 2006. Method for determining whether a certain point is inside a polygon in plane. Chinese Journal of Mechanical Engineering, 42 (3), 130–135 (In Chinese with English abstract).10.3901/JME.2006.03.130
   Google Scholar
• Xie, J.B., 2012. Implementation and performance optimization of a parallel contour line generation algorithm. Computers & Geosciences, 49, 21–28.
   Web of Science ®Google Scholar
• Yang, C.T., Cheng, K.W., and Shih, W.C., 2007. On development of an efficient parallel loop self-scheduling for grid computing environments. Parallel Computing, 33 (7–8), 467–487.10.1016/j.parco.2007.01.003
   Web of Science ®Google Scholar
• Yang, S., et al., 2010. A point-in-polygon method based on a quasi-closest point. Computers & Geosciences, 36 (2), 205–213.
   Web of Science ®Google Scholar
• Ye, J.Y., et al., 2011. A spatial data partition algorithm based on statistical cluster. Proceedings of 19th International Conference on Geoinformatics. Shanghai, China, 1–6.
   Google Scholar
• Yu, X., Yu, J., and McMillan, L., 2009. Towards multi-perspective rasterization. The Visual Computer, 25 (5–7), 549–557.10.1007/s00371-009-0335-3
   Web of Science ®Google Scholar
• Zhang, J.T., 2011. Speeding up large-scale geospatial polygon rasterization on GPGPUs. In: Proceedings of the ACM SIGSPATIAL Second International Workshop on High Performance and Distributed Geographic Information Systems, Chicago, USA, 10–17.
   Google Scholar
• Zhou, C.H., et al., 2007. An equal area conversion model for rasterization of vector polygons. Science in China Series D: Earth Science, 50 (S1), 169–175.10.1007/s11430-007-5013-6
   Google Scholar