Header

UZH-Logo

Maintenance Infos

Real-time generalization of point data in mobile and web mapping using quadtrees


Bereuter, Pia; Weibel, Robert (2013). Real-time generalization of point data in mobile and web mapping using quadtrees. Cartography and Geographic Information Science, 40(4):271-281.

Abstract

With a focus on mobile and web mapping, we propose several algorithms for on-the-fly generalization of point data, such as points of interest (POIs) or large point collections. In order to achieve real-time performance we use a quadtree data structure. With their hierarchical subdivision structure and progressive levels of detail, indices of the quadtree family lend themselves as auxiliary data structures to support algorithms for generalization operations, including selection, simplification, aggregation, and displace-ment of point data. The spatial index can further be used to generate several local and global measures that can then serve to make educated guesses on the density and prox-imity of points across map scales, and thus enable control of the operation of the general-ization algorithms. An implementation of the proposed algorithms has shown that thanks to the quadtree index, real-time performance can be achieved even for large point sets. Furthermore, the quadtree data structure can be extended into a caching structure, which can be used to store pre-computed generalizations; thus, a desired level of detail can simply be retrieved from cache.

Abstract

With a focus on mobile and web mapping, we propose several algorithms for on-the-fly generalization of point data, such as points of interest (POIs) or large point collections. In order to achieve real-time performance we use a quadtree data structure. With their hierarchical subdivision structure and progressive levels of detail, indices of the quadtree family lend themselves as auxiliary data structures to support algorithms for generalization operations, including selection, simplification, aggregation, and displace-ment of point data. The spatial index can further be used to generate several local and global measures that can then serve to make educated guesses on the density and prox-imity of points across map scales, and thus enable control of the operation of the general-ization algorithms. An implementation of the proposed algorithms has shown that thanks to the quadtree index, real-time performance can be achieved even for large point sets. Furthermore, the quadtree data structure can be extended into a caching structure, which can be used to store pre-computed generalizations; thus, a desired level of detail can simply be retrieved from cache.

Statistics

Citations

7 citations in Web of Science®
17 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

146 downloads since deposited on 13 Jan 2014
46 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Language:English
Date:2013
Deposited On:13 Jan 2014 16:31
Last Modified:05 Apr 2016 17:21
Publisher:Taylor & Francis
ISSN:1523-0406
Publisher DOI:https://doi.org/10.1080/15230406.2013.779779

Download

Download PDF  'Real-time generalization of point data in mobile and web mapping using quadtrees'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 571kB
View at publisher