Quick Search:

is currently disabled due to reindexing of the ZORA database. Please use Advanced Search.
uzh logo
Browse by:
bullet
bullet
bullet
bullet

Zurich Open Repository and Archive 

Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-6451

Yan , H; Weibel, Robert (2008). An algorithm for point cluster generalization based on the Voronoi diagram. Computers & Geosciences, 34(8):939-954.

[img] PDF - Registered users only
1MB

Abstract

This paper presents an algorithm for point cluster generalization. Four types of information, i.e. statistical, thematic, topological, and metric information are considered, and measures are selected to describe corresponding types of information quantitatively in the algorithm, i.e. the number of points for statistical information, the importance value for thematic information, the Voronoi neighbors for topological information, and the distribution range and relative local density for metric information. Based on these measures, an algorithm for point cluster generalization is developed. Firstly, point clusters are triangulated and a border polygon of the point clusters is obtained. By the border polygon, some pseudo points are added to the original point clusters to form a new point set and a range polygon that encloses all original points is constructed. Secondly, the Voronoi polygons of the new point set are computed in order to obtain the so-called relative
local density of each point. Further, the selection probability of each point is computed using its relative local density and importance value, and then mark those will-be-deleted points as ‘deleted’ according to their selection probabilities and Voronoi neighboring relations. Thirdly, if the number of retained points does not satisfy that computed by the Radical Law, physically delete the points marked as ‘deleted’ forming a new point set, and the second step is repeated; else physically deleted pseudo points and the points marked as ‘deleted’, and the generalized point clusters are achieved. Owing to the use of the Voronoi diagram the algorithm is parameter free and fully automatic. As our experiments show, it can be used in the generalization of point features arranged in clusters such as thematic dot maps and control points on cartographic maps.

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Geography
DDC:910 Geography & travel
Uncontrolled Keywords:Point clusters; Map generalization; Measures; Algorithms; Voronoi diagrams
Language:English
Date:August 2008
Deposited On:02 Dec 2008 11:07
Last Modified:14 Jul 2014 12:52
Publisher:Elsevier
ISSN:0098-3004
Publisher DOI:10.1016/j.cageo.2007.07.008
Citations:Web of Science®. Times Cited: 8
Google Scholar™
Scopus®. Citation Count: 16

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page