y many 
ational 
nd path 
IS ZOOS. 
record 
fferent. 
fferent. 
uilding 
| in this 
d more 
ethods. 
s place 
person 
China 
t know 
for the 
that are 
ong the 
t of the 
P in the 
International Archives of the Photogrammetry, Remote Sensing an 
   
\ 
wy 1 Tn 
n ig" A ai a 2 - 
1 T 
i Mr. qi 
| A 
i 
FIFRA i Beijing Zoo 
jh à = i * 
MM I. D. & lerne n 
NGCC Trt] 
WA | 1 
[5 3 a di fist S00. 
m 5 
y 1H 
SEER Frees 
alien an. as rte 
ue 
  
th 1 
| xr 
Fig. 1 An example of path finding 
In this process, two kinds of relationships between spatial objects 
will be used. One is the adjacency between road segments and the 
Zoo (M), which are used to find the road segments around the 
Zoo. The other is the connectivity of road segments in the road 
network, which is used to calculate the shortest route between A 
and P. As we describe in section 3, these relationships can be 
represented as 'special' area topology, arc-node topology, and 
node-arc topology in ITS application. “Special” area topology in 
this definition is different from the traditional TRs. It records the 
TRs between some area features and the around road segments 
rather than the TRs between area features and all their boundaries. 
Moreover, topological relationships in ITS application need to be 
constructed fast and automatically. The traditional methods, 
which are time-consuming and inefficient, cannot satisfy these 
requirements. In a word, the traditional TRs haven't considered 
the characteristics of ITS application and they don't suit for ITS 
applications very well. Therefore, we should study the specific 
topological relationships in ITS application and find out efficient 
algorithm to build topological relationships fast and 
automatically. 
The rest of the paper is structured as below. In section 2, the 
traditional methods for building topological relationships and the 
limitation of such methods are introduced. The third and forth 
section expounds the topologically structured data model and the 
algorithm for building full topology. The experiments and 
corresponding results are given in section 5. The sixth section is 
the summary. 
d Spatial Information Sciences, Vol XXXV, Part B-YF. Istanbul 2004 
2. TRADITIONAL METHODS FOR BUILDING 
TOPOLOGY 
It's well known that TRs can facilitate spatial query, error 
detection, and produce valuable derived statistics for revealing 
graph or surface properties (Mark, Egenhofer, 1995; Kimfung Liu, 
Wenzhong Shi, 2003). In the past years, two key issue related to 
TRs, which are topological data model and algorithm for building 
topology, have been discussed widely. On the one hand, many 
topological data models have been developed and applied, such as 
DIME model of the US Census Bureau for the 1970 census, 
POLYVRT structure used by the ODYSSEY system of Harvard 
University, and ARC/INFO topological data model (Laurini 
Robert, Thompson Derek, 1992). In these models, topological 
relations are generally recorded and stored in a tabular format. 
For example, ARC/INFO defines different feature attribute tables, 
such as PAT, AAT, NAT, TAT, to describe TRs of different 
features, namely polygon, line, point, node and annotation. 
Generally speaking, these models are related to certain 
application fields (Ayse Can, 1996; Michael J. Mineter, 2003; 
Serafino Cicerone, Eliseo Clementini, 2003; S. Dowers, B. M. 
Gittings and M. J. Mineter, 2000), that is, different application 
has different topological data models. On the other hand, 
traditional algorithms for building topology can be divided into 
three kinds. The earliest method for creating topology tables 
depends on manual edits during the process of digitizing (LI LIN, 
1987). It often appears excessively labor consuming and tedious. 
With the development of computer technology, researchers begin 
to make a study of a half-automatic method. They proposed to 
figure out topological relations from line intersection 
computation, which release people from the heavy and dull job. 
However, such methods cannot, by themselves, handle islands or 
self-intersecting arcs (Gold et al., 1994). Subsequently, Gold 
proposed an approach based on voronoi diagram to generate the 
adjacency relationships between each atomic element of the map. 
Although it also has the ability to extract the traditional 
polygon-arc-node topology, it contains an excess of information 
and its storage requirements almost several times larger than for 
the previous methods (Gold et al, 1991, 1994). Moreover, 
whichever method described above consider the boundaries of the 
area features when building the polygon topology. If we adopted 
such methods in ITS application, we would need another table 
besides the traditional polygon-arc-node topology to represent the 
relationship between road and area features because the 
11