2 
ISPRS, Vol.34, Part 2W2, “Dynamic and Mutti-Dimensional GIS", Bangkok, May 23-25, 2001 
ISPRS, Vol.34, I 
spatial characteristic, such as area size. Generally, through SQL 
conditional selection can delete some categories of building and 
remained building is equally of importance requiring other 
operation to solve conflicts. Displacement is valid just within 
relative large space. When scale changes largely, in limited 
space one displacement may result in new conflicts and it’s very 
hard to find an appropriate position for each building. 
Combination makes the conflict between original buildings 
disappear but increases the building size. Furthermore the 
conflict between new combined results still exist, unless all 
buildings having conflict to each other are combined to one big 
block. Single operation does not work for building cluster 
generalization. The valid strategy is executing both displacement 
and aggregation. (The independent simplification is necessary, 
however we do not consider it here for building cluster.) Two or 
more buildings moving together and aggregating into one, the 
conflict between them doe not exist, on the other hand, 
movement gives the contrary direction more room and the 
conflict between new just generated building and context 
neighbors may also be resolved. 
Some of constraints are contradict to each other in building 
generalization. The compromise strategy is to sacrifice each 
constraint partly, not respecting anyone completely. Spatial 
conflict removal is one of constraints and its solution has to 
consider maintenance of position accuracy, the whole area 
balance and Gestalt nature. The largest offset distance of 
displacement should be restricted within position accuracy. 
Generally, displacement can not guarantee two neighbor 
buildings seamlessly sharing one common boundary, still with 
gap fragment. So the aggregation result has the trend to 
increase area. Following independent simplification needs to 
consider this fact, and to perform operation preferring area 
reduction. 
The Gestalt nature is hard to maintain because of the difficulties 
of formally describing these cognition principles. We can 
psychologically feel some buildings with same size, same 
direction, same shape and other similar visual characteristics 
should be assigned to one group, but until now we can not find a 
model to represent spatial distribution pattern to identify the 
group. It depends on complex spatial relationship representation 
with the consideration of context environment, such as similarity 
relationship. For building cluster, when the difference of gap 
distance is distinct to each other, the grouping decision can be 
made on only distance computation. Otherwise there may be the 
case that all buildings within one street block has conflict 
distance to each other and needs to be classified as one group. 
In this situation, it is Gestalt nature rather than geometric 
distance that distinguish building group in cluster structure. 
3. PARTITIONING GEOMETRICAL CONSTRUCTION BASED 
ON DELAUNAY TRIANGULATION SKELETON 
Delaunay triangulation, which has the circumcircle principle and 
closest to equilateral properties (Preparata and Shamos ,1985) 
plays an important role in spatial adjacent relationship analysis 
and results in series of achievements related to spatial neighbor 
assessment. It can be applied to detect neighbor objects of one 
determinate object and to analyze the conflict between them 
(Jones etc.,1995, Ware etc., 1997). In spatial pattern recognition, 
Peng implements Delaunay triangulation model identifying 
islands lineal arrangement structure (Peng 1995). For polygon 
categorical map generalization, Bader and Weibel propose an 
approach of polygon combination by dividing small polygon 
equally along skeleton and blending two parts into neighbor 
polygons respectively(Bader and Weibel, 1997 ). Poorten and 
Jones (1999) develop a method of customisable line 
generalization using Delaunay triangulation. Ai(2000) constructs 
a binary tree on the basis of Delaunay triangulation to represent 
curve bend hierarchical structure. 
Building cluster distribution contains much information 
associated with adjacent relationship under context environment. 
Next we will use Delaunay triangulation constructing a special 
geometric construction to extract this kind of distribution 
structured information. 
3.1 Constructing Interpolated and Constrained Delaunay 
Triangulation 
When constructing Delaunay triangulation, all the building 
boundary must be forced to serve as edge of triangles, not 
intersecting with any triangles. This kind of triangulation is called 
constrained Delaunay triangulation(Jones,1995). The triangles in 
Delaunay triangulation (not constrained) network have the 
properties of “as equilateral as possible” avoiding the 
appearance of very narrow triangles and very sharp angles. It is 
this nature that makes the Delaunay triangulation a powerful 
model in spatial adjacency analysis. However, for constrained 
triangulation, the constrained condition destroys this nature. In 
the case of building cluster, some of boundary segments may be 
long and leads to triangles also inheriting the long edge. The 
constrained triangulation will not correctly detect adjacent 
relationship between objects as illustrated in Figure 1 top. To 
resolve the contradict, we apply a method of point-interpolation 
on long boundary edges. This method divides the long edge into 
several short segments and makes them respectively act as 
different triangle edge in triangulation network. In Figure 1, for 
the top graphic copied from(Ware,1997), the polygon boundary 
is not interpolated and object o 2 can not be identified having 
neighbor relation with object Oi. After the polygon boundary is 
interpolated as shown in the bottom graphic, the triangulation 
may correctly detect neighbor relationship between object o 2 and 
Oi. 
M 
'Z'/'i' 1 ' ' 
V V » x i \ f V M V 
Fig. 1. Directly constructing constrained Delaunay 
triangulation results in many very narrow triangles and 
can not find o 2 is the neighbor of Oi. After boundary 
being interpolated, the identification result is 
correct.(The top graphic is from Ware,1997b) 
A series of points add on building boundary edge in which 
interval distance between two points is longer than interpolation 
interval threshold w. Suppose the original building polygon 
boundary (Pi), when the length || PiP i+1 ||>w ,then the interpolation 
points {Q k } is computed as following: 
Xj+X k X, +1 Y,+X k Y i+1 
X k = , Y k = 
1 +X k 1 +X k 
where, 
k w 
X k = (k=1,2,3 ) 
|PiP i+ i|-kw 
To prepare for the next application, we define a data structure for 
triangle storage with consideration of the relation between 
building polygon and triangles: 
typedef structure TRI-TYPE 
{ int belong_to[3]; /* Polygon IDs on which three 
triangle vertex points locate 
int neighbor[3]; /* Three neighbor triangle IDs of 
the current triangle 
POINT barycenter, T The barycenter point of triangle; 
} 
The barycenter 
building or not 
this data structu 
building, outside 
outside buildinc 
respectively, 
3.2 Selecting ai 
We use the folk 
set (where t re| 
Select {tj 
¡(ti.be/onsr_f 
It removes two c 
One is those witl 
locating in one 
removal is to a\ 
the next partitio 
illustrates the se 
light grey and mi 
Fig. 2. Interestei 
For selected tri 
according to tf 
neighbor, two ni 
classified as typ 
type I triangle a 
triangle on the t 
type II distributin 
3.3 Creating I 
Triangle SI 1 
Skeleton connec 
in figure 3, when 
Type I 
Fig.3, Skeleton cc 
polygons, th< 
geometric cc 
(visualized as