anbul 2004 
eas once a 
resent such 
tes if deer 
this means 
ptured and 
model and 
ly flexible 
iverse and 
rian Forest 
rstand the 
- those of 
hat can be 
extend the 
/ to a more 
es (instead 
nth a set of 
(relational) 
scellancous 
king use of 
ons. 
Referenz. 
170-0 
fall in den 
t Lehrstuhl 
Universität 
An Oracle 
: Oracle 91 
cal White 
orstverwal- 
Windwurf 
y 2001 
elationalen 
ormations- 
nssysteme, 
ng Spatial 
An Oracle 
"om 
:ts/spatial/ 
ALGORITHMIC DEVELOPMENT OF AN OPTIMAL PATH COMPUTATION MODEL 
BASED ON TOPOGRAPHIC MAP FEATURES 
Mandy, Y.F. Tang*, Lilian, S.C. Pun-Cheng® 
Department of Land Surveying and Geo-Informatics 
The Hong Kong Polytechnic University 
Hunghom, Kowloon, Hong Kong 
"Isgi.mandyGpolyu.edu.hk , Plspun@polyu.cdu.hk 
KEYWORDS: GIS, Mapping, Modelling, Algorithms, Data Structures 
Commission PS, Working Group IV/1 
ABSTRACT: 
Path finding problems have attracted widespread research interests with different GIS-T applications such as Logistics applications, 
Infrastructure Planning and Travel Demand analysis. Previous researches have largely been conducted on developing shortest path 
algorithms in GIS. The conventional approach is to adopt the arc-node network model. For example, a road is represented by a 
centerline that is formed between the two road margins. The interconnection of these lines and their intersecting nodes will form a 
network ready for path finding and computation of relevant parameters. However, the generation and maintenance of a centerline 
network is difficult and tedious because these are not natural but imaginary features. Human judgment and manual digitization are 
essential and will differ between individual operators in the creation of these lines. To remedy the situation, an alternative approach 
is suggested that path finding method is independent of any arc-node data structure. The network model for such computation is 
solely based only on feature outlines as appeared on the topographic maps. In other words, outlines or symbology of relevant 
features for a certain path finding application like road margins, building outlines, subways will directly be used to model the path 
finding network. This paper will investigate the rationale and logistics to develop such a model first for pedestrian walking. A small 
set of digital map data from a very congested Hong Kong urban area will be used to evaluate the model reliability and efficiency. 
I. INTRODUCTION the road margins. Although many GIS software are intended to 
automate the process of creating the centerline, the result could 
be unsatisfactory when some sophisticated cases are met. 
Therefore, the generation of centerlines could be cumbersome 
and time consuming. 
The use of map features directly to perform path finding 
analysis provides an alternative method to replace the tedious 
generation of arc-node representations. Although there is no 
centerline shown on paper map, users can determine the 
accessible path based on both spatial features (e.g. vehicular 
road, walking path, buildings) and their descriptions (e.g. slope, 
stairs, turning directions) without the extra effort of generating 
another set of imaginable lines. Therefore, it should be possible 
to find a path with the use of base map features such as 
footbridge/elevated walkway, footpath, kerb line, pavement line, 
steps, subway and road/rail tunnel etc. provided in a digital map. 
This paper proposed an algorithm which is applied for a 
specific path-finding application — pedestrian walking. 
1.1 General Instructions 
With the development of geographical information systems 
(GIS) technology, network and transportation analyses within a 
GIS environment have become a common practice in many 
application areas. Many previous research studies focus on 
Geographical Information Systems for Transportation (GIS-T) 
have been published, including Vuren et al. (1987), Horowitz 
(1996), Sutton (1996), Zhan and Noon (1998), Kirkby et al. 
(1999), Chan and Yang (1999), Han et al. (2001) and Goodchild 
(2000). 
The most common and convenient way to represent a road 
network is the node-arc representation. Generally, nodes 
correspond to street intersections while arcs correspond to street 
segments between intersections. In many applications, network 
arcs so called road centerlines are digitized to lie between the 
centers of physical road margins. In order to support routing In this paper, we developed a prototype that can be used to 
application, all road centerlines should be snapped together to suggest walking paths for pedestrians with different scenarios 
form a connected road network. This connectivity property of of land feature configurations. Following the discussion of the 
node-arc representation of road network allows system to current approach for finding path for drivers in section two, the 
traverse through the network efficiently with the support of idea of using map features to find walking paths is introduced in 
section three, and the initial results are presented there. The 
discussion of these preliminary results, suggestions for further 
network data storage structure. 
However, road centerlines are not natural that can be found on work and conclusion are contained in the last section, section 
ground. Data — capturing techniques like surveying, four. 
photogrammetry and remote sensing are unlikely to capture this 
kind of data. It seems that manual digitization is one of the most 
common ways to generate the road centerlines to lie between 
57 
sheet pines 
aa 
=