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)

Abstract

© 2015 John Wiley & Sons Ltd 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.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Guo, QLqig6@pitt.eduQIG6
Karimi, HAhkarimi@pitt.eduHKARIMI
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: 17 Oct 2017 21:55
URI: http://d-scholarship.pitt.edu/id/eprint/32483

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item