Keywords: 
• automatic map generalization /
• building polygon /
• convex hull /
• polygon aggregation /
• polygon simplification

Abstract: This paper discusses the algorithm of polygon automatic generalization under digital environment and takes into account the orthogonal characteristics of urban building. Two kinds of spatial relations which are topological neighbor relation and visual neighbor relation are distinguished, and the corresponding aggregation methods are presented on the basis of vector and raster data structure. A method of clipping and extending are links is used to aggregate polygons with shared arcs. In contrast to traditional aggregation approach, this method need not to organize arc link sequence and not to detect polygon islands using other steps. For disjoint Polygons, the paper presents an aggregation method including six steps: finding MBR(minimum bounding rectangle), rasterizing, scanning and filling line grid based on distance tolerance, scanning and filling column grid, vectorizing and simplifing edges, and rotating to original direction. The process is based on raster conversion and grid extending performance. Two perpendicular directions related to MBR serve as extending directions and this strategy conserves rectangle geometric properties of right angle. The presented method fills the gap area between buildings with consideration of gap distance and this tolerance could be adjusted. As for the simplification of building shape, the paper proposes the approach of rectangle differential model according to building inner component structure. Algorithm ideas come from the suppose that building polygon was composed of rectangles. Through separation, the building polygon can be represented by a series of rectangles with different hierarchical levels. This kind of divide-and-conquer analysis is popular in computation geometry and shape analysis. Without strict theory testifying, but it is useful in realistic application of building simplification. The shape simplification procedure based on hierarchical rectangle differential method builds the relation between rectangle component state and generalization result with some resolutions. On the basis of bounding rectangle, the building polygon is separated as a rectangle extracting several concave part polygons that locate in the corner or on the edge. The author developes an experiment system to generalize urban buildings and the test result is illustrated in the paper. In the algorithm experiment, the building candidates to be merged are decided by manual interactive operation. But how to aggregate is conducted by program automatically. So the above method resolves the how question but not when, where question in urban building generalization. As for the generalization constraints, the method mainly takes into account the shape structure conservation.