Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

A Topology-Inferred Graph-Based Heuristic Algorithm for Map Simplification

Guo, QL and Karimi, HA (2016) A Topology-Inferred Graph-Based Heuristic Algorithm for Map Simplification. Transactions in GIS, 20 (5). 775 - 789. ISSN 1361-1682

[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)


In this article we present a heuristic map simplification algorithm based on a novel topology-inferred graph model. Compared with the existing algorithms, which only focus either on geometry simplification or on topological consistency, our algorithm simplifies the map composed of series of polylines and constraint points while maintaining the topological relationships in the map, maximizing the number of removal points, and minimizing error distance efficiently. Unlike some traditional geometry simplification algorithms, such as Douglas and Peucker's, which add points incrementally, we remove points sequentially based on a priority determined by heuristic functions. In the first stage, we build a graph to model the topology of points in the map from which we determine whether a point is removable or not. As map generalization is needed in different applications with different requirements, we present two heuristic functions to determine the priority of points removal for two different purposes: to save storage space and to reduce computation time. The time complexity of our algorithm is O(nlogk) which is efficient enough to be considered for real-time applications. Experiments on real maps were conducted and the results indicate that our algorithm produces high quality results; one heuristic function results in higher removal points saving storage space and the other improves the time performance significantly.


Social Networking:
Share |


Item Type: Article
Status: Published
CreatorsEmailPitt UsernameORCID
Guo, QLqig6@pitt.eduQIG6
Karimi, HAhkarimi@pitt.eduHKARIMI0000-0001-5331-5004
Date: 1 October 2016
Date Type: Publication
Journal or Publication Title: Transactions in GIS
Volume: 20
Number: 5
Page Range: 775 - 789
DOI or Unique Handle: 10.1111/tgis.12188
Schools and Programs: School of Information Sciences > Information Science
Refereed: Yes
ISSN: 1361-1682
Date Deposited: 26 Jun 2017 20:12
Last Modified: 30 Mar 2021 22:55


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item