ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
3 
Constrained Delaunay 
ation, all the building 
edge of triangles, not 
of triangulation is called 
s,1995). The triangles in 
Bd) network have the 
oossible” avoiding the 
I very sharp angles. It is 
triangulation a powerful 
iwever, for constrained 
destroys this nature. In 
ndary segments may be 
ing the long edge. The 
rectly detect adjacent 
ted in Figure 1 top. To 
od of point-interpolation 
vides the long edge into 
em respectively act as 
etwork. In Figure 1, for 
i, the polygon boundary 
lot be identified having 
ie polygon boundary is 
'aphic, the triangulation 
p between object 02 and 
ained Delaunay 
aw triangles and 
After boundary 
tion result is 
997b) 
iundary edge in which 
onger than interpolation 
iginal building polygon 
w ,then the interpolation 
(fine a data structure for 
the relation between 
in IDs on which three 
jle vertex points locate 
aeighbor triangle IDs of 
urrent triangle 
center point of triangle; 
The barycenter contributes to decide whether triangle is within 
building or not through point-in-polygon judgement. Based on 
this data structure we can select triangle sub-sets locating within 
building, outside building and connecting two or three buildings, 
outside building and only in one building’s concave parts 
respectively, 
3.2 Selecting and Classifying Interested Triangles 
edge, and O the triangle barycenter. Linking skeleton segment 
by means of next paths and through polygon topological 
organization, we obtain the special geometric construction as 
illustrated in Figure 4. 
Type I A ->P, or Pi—>A 
Type II Pi-^P 2 or P 2 -»Pi 
Type III 0->Pi or P,->0, ¡=1,2,3 
We use the following query statement to get interested triangle 
set (where t represents one triangle.): 
Select {tj} from AII_Triangles where 
\(\ t .belong_to{0] == \ l .belong__tc['\] == t,.belongJc{2]) 
It removes two categories of triangle from the whole triangle set. 
One is those within building polygon, another outside building but 
locating in one building’s concave region. The reason of latter 
removal is to avoid appearance of dangle skeleton branch in 
the next partitioning geometric construction creating. Figure 2 
illustrates the selected triangles between buildings, shaded with 
light grey and marked with Rome number. 
This geometric construction looks like Voronoi diagram(VD). But 
according to strict definition of VD (Shoms 1985), it is not 
Voronoi diagram. VD cell is convex polygon, while the 
partitioning polygon of this geometric construction may be 
concave. VD network is originally point cluster oriented. For 
polygon cluster, it is difficult to define VD, but just from the 
viewpoint of GIS application, considering properties of space 
partitioning equally, it is feasible to borrow Voronoi name and call 
this construction as polygon cluster’s VD. 
Rather than construction name calling, what we are interested is 
its properties as follows: 
i>. Each partitioning polygon contains one building; 
ii>. Each node relates three skeleton edge; 
iii>.Each edge of partitioning polygon boundary faces to a left 
building and a right building, separating two buildings equally in 
space; 
iv>. If the number of type I, type II, type III triangle is ni,n 2 ,n 3 
respectively, then the node number is ^+3^, and the edge 
number (nr^na)/^; 
Fig. 2. Interested triangles selection and their type assignment 
For selected triangle set, we assign them into three types 
according to the number of neighbors. Those having one 
neighbor, two neighbors and three neighbors are respectively 
classified as type I, type II and type III. As shown in Figure 2, 
type I triangle appears on the exit of building cluster, type III 
triangle on the region of three buildings meeting together, and 
type II distributing around the gap area between two buildings. 
3.3 Creating Building Partitioning Polygon Based on 
Triangle Skeleton 
Skeleton connection way for three types of triangle is described 
in figure 3, where Pi,P 2 ,P 3 the midpoint of corresponding triangle 
A*-— 
Type I Type II Type III 
Fig.3, Skeleton connection ways for three types of triangle. 
Property i,ii,iii is except for the border area of building cluster. 
Property iii has problem for the case of concave building, for 
example of building A, B in Figure 4. As triangles locating in 
concave part have been removed in previous selection process, 
the skeleton is no long to separate space equally between 
concave building and its neighbor building. It means some of 
outside concave area is also regarded as belonging to building. 
But for such as building B in figure 4, not filling “U” formed mouth 
is difficult to describe equal partitioning. It is same for the method 
of raster operation to get polygon cluster VD. This is the reason 
why we do not directly use skeleton based on all triangle outside 
building to get this kind of geometric construction. 
The partitioning polygon can be thought of as the growth region 
of corresponding building, covering the whole area with neither 
gap nor overlapped region. We can understand it is the result of 
each building competing outward for growth range and this 
competition has considered context impact. In this sense, we 
can say each building has two representation in cluster coverage. 
Next we call building polygon OP (Object Polygon), and 
partitioning polygon GP(Growth Polygon). The relationship 
analysis of OP to each other can be transformed to that of GP 
instead. 
E• 11 .viSfaUijj 
Fig.4. Based on the part of triangles between building 
polygons, the skeleton connection gets a special 
geometric construction similar to Voronoi diagram 
(visualized as wide dark line ). 
To describe topological and geometric aspects, We define the 
following data structure for GP edge storage: 
typedef struct SKELETON_ TYPE 
{ long LObject; II Left Building 
long RObject; II Right building; 
POINT *pt; //Coordinate string 
long ptNum; II Coordinate point number 
double Width; II Weighted width between L R object 
double Min Width; II Minimum width between L R object; 
long FromNode; // Related start node; 
long ToNode; //Related terminal node. 
3.4 Parameter Computation 
Based on the relationship of GP to each other and the 
relationship between GP and OP, some useful geometric 
parameters can be computed.