Study On Parallel Computation Methods Of Automated Line Feature Generalization

Map generalization, as an important method to produce and update cartographic data, map feature extracting and visualization, is always a challenging issue in cartography and geographic information science. With the continuous deepening of applications in various fields of GIS, the technology of GIS data processing can’t meet the needs of digital spatial information age and the information society. One important aspect, the problem how to change the amount of information with the change of scale can’t be solved. The fundamental way to solve this problem is to achieve automatic map generalization. With the development of network technologies, the requirements on real-time, on-the-fly multi-scale geographic information services are increased. In order to achieve real-time data processing of massive geographic data, the efficiency of map generalization needs to be increased.Not only the method to improve the map generalization algorithms, but also the development of parallel computing provides a new method to improve the efficiency of map generalization.Line generalization, one of the most important fields of map generalization, is still a hot spot for experts and scholars after many years’ development because of the importance of line in map representation and in GIS analysis. However, there are many line features which have different data characteristics and the methods of map generalization are different. Above all, it’s essential to reseach on the methods of parallel computing of line generalization.Based on the reviewing the current theories and methods of line features generalization and the applications of parallel computing in map generalization, the paper analyzed the time complexity of some common line simplification algorithms.Then the paper analyzed the suitability of parallel computing of contour generalization based on existing data decomposition methods and proposed the data decomposition strategy of line features based on hierarchy. Baesd on the analysis of methods of contour generalization and data characteristics of contours, the data decomposition method of contours based on elevation zones was proposed. Finally,some experiments were carried on in the OpenMP and MPI parallel computing environment using some common line simplification and data decomposition method based on elevation zones.The experiments proved this data decomposition method is effective and proved the accuracy of time complexity analysis on these line simplification algorithms.The experiments also showed that the efficiency of line simplification algorithms can be increased in the OpenMP parallel computing environment,but in the MPI parallel computing environment something was different.The efficiency of those algorithms time complexity of which is O(n) was’t increased,but the efficiency of those algorithms time complexity of which is O(n2) was increased. The result also showed that the efficiency of the algorithm itself and the choice of parallel computing environment are closely linked and provided the basis for the realization of parallel computing of line generalization.