An efficient method of map generalization using topology partitioning and constraints recognition

Map Generalization is one of the most fundamental technologies for modern digital maps. It can effectively reduce the storage space and fit to different applications according to their scale requirement. This paper presents an efficient solution for this problem that won the ACM SIGSPATTAL CUP 2014. Given the original geometries which are represented by sampling points sequence, this method divides the boundaries into many small segments based on their topological characteristics and constriants. It attempts to minimize the number of sampling points by simplifying the given map and constraining points. In addition, the method also employs many optimization techniques to reduce the total latency, like memory pool, parallel computing and string parsing. Experimental results on real datasets demonstrate the effectiveness and efficiency of the proposed method.