An approach to simplifying point features on maps using the multiplicative weighted Voronoi diagram

摘要

A number of features, such as settlements and islands, are represented using point symbols on intermediate and micro scale maps. If the maps are reduced to smaller scale, the point features need to be simplified to make the maps legible. Hence, it is necessary to develop algorithms for point feature generalisation. For the reason above, an algorithm based on the multiplicatively weighted Voronoi diagram (MWVD) is proposed in the paper. To ensure statistical, thematic, metric and topological information contained in the original point features can be transmitted correctly after simplification, the algorithm selects corresponding measures (i.e. the number of points, weight, Voronoi neighbour, Voronoi polygon and distribution range) to quantify the four types of information, and integrates the measures in the process of point feature generalisation. First, the algorithm detects the range polygon of the given point features; second, it adds the pseudo points (i.e. the vertices of the range polygon) to the original points to form a new point set and tessellates the new point set to get the MWVD; then it computes the selection probability of each point using the area of each Voronoi polygon, and sorts all points in decreasing order by their selection probability values; after this, it marks those to-be-deleted points as 'deleted' according to their selection probability values and their Voronoi neighbouring relations, and determines if they can be physically deleted. Finally, the algorithm is ended by comparing the number of points retained on the map with that computed by the Radical Law. The algorithm is parameter-free, automatic and easy to understand, owing to the use of the MWVD. As the experiments show, it can be used in simplification of point features arranged in clusters, such as settlements, islands and control points on topographic maps at intermediate/ micro scale.