AN ALGORITHM FOR BUILDING FULL TOPOLOGY 
Chaoying HE'?, Jie JJANG?, Gang HAN?, Jun CHEN? 
'College of Remote Sensing and Information Engineering, Wuhan University, Wuhan, China 430079, 
hechying@hotmail.com 
2National Geomatics Center of China, 1 Baishengcun, Zizhuyuan, Beijing, China, 100044 
(jjie! Ihangang, chenjun) @nsdi.gov.cn 
KEY WORDS: Navigation, Databases, Algorithms, Full Topology, ITS 
ABSTRACT 
Traditional polygon-arc-node topological relationships (TRs) is standard in vector GIS. That has been explicitly represented by many 
commercial GIS systems. In the case of Intelligent Transportation System (ITS), a full topology is defined by an international 
standard with which road network data are topologically structured. One important part of ITS application is place searching and path 
finding that is based on the connectivity of road segments and TRs between road segments and certain area features, such as zoos. 
Therefore, we need to construct arc-node topology to record From-Node and End-Node of one edge, node-arc topology to record 
edges at the node, and ‘special’ area topology. The former two are similar to the definition in the past, but the last one is different. 
Since the required topologies in ITS application are different from that of the traditional methods, the required algorithm is different. 
Based on the analysis of the requirements and characteristics of ITS application, the present paper proposes an algorithm for building 
the topological relationships between spatial objects in road network. Compared with other methods, the topologies defined in this 
paper can describe TRs between spatial objects in road network more accurately; the present algorithm is simplified and more 
efficient. Experiments demonstrate that the efficiency of the proposed algorithm is improved by 150% in contrast with other methods. 
1. INTRODUCTION In ITS applications, one of the most important functions is place 
searching and path finding. For example (Fig.l), one person 
The term “topology” has been used in GIS to describe one kind of : : i à : : Louk 
wants to drive from National Geomatics Center of China 
spatial relationships among spatial objects, which might be tee, ete 
(NGCC, point A) to Beijing Zoo (area M) and he doesn't know 
expressed as O-dimension (nodes), 1-dimension (ares) or : : i 
where the Zoo is. In this case, he must at first search for the 
2-dimension (polygons) (Chrisopher M. Gold, 1994). In general ( ee 
(pos ; p e location of Beijing Zoo, and then seek the road segments that are 
GIS topological data model, such as the one used in ARC/INFO, : 
adjacent to M, and then find out the access to the Zoo along the 
one of the most popular GIS software, people build topological . ; : ; ; : 
pop peop polog road segments. In fig.1, point P is one of the enter point of the 
relationships (TRs) between nodes and edges, as well as TRs = : 
pet ) e Zoo. Then, he should find a shortest route between A and P in the 
between edges and polygons. This kind of TRs, which we called | 
given road network. 
as traditional TRs, can meet most of the requirements in GIS 
applications. However, in certain application, such traditional 
TRs are not always totally applicable. For example, in Intelligent 
Transportation System (ITS), owing to the characteristics of such 
application, the TRs between edges and polygons are not always 
necessary. So different TRs need to be built in ITS field (Jie 
JIANG, 2003). 
10