Header

UZH-Logo

Maintenance Infos

Algorithms for on-the-fly generalization of point data using quadtrees


Bereuter, Pia; Weibel, Robert (2012). Algorithms for on-the-fly generalization of point data using quadtrees. In: The 2012 AutoCarto International Symposium on Automated Cartography, Columbus, Ohio, USA, 16 September 2012 - 18 September 2012, online.

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. With their hierarchical structure and progressive levels of detail, indexes of the quadtree family lend themselves as auxiliary data structures to support algorithms for generalization operations, including selection, simplification, aggregation, and displacement of point data. The spatial index can further be used to generate several measures on the relative point position and proximity of points, neighborhood, clusters, local and global density, etc. Using the tiles of the tree structure, such measures can be efficiently generated and updated. These measures can then serve to make educated guesses on the density and proximity of points across a series of map scales, and thus enable to control the operation of the generalization 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 storage structure, which can be used to store pre-computed generalizations; thus, a desired level of detail can simply be retrieved from storage.

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. With their hierarchical structure and progressive levels of detail, indexes of the quadtree family lend themselves as auxiliary data structures to support algorithms for generalization operations, including selection, simplification, aggregation, and displacement of point data. The spatial index can further be used to generate several measures on the relative point position and proximity of points, neighborhood, clusters, local and global density, etc. Using the tiles of the tree structure, such measures can be efficiently generated and updated. These measures can then serve to make educated guesses on the density and proximity of points across a series of map scales, and thus enable to control the operation of the generalization 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 storage structure, which can be used to store pre-computed generalizations; thus, a desired level of detail can simply be retrieved from storage.

Statistics

Downloads

272 downloads since deposited on 20 Feb 2013
53 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), not refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Language:English
Event End Date:18 September 2012
Deposited On:20 Feb 2013 17:15
Last Modified:05 Apr 2016 16:34
Official URL:http://www.cartogis.org/docs/proceedings/2012/Bereuter_Weibel_AutoCarto2012.pdf

Download

Preview Icon on Download
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 3MB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations