First image
Previous image

Next image
Last image
Show double pages

Use the mouse to select the image area you want to share.

Please select which information should be copied to the clipboard by clicking on the link:

Link to the viewer page with highlighted frame
Link to IIIF image fragment

The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics

Access restriction

There is no access restriction for this record.

Copyright

CC BY: Attribution 4.0 International. You can find more information here.

Search in

Bibliographic data

fullscreen: The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics

Monograph

Persistent identifier:: 856566209

Author:: Chen, Jun

Title:: The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics

Sub title:: May 23 - 25, 2001, Bangkok, Thailand

Scope:: VI, 434 Seiten

Year of publication:: 2001

Place of publication:: Pathumthani, Thailand

Publisher of the original:: AIT

Identifier (digital):: 856566209

Illustration:: Illustrationen, Diagramme, Karten

Language:: English

Usage licence:: Attribution 4.0 International (CC BY 4.0)

Publisher of the digital copy:: Technische Informationsbibliothek Hannover

Place of publication of the digital copy:: Hannover

Year of publication of the original:: 2016

Document type:: Monograph

Collection:: Earth sciences

Chapter

Title:: OPTIMIZING PATH FINDING IN VEHICLE NAVIGATION CONSIDERING TURN PENALTIES AND PROHIBITIONS. Gang HAN, Jie JANG, Jun CHEN

Document type:: Monograph

Structure type:: Chapter

Contents

Table of contents

The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Cover
ColorChart
Title page
PREFACE
Conference Venue
CONTENTS
DISTRIBUTION ANALYSIS AND AUTOMATIC GENERALIZATION OF URBAN BUILDING CLUSTER. Tinghua AI
GENERALIZATION FOR 3D GIS. Fengwen BAI, Xiaoyong CHEN
USING IKONOS HIGH RESOLUTION REMOTE SENSING DATA FOR LAND USE CLASSIFICATION IN CHINA. Georg BARETH
LARGE SCALE GIS FOR A SUBURBAN TOWNSHIP OF BEIJING TO MODEL STRATEGIES FOR SUSTAINABLE AGRICULTURE ON FIELD LEVEL. Georg BARETH, Si JIN, Tailai YAN and Reiner DOLUSCHITZ
THREE LEVEL HIERARCHICAL QUALITATIVE DESCRIPTIONS FOR DIRECTIONS OF SPATIAL OBJECTS. Han CAO, Jun CHEN, Daosheng Du
THE APPLICATION OF CENTROGRAPHIC ANALYSIS TO THE STUDY OF THE INTRA-URBAN MIGRATORY PHENOMENON IN THE GREATER MONCTON AREA IN CANADA, 1981-1996. Huhua CAO
PER-FIELD CLASSIFICATION INTEGRATING VERY FINE SPATIAL RESOLUTION SATELLITE IMAGERY WITH TOPOGRAPHIC DATA. Mauro CAPRIOLI, Eufemia TARANTINO
INTEGRATION OF GIS WITH PESTICIDES LOSSES RUNOFF MODEL. Bing CHEN, Gordon HUANG, Jonathan LI, Yueren LI, and Yifan LI
RESEARCH ON 3D CITY VISUALIZATION BASED ON INTERNET. Jing CHEN, Qingquan Ll, Jianya GONG, Bisheng YANG
DYNAMIC AND MULTI-DIMENSIONAL GIS: AN OVERVIEW. Jun CHEN, Zhilin LI, Jie JIANG
A GIS-SUPPORTED ENVIRONMENTAL RISK ASSESSMENT FOR PETROLEUM WASTE CONTAMINATED SITE. Su Chen, Gordon Huang, and Jonathan Li
MEASURING UNCERTAINTY IN SPATIAL FEATURES IN A THREE-DIMENSIONAL GEOGRAPHICAL INFORMATION SYSTEM. Chui Kwan CHEUNG and Wenzhong SHI
SPATIAL DEVELOPMENT RESEARCH OF LARGE CITY BASED ON GIS SPATIAL ANALYSIS. Anrong DANG, Qizhi MAO, Xiaodong WANG
DIGITAL CLOSE RANGE PHOTOGRAMMETRY: A POTENTIAL TOOL FOR LAND FEATURE PRESENTATION. Gang DENG
3D SPATIAL OBJECTS MODELING AND VISUALIZATION BASED ON LASER LANGE DATA. Jie DU, Apisit EIUMNOH, Xiaoyang CHEN, Michiro KUSANAGI
3D REPRESENTATION AND SIMULATION OF MINING SUBSIDING LAND BASED ON GIS, DPS AND GPS. Peijun DU, Dazhi GUO and Qihao WENG
USE DSM/DTM TO SUPPORT CHANGE DETECTION OF BUILDING IN URBAN AREA. Hong FAN, Jianqing ZHANG, Zuxun ZHANG, Zhifang LIU
ENHANCE MANAGEMENT LEVEL OF URBAN WATER SUPPLY DEPARTMENT WITH 3S TECHNOLOGY. Yewen FAN and Wei WANG
AUTOMATIC REGISTRATION OF SATELLITE IMAGE TO MAP. Kensaku FUJII
DIFFERENTIAL SATELLITE POSITIONING OVER INTERNET. Ying. GAO and Zhi. LIU
FEDERATED SPATIAL DATABASES AND INTEROPERABILITY. Jianya GONG, Yandong WANG
OPTIMIZING PATH FINDING IN VEHICLE NAVIGATION CONSIDERING TURN PENALTIES AND PROHIBITIONS. Gang HAN, Jie JANG, Jun CHEN
DEVELOPMENT OF DYNAMIC MANAGEMENT SPATIAL-TEMPORAL INFORMATION SYSTEM AND APPLICATION FOR CENSUS DATA- TOWARD ASIAN SPATIAL TEMPORAL GIS (ST-GIS) (2)-. Michinori HATAYAMA, Shigeru KAKUMOTO, Hiroyuki KAMEDA
MODELING LAND USE EFFECT ON URBAN STORM RUNOFF AT THE WATERSHED SCALE. Chansheng HE
EXTRACTION OF THE SEA OIL INFORMATION FROM TM AND AVHRR IMAGE BY THE METHOD OF FEATURE DATA LINE -WINDOW. Fengrong HUANG
THE APPLICATION OF NEURAL NETWORK AND FUZZY SET TO CLASSIFICATION OF REMOTELY SENSED IMAGERY. Dongmin HUO, Jingxiong ZHANG, Jiabing SUN
A SELF-ADAPTIVE ALGORITHM OF AUTOMATIC INTERIOR ORIENTATION FOR METRIC IMAGES. Wanshou JIANG, Guo ZHANG, Deren LI
DETECTION OF SHEER CHANGES IN AERIAL PHOTO IMAGES USING AN ADAPTIVE NONLINEAR MAPPING. Yukio KOSUGI, Munenori FUKUNISHI, Mitsuteru SAKAMATO, Wei LU and Takeshi DOIHARA
EFFECTIVENESS OF MENU-DRIVEN VS. SCRIPT-BASED GIS TUTORIAL SYSTEMS. Bin LI
BUILDING OF B/S-BASED OBJECT ORIENTED ELECTRONIC CHART DATABASE. Guangru LI, Shaopeng SUN, Depeng ZHAO
MINE GIS 3D DATA MODEL AND SOME THINKING. Q. Y. LI, D. Y. CAO, X. D. ZHU
THE RESEARCH OF THE INFINITELY VARIABLE MAP SCALE IN GIS. Yifan LI, Shaopeng SUN
RESEARCH ON INFORMATION AUTOMATIC GENERALIZATION WITH VARYING MAP SCALE. Yuanhui LI, Dan LIU, Yifan LI
QUANTITATIVE MEASURES FOR SPATIAL INFORMATION OF MAPS. Zhilin LI and Peizhi HUANG
AN ALGEBRA FOR SPATIAL RELATIONS. Zhilin LI, Renliang ZHAO and Jun CHEN
A STUDY ON THE EXTRACTION OF DEM FROM SINGLE SAR IMAGE. Mingsheng LIAO, Jie YANG, Hui LIN
A GIS-BASED ENVIRONMENTAL DECISION SUPPORT SYSTEM FOR THE ERHAI LAKE WATERSHED MANAGEMENT. Lei LIU, Gordon HUANG, and Jonathan LI
APPLICATION OF 4D AND ASSOCIATED ENABLING TECHNOLOGIES FOR URBAN DECISION SUPPORT SYSTEM. Rong LIU, Penggen CHENG, Zhuguo XING, Kaiyun LU
3D RECONSTRUCTION OF A BUILDING FROM SINGLE IMAGE. Yawen LIU, Zuxun ZHANG, Jianqing ZHANG
AN INTELLIGENT GIS SEARCH ENGINE TO RETRIEVE INFORMATION FROM INTERNET. Zhe LIU, Yong GAO
AN ENHANCED TIN GENERATION METHOD FOR USING CONTOUR LINE AS CONSTRAINS. Wei LU, Takeshi DOIHARA
NON-LINEAR RECTIFICATION OF MAP WITH COLLINEAR CONSTRAIN. Wei LU, Takeshi DOIHARA
A STUDY ON VEHICLE POINT CORRECTING ALGORITHM IN GPS/AVL SYSTEMS. HongShan NIU, Jie XU, Hong LI
A SPATIO-TEMPORAL GEOGRAPHIC INFORMATION SYSTEM BASED ON IMPLICIT TOPOLOGY DESCRIPTION: STIMS. Yutaka OHSAWA, Atushi NAGASHIMA
APPLICATION OF VRML IN A DYNAMIC AND MULTI-DIMENSIONAL DIGITAL HARBOR. Mingyang PAN, Yifan LI, Depeng ZHAO
A COMMON DATA MODEL AND REQUESTING LANGUAGE FOR SPATIAL INFORMATION MARKETPLACES. Matthew Y. C. PANG, Wenzhong SHI, Geoffrey SHEA
TOPOLOGIC DATA STRUCTURE FOR A 3D GIS. Mattias Pfund
AUTOMATIC RECOGNITION AND LOCATION OF ROAD SIGNS FROM TERRESTERIAL COLOR IMAGERY. Sompoch PUNTAVUNGKOUR, Xiaoyang CHEN, Michiro KUSANAGI
A NEW STEREO MATCHING APPROACH USING EDGES AND NONLINEAR MATCHING PROCESS OBJECTED FOR URBAN AREA. Mitsuteru SAKAMOTO, Wei LU, Pingtao WANG
MINING SEQUENTIAL PATTERN FROM GEOSPATIAL DATA. Yin SHAN
THE ADVANCED GIS AND GPS TECHNOLOGIES TO BE USED IN THE LANCHANG BASIN AREA OF YUNNAN PROVINCE OF CHINA. Kun SHI
PRIMARY SPATIAL CHANGES. Hong SHU, Christopher GOLD and Jun CHEN
INCORPORATING 3D GEO-OBJECTS INTO AN EXISTING 2D GEO-DATABASE: AN EFFICIENT USE OF GEO-DATA. Jantien STOTER, Peter VAN OOSTEROM
A FRAMEWORK FOR AUTOMATED CHANGE DETECTION SYSTEM. Haigang SUI, Deren LI, Jianya GONG
BUILDING DISTRIBUTED GEOGRAPHIC INFORMATION SYSTEM FOR OCEAN TRANSPORTATION (GIS-OT). Shaopeng SUN, Guangru LI, Depeng ZHAO
COMPUTATION OF ACCURACY ASSESSMENT IN THE INTEGRATION OF PHOTOGRAPH AND LASER DATA. Taravudh TIPDECHO & Xiaoyong CHEN
PROXIMITY AND ACCESSIBILITY TO SUITABLE JOBS AMONG WORKERS OF VARIOUS WAGE GROUPS. Fahui WANG
WEB MAPPING WITH GEOGRAPHY MARKUP LANGUAGE. Xingling WANG, Chongjun YANG, Donglin LIU
INTEGRATION OF COMPACTNESS MEASUREMENT METHODS USING FUZZY MULTICRITERIA DECISION MAKING : A NEW APPROACH FOR COMPACTNESS MEASUREMENT IN SHAPE BASED REDISTRICTING ALGORITHM. Yinchai WANG
GIS-BASED SYSTEM FOR RAINFALL ESTIMATION USING RAINGAUGE DATA: A PROTOTYPE. Yinchai WANG, Teck Kiong SIEW
A NEW APPROACH FOR DISTRIBUTED GIS. Yuxiang WANG, Chongjun YANG, Donglin LIU
GEOD2D: A FLEXIBLE SOLUTION FOR GIS DATA EXCHANGE BASED ON COM. Huayi WU, Xinyan ZHU
GEOLOGICAL DATA ORGANIZATION FOR FEM BASED ON 3D GEOSCIENCE MODELING. Lixin WU, Enke HOU, Chunan TANG
DIGITAL MODEL AND GPS BASED PATH REPRESENTATION AND OPTIMIZATION. Linyuan XIA
AN COMPOSITE TEMPORAL DATA MODEL IN CADASTRAL INFORMATION SYSTEM. Changsheng XUE, Qingquan LI, and Bisheng YANG, Yuanchun HUA, Shiwu XU
A SPATIAL-TEMPORAL DATA MODEL FOR MOVING AREA PHENOMENA. Shanzhen Yl, Yong ZHONG, Lizhu ZHOU, Jun CHEN, Qilun LIU
CONSTRUCTION OF 3D MODELS FOR ELEVATED OBJECTS IN URBAN AREAS USING AIRBORNE SAR POLARIMETRIC DATA. Yalkun YUSUF, Masashl MATSUOKA, Fumio YAMAZAKI, Seiho URATSUKA, Tatsuharu KOBAYASHI, Makoto SATAKE
COASTAL GIS: FUNCTIONALITY VERSUS APPLICATIONS. Thomas Q ZENG, Qiming ZHOU, Peter COWELL and Haijun HUANG
CIS AIDED CHARACTERIZATION OF SOIL AND GROUNDWATER ARSENIC CONTAMINATION IN SOUTHERN THAILAND. Jianjun ZHANG, Xiaoyong CHEN, Preeda PARKPIAN, Monthip Sriratana TABUCANON, Janewit WONGSANOON, Kensuke FUKUSHI, Skorn MONGKOLSUK and N.C.THANH
MULTIRESOLUTION TERRIAN MODEL. Jin ZHANG
A TROUS WAVELET DECOMPOSITION APPLIED TO DETECTING IMAGE EDGE. Xiaodong ZHANG, Deren LI
RESEARCH OF THE LAND MANAGEMENT INFORMATION SYSTEM BASED ON WEB GIS AND SPATIAL DATABASES FOR PROVINCIAL AND LOCAL GOVERNMENTS IN CHINA. Junsan ZHAO, Yaolong ZHAO, Qiaogui ZHAO and Tao WEI
ANALYSING BRANCH BANK CLOSURES USING GIS AND THE SMART MODEL. Lihua ZHAO, Barry J. GARMER
QTM-BASED ALGORITHM FOR THE GENERATING OF VORONOI DIAGRAM FOR SPHERICAL OBJECTS. Xuesheng ZHAO, Jun CHEN
MODELING AND LANDSCAPE OF HIGHWAY CAD. Jiaqing ZHENG, Xi’an ZHAO, Chujiang CHEN
ASSISTING THE DEVELOPMENT OF KNOWLEDGE FOR PREDICTIVE MAPPING USING A FUZZY C-MEANS CLASSIFICATION. A-Xing ZHU, Edward ENGLISH
THE DESIGN AND IMPLEMENTATION OF CYBERCITY GIS (CCGIS). Qing ZHU, Deren LI, Yeting ZHANG, Hanjiang XIONG
3D COMPUTER SIMULATION OF ANCIENT CHINESE TIMBER BUILDINGS. Yixuan ZHU, Jie YANG, Deren LI
3D MODELLING FOR AUGMENTED REALITY. Siyka ZLATANOVA
THE DESIGN OF SPATIAL DATA WAREHOUSE. Yijiang ZOU
AUTHOR INDEX
Cover

Full text

ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
121 
Penalties 
t) 
3 7 0 
5 16 0 
23 0 
17 12 0 
4 16 0 
11 0 
19 9 0 
includes 
array, the 
:luded in a 
). The first 
e equal to 
ies with the 
ig. 3c); the 
out degree 
; one. The 
,e that the 
The penalty 
iresents the 
itwork, e.g. 
; prohibited, 
rresponding 
ntribution in 
ed [Kirby & 
at efficiently 
intersection 
the network 
by Caldwell 
the following 
from the end 
ravel time on 
e movement 
ostream of /,. 
e a path as a 
f nodes and 
ring the new 
equired to be 
not to be 
this approach 
no interfaces 
e. 
ts approach, 
iat computes 
lents, but not 
ibel-correcting 
he potential to 
The links from 
rder, while the 
ond list. When 
econd list are 
i requires the 
ategorizes the 
ave prohibited 
ie efficient, but 
not consider 
4. METHOD PROPOSED BY THE AUTHORS 
From the previous analysis, a conclusion that changing the 
topology of network is not easy can be achieved. The 
alternative way by defining a new data structure is relative 
easy. Thus the authors of this paper proposed a new data 
structure to represent the turn restrictions. Based on this 
new data structure, a slight modification is made on the 
classical algorithm to compute the shortest path. 
4.1 THE NEW DATA STRUCTURE 
As we all know that turning left or right is banned in some 
urban roads. In statistic, the number of banned turns is 
larger than the number of permitted turns (Table 1). 
Theoretically, the value of banned turn penalties is infinite, 
meaning that the corresponding movement is prohibited. 
But in real implementation, an infinite value in data structure 
is nonsensical. Considering the store space and 
performance of looking for, it is necessary to eliminate 
these infinite values from data structure. 
Total 
turns 
Banned turns 
Permitted 
turns 
43575 
32139 
11436 
Table 1. The turns information numbers in Hong Kong Road 
In EFSS data structure, the ForwardPointer() of the next 
node must be given. Only by this pointer and the pointer of 
current node, all nodes adjacent with current node can be 
definitely found out. In Penalties() column, only the penalty 
value is given but node id is not given that the value 
attached. A quadric search must be implement in the 
process. It is necessary to append the node id in the 
PenaltiesQ column. Moreover, a best path may contain 
loops, resulting from prohibited or high cost movement 
delays. A loop route including algorithm process is a 
time-consuming work. The terminal result of a loop route 
often makes the algorithm into a deadlock. The node id 
connected Penalties() is a useful information to avoid the 
loop route problem. A quadric search is also need to find 
the nodes id with turn penalties. General speaking, these 
redundant implement will largely depress the efficient of 
algorithm. 
Because the addition of the turn feature, the meaning of 
same node come from this parent node is different the 
meaning come from that parent node. Even though come 
from the same parent node the meanings of this parent 
node are different because of turn (Fig 4). The parent and 
grandparent nodes information must be given when 
computing the shortest path. Otherwise, the shortest path 
can’t be reconstructed when the computing process is 
finished. 
Fig 4. Different turns of same node 
Let G=(N, A) be a simple directed graph, where N is the set 
of the nodes, of cardinality n, and A is the set of the arcs, of 
cardinality m. In the forward star structure (FSS), a list 
(Adjacent list) is kept for each node of the network, 
indicating the position in the arc list, of arcs beginning at this 
node. In adjacent list, three fields are included: adjacent 
node id, next adjacent node pointer and a penalty list 
pointer. Another list (Penalties list) is kept for indicating next 
moving towards nodes in network after leaving the adjacent 
node. In Penalties list, three basic fields are included: 
penalty value, node id connect penalty and next pointer. Fig 
5. illustrates this list representation for the network sketched 
in Fig 2a. 
Fig 5. One node presentation 
4.2 THE MODIFIED ALGORITHM 
On the graph G defined in the previous section, let assume 
that all cycles have nonnegative cost and that there exists a 
path from s(source node) to every other vertex of N. For 
notation convenience, let sc(s) be shortest path cost from 
s(source node) to d(destination), pred(v) the predecessor of 
v and ppred(v) the parent of the predecessor of v in road 
network. T will represent the set of vertices marked as 
temporary and pc(v) will represent the penalty cost between 
arcs connected node v. adj(v) represent the set of vertices 
which connected with node v; 
Then the algorithm can be formalized: 
Step 1: Initializations. 
Set sc(s)<r 0 and pred(src)<r 0. 
For each vertex ie adj(s), set sc(i)<r+°° and pred(i)<r i. 
Finally, set T4-N 
Step 2: Selecting and updating. 
Find vertex / in T verifying 
If the minimum is not unique, select any i that achieves the 
minimum. 
For each vertex j eadj(i), scan all processors node of i, if 
none of them is j, then test if sc(i)+Wi+pc(i)<sc(j), then 
Set sc(j)<rsc(i)+Wij +pc(i). and pred(j)<ri. Else dessert j. 
Step 3: Loop or exit. 
If T is empty, then exit. 
Else if current node in T is node destination node), then 
exit. 
Else go to Step 2. 
The time performance of the algorithm is expected to be 
somewhat worse than the pure shortest path algorithms 
without intersection movements. 
5. EXPERIMENT AND CONCLUSION 
It will be difficult to defining the topology of road network

Cite and reuse

Cite and reuse

Here you will find download options and citation links to the record and current image.

Monograph

METS MARC XML Dublin Core RIS Mirador ALTO TEI Full text PDF DFG-Viewer OPAC

TOC

Chapter

Image

PDF ALTO TEI Full text

Preview 114×150 jpg

Small 780×1024 jpg

Medium 1560×2048 jpg

Master 3928×5156 MASTER

Image fragment

Link to the viewer page with highlighted frame Link to IIIF image fragment

Citation links

Citation links

Monograph

To quote this record the following variants are available:

Here you can copy a Goobi viewer own URL:

Chapter

To quote this structural element, the following variants are available:

Here you can copy a Goobi viewer own URL:

Image

To quote this image the following variants are available:

Here you can copy a Goobi viewer own URL:

Citation recommendation

Chen, Jun. The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics. AIT, 2001.

Please check the citation before using it.

Image manipulation tools

Tools not available

Share image region

Use the mouse to select the image area you want to share.

Please select which information should be copied to the clipboard by clicking on the link:

Link to the viewer page with highlighted frame
Link to IIIF image fragment

Contact

Have you found an error? Do you have any suggestions for making our service even better or any other questions about this page? Please write to us and we'll make sure we get back to you.

Name: (Required)

Last name:

E-mail: (Required)

Message: (Required)

Security question:

How much is one plus two?:

I hereby confirm the use of my personal data within the context of the enquiry made.

Accept:

No Yes