International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
2. NETWORK DATA MODEL 
GIS provides users powerful tool to store, present and analyze 
geographical data digitally. In tradition, spatial data are 
presented on a paper map with the use of lines, symbols and 
color. But in GIS, spatial information have to be geometrically 
and semantically stored in a spatial database. The vector format 
is by far considered as an easily understood way of storing a 
feature semantically as it is. 
Traditionally, vector representation has also been the domain of 
the network analysis in GIS. The linear network model is 
normally defined as a graph G, where G — (N, A) consists of (1) 
a finite set N ^ (nj, nj ... , nj, whose elements are called 
nodes and (ii) a subset A of the Cartesian product A x A, the 
elements of which are called arcs. These two primitives: nodes 
and arcs represent the intersections and segments respectively 
in a continuous and connected linear network. Due to the 
connectivity property of the vector network, the complexities 
such as costs, distance, and time can be incorporated in the 
model easily. In the following discussions, road network will be 
specifically used for explanation because of its popularity in 
network application. 
The conventional arc-node model is common and widely 
utilized to model the complexity of network elements in a 
logical way. The reason is clear. In a road network, arcs 
correspond to road segments that are the conduits for 
transportation and nodes correspond to road intersection 
connecting arcs together. This means, a connected network is 
consequently resulted to depict the complexities (such as turns, 
restrictions and lane information) of transport system no matter 
how sophisticated it is. Since the connectivity relationship of 
arcs and nodes and turn restrictions are implemented in 
attributes tables and turn table respectively, the optimum path 
between a source and destination(s) can be derived easily by 
traversing the topology of road network. It is just like 
performing a "search" operation in a branching tree with a 
parent root (the source) and corresponding child nodes 
(possibilities of destinations). 
2.4 Problems Raised by Conventional Arc-Node Data 
Model 
As stated in the beginning of this paper, the road centerline is 
an "abstract feature" to represent a road network. Therefore, 
generating road centerlines or developing the node-arc data 
model for network analysis are both important and difficult. It 
is important because road centerlines seem to be an essential 
element of a transportation network as discussed above; it is 
difficult because it involves tedious digitizing work. Although 
centerline mapping technologies are evolving rapidly, from 
traditional map digitizing to GPS, photogrammetry and remote 
sensing, each technology is associated with a performance 
range in terms of accuracy or resolution. There are many ways 
to model the transport system. Different definitions of roads, 
quality requirements or criteria make it difficult to have a 
consistent representation of transportation system. According to 
Dueker and Butler (2000), there are several GIS data models 
used for transportation applications. Prominent examples 
include Geographic Data File Standard (GDF), National 
Cooperative Highway Research Program 20-27 (NCHRP) and 
Dueker and Butler's enterprise GIS-T data model have been 
developed for transportation. However, these kinds of 
specifications do not lead to consistency due to their definitions 
and criteria differ. 
Besides, the maintenance of a road centerline is hard. lt is 
because the geometry and position of centerline are determined 
by the physical geometry of a road shown on a base map. The 
changes of physical geometry imply the changes of road 
centerline geometry and its related non-spatial attribute data. 
These may include node and arc identifiers, impedances and 
turns etc. Also, the existing arc-node representation of the road 
network results in a huge volume of data model. Especially in a 
planar network, the enforcement of a node at every intersection 
not only generates more turn possibilities at each junction, but 
also creates more arcs and nodes in the network. Take Hong 
Kong such a small territory as an example, its planar network 
consists of about 40,000 arcs and 30,000 nodes, with as many 
as 200,000 turn possibilities. Clearly, substantial amount of 
time are required for data input, preparation and validation in 
order to maintain a good quality road network and its associated 
attribute data. 
In addition, the planarity of network does not represent well the 
real world properties of transportation networks that contain 
features such as “underpass” and “overpass” (Miller and Shaw 
2001). Placing an additional node as under- or over-pass 
introduces a possibility of turning off the highway which does 
not make any sense in the real situation. To restrict those 
unrealistic turns, it can be done by assigning infinity impedance 
in turntable. However, this approach is an inefficient 
workaround. 
With no doubt, data collection and maintenance are always the 
most expensive parts of a fully operational GIS. They could 
account for 60%-80% of the total cost in terms of time and 
money of a GIS project (Longley et al., 1999). Hence, the most 
convenient and efficient way to perform GIS analysis is to use 
the existing and already well-defined base map features directly, 
without attempting to generate a new supplementary data set for 
particular purpose. To accomplish this, it is assumed that digital 
map features are organized systematically with clear definition. 
Associated with user-specified application requirements, these 
map features are supposed to be sufficient enough to support 
several kinds of application. The following section provides an 
illustrative example of finding paths for pedestrians. 
3. FINDING WALKING PATHS FOR PEDESTRIANS 
As mentioned previously, path finding might alternatively be 
computed based on both user-defined relevat spatial features 
(c.g. vehicular road, walking path, buildings) of any geometry 
and their descriptions (e.g. stairs, turning directions) without the 
concept of using the road centerline on either a paper or digital 
map. Figure 1 illustrates an example of a digital base map and 
its organization/modeling of features in an associated database. 
The data structure is simply a product of any national or 
regional mapping agency, for no peculiar application. However, 
from users’ understanding of a map, they may define the type(s) 
of features and attributes relevant to path finding. These will 
then form the basis for further computation as described next. 
Intern 
  
Fei 
Stree 
Buildii 
[ 
(Bridg 
Crossi 
R 
  
It is cl 
linear 
suppos 
stairs, « 
zebra « 
layer i 
moven 
steps, 1 
moven 
second 
betwee 
bridges 
street b 
P: 
et 
a 
  
pe 
i 
Figure ‘