A Constrained Delaunay Partitioning of Areal Objects to Support Map Generalization

Map generalization has to consider the map object properties in geometrical, topological and semantic aspects. It also needs special supporting data model to represent these characteristics of both objects and their relations. With respect to the generalization of polygon objects, this paper presents a method of Delaunay TIN partitioning in two-dimensional space. The constructed structure involves the description of polygon loop, islands, boundary and vertexes, and so can retrieve kinds of interesting region composed of partitioning triangles through formalizing selection, such as the concave part of one polygon, the adjacent area between polygons, the inside area between one island and outside boundary within one polygon etc. Compared with SDS model built by Buntly,Ware and Jones, this model is more complete in describing graphic elements, and the formalization selection strategy makes the operator algorithm built on the model more direct and easier to design. This data structure can be used to support such operations as finding neighbor polygons, identifying bend parts of polygon, detecting conflict region between polygons and merging polygon group. As the extracted skeleton line from Delaunay TIN contains a little of information supporting map generalization, the paper discusses an approach of generating center-lines based on Delaunay TIN in detail. The offered approach distinguishes the triangles into three types according to the number of each triangle with neighbor triangles. For each type of triangles, a skeleton line link way is provided as well as width representation. Depending on the distribution of different types of triangle, the skeleton structure could be tree structure or graph structure. The skeleton graph has some properties similar to Voronoi diagram in space separating equally. But the cell polygons are not convex polygons. The tree structure has the characteristic that each node has three extending branches. After investigating the relation between polygon and skeleton, the paper presents a model to describe polygon shape which is regarded as a buffer with changing width on the basis of buffer polygon differential ideals. (). According to this model, the skeleton extracting process could be regarded as the inverse of buffer generating which is a popular spatial analysis operator in most GIS software. Furthermore, the paper analyzes the width computation of polygon buffer which is related to skeleton line, including the width of one determinate location and the mean width of the whole buffer polygon. Skeleton lines can play important supporting roles in fields of single river axis conversion, street center-line network construction, neighbor building polygon detection and area object annotation location. Some of the above applications are illustrated in the paper with experimental result. Among them, the approach of using simulated Voronoi diagram to represent and assess building group is very interested and useful. This study can be applied to building density analysis, building adjacent distance and direction analysis in urban map generalization. Based on this method, Regnauld's MST model for building cluster generalization is able to be improved in adjacent distance computation.