QEOGRAPHICAL
`INFORMATION SYSTEMS
`
`PRINCIPLES AND APPLICATIONS
`
`EDITED BY
`
`DAVIDJ MAGUIRE,
`
`MICHAEL F GOODCHILD
`
`AND
`
`DAVID W RHIND
`
`
`
`pl».I. Longman
`Scien’t11ic&
`53' Technical
`Copublished in the United States and Canada with
`John Wiley & Sons, Inc.. New York
`
`
`
`Page 1 of 19
`
`Google Exhibit 1009
`
`

`
`E)C>(:tU
`
`
`
`Longman Sclentlflcand Technical.
`,,
`(5
`Longman Group UK Ltd
`:0 ' /\
`1 iY\ 331‘ i Longmaii House. Burnt Mill, Harlow,“
`‘
`Essex CM20 ZJE. England
`and Associated Companies throughout the world.
`copublished in the United States and Canada with
`John Wiley & Sons, Inc.. 605 Third Avenue, New York.
`NY [0158
`
`‘/ - 2,
`
`'-L
`
`© Longman Group UK Limited l99l
`
`All rights reserved; no part of this publication may be
`reproduced. stored in a retrieval system. or transmitted in
`any form or by any means, electronic, mechanical.
`photocopying. recording. or otherwise without either the
`prior written permission of the Publishers or a licence
`permitting restricted copying in the United Kingdom
`issued by the Copyright Licensing Agency Ltd. 90
`Totlcnham Court Road. London W1 P 9HE.
`
`Trademarks
`
`Throughout this book trademarked names are used.
`Rather than put a trademark symbol in every occurrence
`of a trademarked name. we state that we are using the
`names only in an editorial fashion and to the benefit of the
`trademark owner with no intention ofinfringemcnt of the
`trademark.
`
`First published 1991
`Reprinted I992
`
`Brltlsli Library Cataloguing ln Publication Data
`Maguire. David J.
`Geographical iniormation systems: Principles and
`applications
`I. Title
`II. Goodchild. Michael F.
`Ill. Rhind, David W.
`910.901
`
`ISBN 0-582-05661-6
`
`Llbnry of Congress Cataloging-in-Publication Data
`Maguire, D. J. (David J.)
`Geographical information systems / by D. J. Maguirc.
`Michael F. Goodchild, and David W. Rhind.
`p.
`cm.
`lncludes bibliographical references and index.
`Contents: v. I. Principles — v. 2. Applications.
`ISBN 0-470-21789-8 (‘USA only)
`1. Geographical information systems.
`I. Goodchild, Michael F.
`ll. Rhind.
`David.
`lll. Title.
`G70.2.M354
`1991
`9lO'.285—dc20
`
`91-3724
`CIP
`
`Set in Great Britain by Fakenham Photosetting Limited.
`
`Printed and Bound in Great Britain at the Bath Press. Avon
`
`
`
`

`
`Preface
`List of contributors
`Acknowledgements
`
`Section I Overview
`
`Introduction
`
`D J Maguire, M F Goodchild and DW Rhind
`
`1. An overview and definition of GIS
`
`D J Maguire
`
`2. The history of GIS
`J T Coppock and D W Rhind
`
`3. The technological setting of GIS
`M F Goodchild
`
`4. The commercial setting of GIS
`J Dangermond
`
`5. The government setting of GIS in the United Kingdom
`R Charley and R Burton
`
`6. The academic setting of GIS
`D J Unwin
`
`7. The organizational home for GIS in the scientific
`professional community
`I L Morrison
`
`8. A critique of GIS
`R T/iangeenbrug
`
`Section 1] Principles
`
`Introduction
`
`M F Goodchild, D WRhind and D J Maguire
`
`xiii
`xvii
`xxvii
`
`3-7
`
`9-20
`
`21-43
`
`45-54
`
`55-65
`
`67-79
`
`91-100
`
`101-7
`
`111-17
`
`vii
`
`Pa
`
`:30f19
`
`

`
`
`
`PRINCIPLES
`
`VOLUME1
`
`:
`
`(8)
`
`9.
`
`10.
`
`ll.
`
`12.
`
`13.
`
`14.
`
`Nature of spatial data
`
`Concepts of space and geographical data
`A C Gatrell
`
`Coordinate systems and map projections for GIS
`D H Maling
`
`Language issues for GIS
`A U Frank and D M Mark
`
`The error component in spatial data
`N R Chrisman
`
`Spatial data sources and data problems
`P F Fisher
`
`GIS and remote sensing
`F W Davis and D S Simonerl
`
`(b)
`
`Digital representation
`
`. Computer systems and low-level data structures for GIS
`Wm R Franklin
`
`
`
`119-34
`
`135-46
`
`I47-63
`
`165-74
`
`l75—89
`
`19!-213
`
`2I5-25
`
`227-37
`
`239-49
`
`
`
`. High-level spatial data structures for GIS
`M J Egenhofer and J R Herring
`
`. GIS data capture hardware and software
`M J Jackson and P A Woodsford
`
`

`
`119-34
`
`135-46
`
`147-63
`
`165-74
`
`175-89
`
`191-213
`
`IS
`
`215-25
`
`227-37
`
`239-49
`
`Pa 5of19
`
`. Database management systems
`R G Healey
`
`19.
`
`Digital terrain modelling
`R Weibel and M Heller
`
`20.
`
`Three-dimensional GIS
`
`J F Raper and B Kelk
`
`(c) Functional issues
`
`21.
`
`The functionality of GIS
`D J Maguire and J Dangermond
`
`Information integration and GIS
`I D H Shepherd
`
`. Cartographic modelling
`C D Tomlin
`
`Spatial data integration
`R Flowerdew
`
`NNNNNO‘5"F‘'-*’P’
`
`251-67
`
`269-97
`
`299-317
`
`319-35
`
`337-60
`
`361-74
`
`375-87
`
`403-12
`
`413-25
`
`ix
`
`Developing appropriate spatial analysis methods for GIS 389-402
`S Openshaw
`
`. Spatial decision support systems
`PJ Densham
`
`I9\l
`
`. Knowledge-based approaches in GIS
`TR Smith and Ye Jiang
`
`

`
`VOLUME1
`
`;
`
`PRINCIPLES
`
`
`
`-
`
`((1) Display Issues
`
`28. Visualization
`
`B P Buttenfield and WA Mackaness
`
`29. Computer name placement
`H Freeman
`
`30. Generalization of spatial databases
`J-C Muller
`
`(e) Operational issues
`
`31. GIS specification, evaluation and implementation
`A L Clarke
`
`32. Legal aspects of GIS
`E F Epstein
`
`33. Managing an operational GIS: the UK National On-Line
`Manpower Information System (NOMIS)
`M J Blakemore
`
`34. Spatial data exchange and standardization
`S C Guptill
`
`Consolidated bibliography
`List ofacronyms
`Author index
`
`Subject index
`
`427-43
`
`445-56
`
`457-75
`
`477-88
`
`489-502
`
`503-13
`
`515-30
`
`531 -591
`593-598
`599-613
`
`615-649
`
`
`
`

`
`Preface
`List of contributors
`Acknowledgements
`
`. Section III Applications
`
`Introduction
`
`D W Rhind, D J Maguire and M F Goodchild
`
`(a) National and international GIS programmes
`
`35. A USGS perspective on GIS
`L E Starr and K E Anderson
`
`36. Development of GIS-related activities at the
`Ordnance Survey
`M Sowton
`
`37. National GIS programmes in Sweden
`L Ottoson and B Rystedt
`
`38. The development of GIS in Japan
`S Kubo
`
`39. Land and Geographical Information Systems in Australia
`J F 0’CaI1aghan and B J Garner
`
`40. GIS and developing nations
`D R F Taylor
`
`(b) Socio-economic applications
`41 . -Land information systems
`P F Dale
`
`42. GIS and utilities
`
`R P Mahoney
`
`43. Car navigation systems
`M White
`
`44. Counting the people: the role of GIS
`D W_Rh_ind
`
`45. GIS and market analysis
`J R Beaumont
`
`xiii
`xvii
`xxvii
`
`3-10
`
`11-22
`
`23-38
`
`39-46
`
`47-56
`
`57-70
`
`71-84
`
`85-99
`
`101-14
`
`115-25
`
`127-37
`
`139-51
`
`xi
`
`427-43
`
`445-56
`
`457-75
`
`477-88
`
`489-502
`
`Line
`
`503-13
`
`515-30
`
`531-591
`593-598
`599-613
`615-649
`
`Pa
`
`¥ar19
`
`

`
`VOLUME2
`
`: APPLICATIONS
`
`(c) Environmental applications
`
`46. Soil information systems
`P A Burrough
`
`47. Integration of geoscientific data using GIS
`G F Bonham-Carter
`
`._
`
`153-69
`
`171-84
`
`48. Multisource, multinational environmental GIS: lessons
`learnt from CORINE
`
`I85-200
`
`H M Mounsey.
`49. Environmental databases and GIS
`J R G Townshend
`
`50. Global databases and their implications for GIS
`D M Clark, D A Hastings and J J Kineman
`
`((1) Management applications
`
`51. GIS and public policy
`H W Calkins
`52. Urban GIS applications
`R Parrott and F P Stutz
`.
`.
`53. Land resource information systems
`K C Siderelis
`54. Land management applications of GIS in the state of
`Minnesota
`A Robinette
`55. GIS in island resource planning: a case study in map
`analysis
`J K Berry
`56. Integrated planning information systems
`D J Cowen and W L Shirley
`
`Section IV Epilogue
`Epilogue
`D W Rhind. M F Goodchild and DJ Magulre
`
`Consalidated bibliography
`List of acronyms
`Author index
`
`Subject index
`
`201-16
`
`217-31
`
`233-45
`
`247-60
`
`261-73
`
`275-83
`
`285-95
`
`297-310
`
`313-27
`
`329-389
`391-396
`397-411
`
`413-447
`
`::
`—I._
`
`0 l‘-7
`NI?
`$671
`
`he can
`
`'
`-‘ . ‘
`1
`1 1'5
`fit
`I
`§_‘
`M
`uufi
`11 I
`=' '
`1
`i ‘
`&. I
`:-
`AUX
`§ I
`
`up an
`
`ca: 1
`
`&
`#3
`E ‘
`
`i
`
`xii
`
`
`
`

`
`Automobile navigation is a demanding applicodon of digital maps and appears
`likely to become a comtnon and economically important one. A few systems are
`commercially available and many prototypes exist. These systenu determine location
`using wheel rotation sensors, solid state compassa, inertial devices (gyros and other
`novel devices), radio location or some combination of them. Requirements of the
`source maps depend on the methods used and the user interface. as well as on
`function: performed in addition to location determittation (such as map display.
`verbal directions, pathfinding and destination /finding by address or landmark).
`Typical map requirements for panicular systems includepositional accuracy to the
`order of a car length, detailed street classification, turn restriction data and
`topological encoding. Creating such digital maps to support navigation is a daunting
`task. At the time of writing. there are several pilot projecn. int! a fear comtnerttial
`operations and somefledgling consortia which have as their miasbn the production
`of digital maps for navigation or the promulgation ofstandards fornclr maps. All
`systems require faster retrieval than GIS systems have typically provided.
`Applications using navigation systems include experimental traflic systems. such as
`traffic congestion reporting and ‘sign-post’ trartsmitters and receiver: for
`communicating with on-board navigation systems.
`
`INTRODUCTION
`
`The automobile is becoming it much richer
`electronic environment for the driver. On-board
`computers. cellular telephones and vehicle
`navigation are already available. and real-time
`traffic information and route guidance have been
`demonstrated. The market tor factory-installed
`systems appears to be huge. In Japan, Nissan has
`been selling more than 1000 systems per month as
`anoptiol on theNissanCedric. Thisoption in
`combination of navigation system and television
`(which can only be operated with the vehicle
`stopped). In Gennany. Bosch began to sell the
`Travelpilot in 1989. ln the United States, Etak sold
`2000 Navigators over a period of two years. Because
`electronics are pervading the automobile. a factory-
`installed navigation option will probably become
`inexpensive, perharx less than US SSW. As a
`consequence. demand for and use of digital map
`
`data will grow. Market analysts have estimated that
`sales of navigation systems will grow from US $5
`million in 1990 to US Sill) million in 1994 (Frost dc
`Sullivan 1989).
`Car navigation uses maps intensively. The map
`must provide information for:
`
`O
`
`0
`
`0
`
`determining and maintaining the location of the
`vehicle in relation to features represented on
`the map:
`
`displaying a map graphically or generating
`routing instructions in text or voice;
`
`linking effectively with infrastructure.
`
`This chapter reviews the current ‘state of the
`art’ of digital mapping as regards vehicle navigation
`and, since it is still in its infancy. some speculations
`are made about likely future developments. 'l1te
`infancy of the technology is reflected in the meagre
`
`Page 9 of 19
`
`

`
`
`
`M White
`
`
`
`Fig. 43.2 The Honda Gyrocator screen (courtesy author).
`
`supply of prior research considering the subject and
`directly related cartography [Petchenik 1989).
`Marine navigation is not included in this discussion.
`It has similar requirements and applications and.
`indeed. was the origin and inspiration for much of
`the current vehicle navigation technology.
`However. it differs in many ways from land-based
`vehicle navigation and warrants separate discussion.
`The following sections discuss vehicle
`navigation systems and methods already in use and
`how information is displayed graphically, reported
`textiially or by voice. Then applicmions such as
`finding destinations and pathfinding are considered.
`Finally. there is a review of the essential
`characteristics of digital maps. in so far as
`navigation and its related functions are concemed.
`From this. it will become evident that navigation
`and related applications require a topologically
`encoded and seainles datzbae, as well as very fast
`data retrieval.
`
`NAVIGATION
`
`There are only a few vehicle navigation systems
`commercially available at the time of writing (mid~
`1990). In the United States. the Etalt Navigator has
`been available since 1985. The Bosch Tiavelpilot. a
`derivative of the Etak Navigator. became available
`in Germany in 1989. Both of these systems are
`‘alter-market‘ devices, that is, they are installed
`after manufacture and usually after the end-user
`
`“Page 10 of 19
`
`purchases the vehicle. In Japan, the Toyota Crown
`and the Nissan Cedric have offered factory-installed
`navigation options since 1987 and 1989 respectively.
`The Etak. Bosch and Nissan systems use dead
`reckoning and map matching (explained below) but
`the Toyota system uses only dead reckoning. The
`map matching systems require topologically
`encoded digital maps, whereas the Toyota system
`uses bit-mapped images of paper maps (see Plate
`43.] and Figs. 43.1 and 43.2)
`
`
`
`Fig. 43.1 The Nissan Cedric screen (courtesy
`author).
`
`In addition. there are several experimental
`systems and ‘concept cars‘ either demonstrating or
`‘mocking up‘ navigation systems. In an auto show in
`Japan in early I990. more than a dozen
`
`

`
`Fig. 43.3 The Autoguide screen (courtesy Department of Transport).
`
`manufacturers showed such concept cars. This
`indicates a strong interest in navigation and. by
`implication. maps for navigation. Examples of
`experimental systems include the Philips CA RIN
`(Thoone I987), ('lan'on NAVI and the UK
`Autogurde (Calling and Belcher 1989). CARIN and
`Autoguide present stylized graphic instructions
`representing the upcoming intersection to the driver
`(see Fig. 43.3). Only the general principles on which
`such systems work are known: all the current
`vendors of navigation systems regard their software
`and data storage methodology as proprietary and.
`accordingly. do not reveal details. This is
`unsurprising because navigation has pushed forward
`the frontier of map access technology: typically. on-
`board computers are much less powerful
`computationally and contain less copious RAM
`than ‘normal’ GlS require and, at the same time.
`demand a faster response rate than available GlS
`offer. In addition. navigation algorithms and their
`implementation have involved substantial
`expenditure. The commercial stakes are high and.
`accordingly. secrecy prex ails on the internal details
`of each vendor's offerings.
`
`POSITION DETERMINATION
`
`Navigation includes determination ofp -.:r. 3 ;~.
`well as guidance toward a destination. There are
`three essentially different technologies used for
`position determination. These are dead reckoning.
`radio location and proximity beacon detection.
`They can be used alone or in combination.
`Destination finding and guidance towards the
`destination have various quite different user
`interfaces.
`
`Dead reckoning and radio location
`
`Dead Reckoning (DR) is the process of computing
`an updated position from three inputs: details of a
`prior position; the distance travelled from the prior
`position; and the heading travelled since that prior
`position. The Etak Navigator, Bosch Travclpilot
`and Nissan Cedric all use DR. Figure 43.4 illustrates
`dead reckoning. To measure the distance travelled,
`all three use sensors mounted on the wheels. Other
`
`systems have tried to use the vehicle's odometer but
`this is much less accurate.
`
`Page 11 of 19
`
`:97
`
`

`
`M White
`
`
`
`'..-_-3.-,2 two
`.:_--.-n-. - -; '' :
`F- v
`\" ibsolute heading
`me$urt-.-- ‘rt --- '_t.-.
`-.-‘-.:.~.-..':
`».«
`lT.;_‘._
`. ~ as-state compass t_c.g.
`see?!‘
`..‘
`v~“ ~.'.': .-Webeadingis
`comocu; " - "-. -r... <".-it measurements. A
`
`.
`
`. '4 —axis magnetometer)
`.-
`';- . ' :. -
`s.» ..w -'
`tnea«i'.~'-
`.
`v~ --~—."~ -tthe ambient magnetic
`freld:'v -
`'~-
`-. an-~'; wmponentofthe
`earth ~
`-
`_ .'. _'
`.
`t-"(I.I!ed.Tltel‘€ are many
`.-
`phy~-.
`. "~ .~‘.'- '
`-cdsuchasthe
`magnet. '
`.-
`'
`, -.."»..'olthe steel in the
`vchide -7 .' -~-
`..—_ -_.,g—..'.tt declination.
`HOIC\_'
`jl -
`_ ~
`, .
`-z-ideratioiis eventually
`.~--_- .-.; ourvoximate position of the
`. "- ~.‘.
`' "-.
`~ magnetic field and
`~
`- .,;~ .: .
`.4‘ An important
`'.
`-
`.--- .-' :.
`.- qxilicationsis dip
`. '- ':r; '-‘._-'r; ofthc compass
`. -r“: - " gut-tie field vector. The
`' - _'
`~ nntimntal only at the
`- ar 3 .cn'neidcs approximately
`.; ;._. .1 -r. Sothc compass
`withthe ge
`measures '.~..- xx;
`.
`.2 vector projected on to
`its mwi plan:
`\\ e -— '-~ .~ normally close to
`horizontal.
`.-
`- 2- in gmund slope caused
`by hills and the - <4-3 .:~mr ~. -gt amount to several
`degrees and affect the -
`- --7-.~.~~'ntagnetic field
`relationship aunrtirrgt} Cxntputatmn of the
`heading from compass mrasnrenicnts must take all
`these effects into eonsédcnmon
`The difference in the tistance travelled on two
`
`
`
`'.
`
`.
`
`_~
`
`._-
`
`‘
`
`it
`
`than does that on the inside of the curve. Thus
`
`wheel sensor readings yield relative heading
`information. Again many physical considerations
`come into play. including wheel base.
`circumference. radius of curvature of the turn.
`
`steering geometry and wheel slip. Taking all these
`factors into account. however, a new heading can be
`computed from the prior heading and the difference
`in distance travelled by the two wheels.
`Other sensors are under development or have
`been demonstrated in experimental systems. These
`include a gyro turning rate sensor. a vibrating rod
`turning rate sensor, an inclinometer, a GPS (Global
`
`Poiitioning System) receiver. ti LORAN-(‘ receiver
`and an optical speed sensor.
`A gyroscope (more commonly a ‘gyro') is a
`spinning mass and the vehicle‘s' turniiig rate is
`measured indirectly by measuring forces resulting
`from the conservation of momentum: such forces
`
`can be experienced by holding a spintiing bicycle
`wheel off the ground and turning it. Large gyros are
`used in inertial navigation systems common on
`board ships or aircraft. The vibrating rod sensors
`also operate on conservation of momentum. An
`iiiclirioineter measures the angle of lllClllli|llUll ofa
`statioiiary (or. more generally. a non-accelerating)
`vehicle and may be used to remove the effects of dip
`angle on the compass measurement as well as
`effects of hills on distance travelled. Any
`acceleration experienced affects the inclinometcr so
`this must also be considered. As a group. the gyro.
`vibrating rod and inclinometer are all inertial
`sensors: they depend on the physics of momentum
`and inertia for their operation. For a survey of such
`inertial navigation sensors. see Smith (l9R6).
`GPS and LORAN-C are radio location
`
`systems. These radio location sensors are not used
`in dead reckoning. instead they provide position
`‘fixes’ that are independent of the prior position.
`They both operate by an on—board receiver and
`computer t-omparingl signals from multiple
`traiisiriitieis and determining receiver location from
`known transmitter positions and signal propagation
`times. The LORAN-C transmitters are based on the
`ground and the UPS are on a constellation of
`satellites in orbit. GPS will cover the entire globe
`when the satellite constellation is completed.
`French (1986) provides an overview of radio
`location systems.
`Compass and radio location sensors are
`‘absolute’ sensors; in contrast. wheel sensors and
`
`gyros are ‘relati
`change inforrna
`information wit
`sensors. hovvev
`Wheel sensors
`
`Magnetic comp
`as well as the es.
`
`(GPS and LOR
`in highly urbani
`characteristics
`
`accuracy of the
`however. comb
`even when one
`Etalt method w
`
`compass and tr
`measureinent.
`
`sensor (the corn
`error and the .~.-
`odomcterl rs
`
`yielding a can!
`(lloney, Millie-
`Despite -i-
`deriving ha.-axis
`position still ,. .-
`location of the
`in sensors It-ad
`
`In practice. D'-
`since the acn-
`threshold of t.~
`needed. achie‘
`radio locatim
`tiresome and .»
`user; the thin:
`Radio locatio"
`
`that are quite ..
`These errors J-
`distance. Instc
`
`clearly and the
`minimum or. .
`information at
`dead reckon l>.
`done. use i.-id5~
`
`just another se
`determination
`
`Map matchln
`
`Map matching
`from dead recl
`
`determined by
`
`opposing wheels depends on the dlangt: in heading.
`When travelling straight ahead (LC. without heading
`change). the two wheels travel the same distance.
`When turning. the outside wheel travels further
`
`118
`
`
`
`

`
`sensors. however, suffer characteristic defects.
`Wheel sensors and gyros have noise and bias.
`Magnetic compasses measure magnetic anomalies
`as well as the earth's magnetic field. Radio location
`(GPS and LORAN) signals are distorted or blocked
`in highly urbanized areas. Manifestly. the sensor
`characteristics are important in assessing the
`accuracy of the estimated position. In addition.
`however. combining sensors can yield good results
`even when one sensor is noisy or fails entirely. The
`Etak method of computing heading. using both a
`compass and differential wheel senso}
`measurement, is an example in which the absolute
`sensor (the compass) suffers no accumulation of
`error and the relative sensor (the differential
`odometer) is unaffected by magnetic anomalies —
`yielding a com bined result that is rarely erroneous
`(Honey. Milnes and Zavoli 1988).
`Despite such accurate and resilient methods of
`deriving heading. the accuracy of a dead reckoned
`position still ako depends on the accuracy of
`location of the prior position. The ineluctable errors
`in sensors lead to accumulated error in DR position.
`In practice, DR alone is insufficient for navigation
`since the accumulated error will eventually exceed a
`threshold of usefulness. So occasional fixes are
`
`needed, achieved either by human intervention.
`radio location or map matching. The first of these is
`tiresome and assumes accuracy on the part of the
`user; the third method is discussed in detail below.
`Radio location, however. has characteristic en-ors
`
`that are quite different to those already discussed.
`These errors do not accumulate over time or
`
`distance. Instead. signals are typically received
`clearly and the error level is the characteristic
`minimum or, alternatively. there is no position
`infomiation available. It is, however. possible to
`dead reckon between radio fixes or, as Etak has
`done, use radio location (in this case LORAN-C) as
`just another sensor to be considered in location
`determination.
`
`Map matching
`
`Map matching is used to remove accumulated emit
`from dead reckoning. The path travelled is
`detennined by dead reckoning or radio location and
`
`Page 13 of 19
`
`absolute sensors in that the error in estimated
`
`position does not continue to grow (as it does with
`use of dead reckoning alone). It differs in that, once
`lost. the map matching algorithm is unlikely to
`recover; absolute sensors, on the other hand, may
`fail for a time or region but, outside that period or
`region. they have their usual error characteristics.
`
`
`
`I-‘ig.43.5 Mapnntctng-rfidlyqa DR path
`(dashed line) with strut: on he nap.
`
`By wayolancxgtkmne would eventually
`accumulate sijtt emit uniquely DR while
`wanderingaltqclty snub Though cowering
`the DR puthIulh:nno-hIue\v¢r. the navfiation
`algorithm an ejte elven that accumulate from
`sensor noise. &k pnnneml the any matching
`apprond (see Hnoq on d Him for the Navigator.
`"l'he Bafi 'lh~e§Ila no the same approach and
`the Nina (‘air an a flat map matching
`methd. Sch 3 naj depends on the driver
`stayin cut; a the rails; it is inappropriate for
`announce pane: of a vehicle. In this approach.
`Elfin he! in nation is determined as an
`output at Imp jetting and is used for orienting
`the nqsfispldyed to the driver. Experience
`ufiauestnt the inpression given by a map display
`01!: A slightly ‘wrong’ orientation is that the
`auputer is lost or will be soon — somewhat like the
`mprsuon of a misaligned street name on a printed
`map. For this reason. map matching methods are
`not to orient and position the display even for
`alnnlute location methods. such as radio location.
`
`Other navigation approaches that have been
`tried require extensive infrastructure. such as
`
`
`
`

`
`

`
`location of destinations, usually specified by street
`address but also by street intersection or major
`landmark, and then finding a way to proceed to the
`destination.
`
`listings.
`
`Path finding
`
`Destination finding
`
`To find a destination, the map database is searched
`via specially designed indexes and the destination is
`shown, for example. on the plot with a flashing star.
`The driver proceeds towards the star and his or her
`destination, as it was for the Biblical Star of
`Bethlehem! In-vehicle destination finding is
`interactive, may lack a keyboard and — because it is
`interactive — can take advantage of the user’s
`ingenuity. In the Bosch Travelpilot and the Etak
`Navigator. for example, there are 12 buttons for
`input and the user only needs to enter a few
`characters before selecting from a list of possible
`cities or street names which match what has already
`been entered. Figure 43.7 shows a destination entry
`in progress. The user‘s ingenuity is exploited for
`recognizing spelling variants. in contrast to the
`common practice in geocoding software to search
`for sound-alike or otherwise similar words.
`
`At the time of writing, only experimental systems
`such as EVA and CARIN compute recommended
`paths from the current location to the destination.
`For pathfinding, the street network topology is
`required. Furthermore. for the recommended paths
`to be feasible, the pathftnding algorithm must use
`traffic flow and turn restriction information; this
`places a significantly larger burden on the map
`database. People often expect the guidance system
`to declare the best route and, ultimately,
`pathfinding is likely to be a required feature of all
`navigation systems.
`The user interface for the pathfinding function
`can take many forms. Autoguide, for example,
`provides only an arrow indicating the action at the
`next intersection, or a more elaborate graphic for a
`roundabout. Highlighting the path on a map display
`is another approach. Two further approaches
`highlight the path on the map display and offer
`verbal instructions (Cass 1989).
`
`
`
`Fig. 43.7 Destination entry to the Etak Navigator.
`
`In the future. business directories (‘Yellow
`Pages‘) and other lists of destinations will be
`provided as part of the map. Finding the nearest
`hardware store or service station is an example of
`such applications. Detailed business information or
`advertising could also be provided: for example,
`
`DIGITAL MAP REQUIREMENTS AND
`CHARACTERISTICS
`
`A digital map for navigation must meet demanding
`criteria. It must reside on rugged media, satisfy
`geometrical requirements imposed by the method of
`position detennination. provide very fast retrieval
`and use an appropriate coordinate system.
`
`Storage media
`
`The storage medium for all available systems except
`the Etak Navigator is Compact Disk (CD) (Honey
`and White 1986). The Navigator uses compact
`cassette tape. The media and reading device must
`be sufficiently rugged for vehicle environments and
`these suffer wide temperature fluctuations and
`severe vibration. CD players meeting in-vehicle
`environmental specifications only became available
`
`Page 15 of19
`
`121
`
`

`
`M White
`
`in 1989 and, being designed some years earlier. the
`Etak cassette player was made specifically to meet
`in-vehicle requirements for the applicati--ri All such
`devices are relatively slow for random retrieval.
`typical average seek time for a CD is 1 second -
`over 30 times that of a typical hard disk. The Etak
`cassette tape. which operates at 80 inches per
`second, has typical seek times of lllseoonds. These
`relatively slow speeds impose noteworthy
`challenges and severe constraints for the retrieval
`software. which are discussed below.
`
`Digital mrips also consume considerable space.
`lzzich CD holds approximately 600 Mb. This is
`sufficient in EtakMap format to contain all of the
`streets. with their names and address ranges. in the
`United States. Etalt‘s cassette tape holds 3.5 Mb.
`which is sufiidcnt for approximately the same
`information as shown in two typical folded paper
`street maps. lncvitably. the current trend is towards
`Compact Disk because the speed is workable and
`the storage available is capacious.
`
`Images, vectors, topology and geometry
`
`The simplest digital map representation to acquire
`and display is the bit—niappcd image. It is also the
`least informative to the navigation software and
`most voracious in memory requirements. Map
`matching systems cannot use such images nor are
`images useful for destination finding. They only
`support display and. in any event, only at one scale
`and in one or a very few orientations: thus an
`iipsitle-down image would not he readable. This is a
`severe limitation since most systems display the map
`with the heading of the vehicle being towards the
`top of the display. the so-called ‘heading-up’
`tKI:nl£l(i0n d('sCflbL’(.l above.
`
`A more useful form of map cncoding for
`n|I\':;.'l:OH software is the vector encoding. in which
`line-r rt-atures are encoded as directed line
`
`srgncns xectors » or sequences of segments (see
`Eguilol.-i mg Honing l99l in this volume). This
`enacting i. i.-r -~-' ii. compact but is much more
`only in ..L.1lu..'r. 1' . _-n support rudimentary map
`matdiing .-rm: _‘~:x:~~'; »
`«tell as variations in scale
`and onenutnc: Sm,-ii ..- dug vectors (i.e storing
`the equivalent --t’ :~:‘~ -"er cauunandsl is not.
`however. sumcicnt ‘.-2 ;u:rir'.r..ling nor is it
`adequate for s. ’f\'l-.\2i.'A'-.l.'..l mar matching that uses
`the network topology in its t.:ltu‘..:!i- -r-.~ On the
`
`122
`
`other hand. a geometrical eiicodiiig which includes
`topology fully supports map matching and display.
`Map matching requires the geometry of the road
`network for comparing and matching the dead
`reckoned path with streets; it also requires the
`geometry for evaluating possible matches against
`paths permitted in the road network topology. For
`exaiiiple, a road connected to the previously
`‘occupied’ road is more likely to be the one
`currently occupied by the vehicle than one that is
`not connected but which is near by.
`.
`In additioit to applications that directly use
`topological inforiiiation from the map, the well-
`known advantages of topological encoding for error
`detection and control. consistency of feature
`attribute assignment and control of digital map
`maintenance all favour such a method of encoding.
`Furthermore. topological data can be used to
`improve retrieval speed, which is quite important
`and is discussed below. Etak uses a topological
`encoding that also includes generalized views; these
`are themselves topological encodings of generalized
`maps computed from the detailed digital map.
`These views are used for small scale displays and
`will be used in the future for pathfinding over large
`distances. In this case, topology in both the fully
`detailed map and the generalized maps is required
`for pathfinding
`
`Retrieval
`
`There are three different types of map retrieval
`criteria used in vehicle navigation. The first is
`window retrieval. which is used to retrieve map data
`surrounding the vehicle or the destination; these
`data are used both for map matching and display.
`Second is retrieval by attributes. such as address or
`street intersection, for destination finding. The third
`criterion is topological. which is used in pathfinding.
`Map retrieval while driving must keep pace
`with the vehicle. That is, regardless of the vehicles
`speed. map data for all the streets surrounding the
`vehicle must be in RAM for use by the map
`matching algorithm. Depending on the scale of the
`display, all or a selection of streets and other
`features must be in RAM for display. This is a very
`difficult requirement to meet given the constraints
`of in—vehicle systems. particularly the slow speed of
`mass storage and limits on amount of RAM
`available. For the Etak Nzix-igator, the mass storage
`
`is cassette tzipe
`256 Kb RAM. ‘l
`
`Etak orgatiizeil
`neighbouring to
`This reduced th
`
`time quite dran
`iniplemcntaiiur
`The coiisti
`
`determined by
`system must lin
`olwaiting. Typi
`ll) seconds or »
`
`but probably tic
`finding.
`
`Seamless map
`
`Various cooidil
`
`use in nayigauu
`distance and he
`
`reckoning and.
`map sheets. C»
`projection para
`coordinates im
`but have the and
`
`over the region
`ellipsoid is used
`re fc rcnce for (‘i
`
`appears likely '
`using GPS.
`For pathfll
`connected giap
`and environs t
`
`adjacent counlx
`origin in one on
`This means that
`seamless. at In
`
`it
`Pzithfinding s.
`the digital stroc
`retrieval calls. ‘
`
`task of map ma
`these are not qt
`
`Digital map pt
`
`Providing digit:
`out above is a r
`business of am:
`
`fact has impede
`
`
`
`

`
`neighbouring features were usually near by on tape.
`This reduced the number of searches and the seek
`
`time quite dramatically over many GIS
`implementations.
`The constraints for attribute-based retrieval are
`
`determined by human factors considerations. The
`system must find a destination before the user tires
`of waiting. Typically this constrains the retrieval to
`10 seconds or 50. Similarly. pathfinding must be fast
`but probably need not be as fast as destination
`finding.
`
`Seamless map and coordinate systems
`
`Various coordinate systems have been proposed for
`use in navigation. Plane projected systems simplify
`distance and heading computations for dead
`reckoning and map matching, at least within single
`map sheets. Complications arise at the seams where
`"projection parameters change. Geodetic
`coordinates involve more complicated calculations
`but have the advantage of being seamless, at least
`over the region that the same approximating
`ellipsoid is used. The WGS84 ellipsoid is the global
`reference for GPS (Global Positioning System) and
`appears likely to be adopted even for systems