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.
