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.
- Registered users only
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|
|Deposited On:||02 Dec 2008 11:07|
|Last Modified:||14 Jul 2014 12:52|
|Citations:||Web of Science®. Times Cited: 9|
Scopus®. Citation Count: 17
Users (please log in): suggest update or correction for this item
Repository Staff Only: item control page