`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-00448
`
`1
`
`
`
`2
`
`
`
`GEOGRAPHICAL INFORMATION SYSTEMS
`
`3
`
`
`
`GEOGRAPHICAL
`
`INFORMATION SYSTEMS
`
`PRINCIPLES AND APPLICATIONS
`
`EDITED BY
`
`DAVID J MAGUIRE,
`
`MICHAEL F GOODCHILD
`
`AND
`
`DAVID W RHIND
`
`> I > Longman
`Scientific &
`1 Technical
`Copublished in the United States and Canada with
`John Wiley & Sons, Inc., New York
`
`4
`
`
`
`Longman Scientific and Technical,
`Longman Group UK Ltd
`Longman House, Burnt Mill, Harlow,
`Essex CM20 2JE, England
`and Associated Companies throughout the world.
`
`copublished in the United States and Canada with
`John Wiley & Sons, Inc., 605 ThirdAvenue, New York,
`NY 10158
`
`© Longman Group UK Limited 1991
`
`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, 9()
`Tottenham Court Road, London WIP 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 of infringement of the
`trademark.
`
`First published 1991
`
`British Library Cataloguing in Publication Data
`Maguire, David J.
`
`Geographical information systems: Principles and
`applications
`I. Title
`II. Goodchild, Michael F.
`III. Rhind, David W.
`910.901
`
`ISBN 0-582-05661-6
`
`Library of Congress Cataloging-in-Publication Data
`Maguire, D. J. (David J.)
`Geographical information systems / by D. J. Maguire,
`Michael F. Goodchild, and David W. Rhind.
`p.
`cm.
`
`Includes bibliographical references and index.
`Contents: V. 1. Principles- v.2. Applications.
`ISBN 0-470-21789-8
`
`1. Geographical information systems.
`I. Goodchild, Michael F.
`II. Rhind,
`David.
`III. Title.
`G70.2.M354
`1991
`910’.285 - dc20
`
`91-3724
`
`5
`
`
`
`lkwwmdmmemmmwof
`
`DAVID S SIMONETT
`
`1926—90
`
`David Simonett was born in Australia in 1926. After earning a Doctorate at the
`University of Sydney, he became a leading pioneer in the field of Remote Sensing,
`holdingfaculty positions at the University of Kansas, the University of Sydney and
`the University of California, Santa Barbara. He was director of land use applications
`at Earth Satellite Corp from 1972 to 1975.
`
`As Chair at Santa Barbarafrom 1975, he was able to build one of the foremost
`Geography programs in the US, culminating in 1988 with the establishment of the
`National Center for Geographic Information and Analysis. The Santa Barbara site
`of the Center was renamed the David Simonett Centerfor Spatial Analysis in 1990 in
`recognition of his role in its creation. He received the Honours Awardfrom the
`Association ofAmerican Geographers and the Victoria Medalfrom the Royal
`Geographical Society.
`
`David Simonett lost a courageous fight against cancer on December 22, 1990 in
`the course of the preparation of his contribution to this book. The editors dedicate
`this book to his memory and to the outstanding role he has played in the
`development of thefield of Geographical Information Systems.
`
`6
`
`
`
`Preface
`List of contributors
`Acknowledgements
`
`Section I Overview
`
`Introduction
`
`D J Maguire, M F Goodchild and D WRhir1d
`
`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 Buxtori
`
`6. The academic setting of GIS
`D J Unwiri
`
`7. The organizational home for GIS in the scientific
`professional community
`J L Morrison
`
`91-100
`
`8. A critique of GIS
`R T/langeenbrug
`
`Section II Principles
`
`Introduction
`
`M F Goodchild, D W Rhirzd and D J Maguire
`
`111-17
`
`7
`
`
`
`VOLUME1
`
`:
`
`PRINCIPLES
`
`(a) Nature of spatial data
`
`9. Concepts of space and geographical data
`A C Gatrell
`
`10. Coordinate systems and map projections for GIS
`D H Maling
`
`11. Language issues for GIS
`A U Frank and D M Mark
`
`12. The error component in spatial data
`N R Chrisman
`
`13. Spatial data sources and data problems
`P F Fisher
`
`14. GIS and remote sensing
`F WDavis and D S Simonett
`
`119-34
`
`135-46
`
`147-63
`
`165-74
`
`175-89
`
`191-213
`
`(b) Digital representation
`
`15. Computer systems and low—level data structures for GIS
`Wm R Franklin
`
`215-25
`
`16. High—level spatial data structures for GIS
`M J Egenhofer and J R Herring
`
`17. GIS data capture hardware and software
`M J Jackson and P A Woodsford
`
`227-37
`
`239-49
`
`8
`
`
`
`18. Database management systems
`R G Healey
`
`19. Digital terrain modelling
`R Weibel and M Heller
`
`20. Three—dimensional GIS
`
`J FRaper and B Kelk
`
`(c) Functional issues
`
`21. The functionality of GIS
`D J Maguire and J Dangermond
`
`22. Information integration and GIS
`I D H Shepherd
`
`23. Cartographic modelling
`C D Tomlin
`
`24. Spatial data integration
`R Flowerdew
`
`251-67
`
`269-97
`
`299-317
`
`319-35
`
`337-60
`
`361-74
`
`375-87
`
`25. Developing appropriate spatial analysis methods for GIS
`S Openshaw
`
`389-402
`
`26.
`
`27.
`
`Spatial decision support systems
`P J Densham
`
`Knowledge—based approaches in GIS
`T R Smith and Je Yiang
`
`403-12
`
`413-25
`
`9
`
`
`
`VOLUME1
`
`:
`
`PRINCIPLES
`
`((1) Display issues
`
`28. Visualization
`
`B P Battenfield 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 of acronyms
`'
`Author index
`Subject index
`
`427-43
`
`445-56
`
`457-75
`
`477-88
`
`489-502
`
`503-13
`
`515-30
`
`531 -5 91
`593-598
`599-613
`615-649
`
`10
`
`
`
`Preface
`List of contributors
`Acknowledgements
`
`Section III Applications
`
`Introduction
`
`D WR/zirid, D J Maguire and M F Goodchild
`
`(a) National and international GIS programmes
`
`35. A USGS perspective on GIS
`L E Starr and K EAriders0n
`
`36. Development of GIS—related activities at the
`Ordnance Survey
`M Sowtorz
`
`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 O’Callagharz 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 Rhind
`
`45. GIS and market analysis
`J R Beaumont
`
`11
`
`11
`
`
`
`VOLUME2
`
`: APPLICATIONS
`
`(c) Environmentalapplications
`
`46. Soil information systems
`P A Burroagh
`
`47. Integration of geoscientific data using GIS
`G FBonham—Carter
`
`153-69
`
`171-84
`
`48. Multisource, multinational environmental GIS: lessons
`learnt from CORINE
`
`185-200
`
`H M Moansey.
`
`49. Environmental databases and GIS
`J R G Townshend
`
`50. Global databases and their implications for GIS
`D M Clark, D A Hastings and JJ Kineman
`
`(d) Management applications
`
`51. GIS and public policy
`H W Calkins
`
`52. Urban GIS applications
`R Parrott and F P Statz
`
`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
`
`201-16
`
`217-31
`
`233-45
`
`247-60
`
`261-73
`
`275-83
`
`285-95
`
`56. Integrated planning information systems
`D J Cowen and W L Shirley
`
`297-310
`
`Section IV Epilogue
`
`Epilogue
`D W Rhind, M F Goodchild and D J Magaire
`
`Consolidated bibliography
`
`313-27
`
`329-389
`
`12
`
`
`
`CAR NAVIGATION SYSTEMS
`
`M WHITE
`
`Automobile navigation is a demanding application of digital maps and appears
`likely to become a common and economically important one. A few systems are
`commercially available and many prototypes exist. These systems determine location
`using wheel rotation sensors, solid state compasses, 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
`functions performed in addition to location determination (such as map display,
`verbal directions, pathfinding and destination finding by address or landmark).
`Typical map requirements for particular systems include positional 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 projects, just a few commercial
`operations and some fledgling consortia which have as their mission the production
`of digital maps for navigation or the promulgation of standards for such maps. All
`systems require faster retrieval than GIS systems have typically provided.
`Applications using navigation systems include experimental traffic systems, such as
`traflic congestion reporting and ‘sign-post’ transmitters and receivers for
`communicating with on-board navigation systems.
`
`INTRODUCTION
`
`The automobile is becoming a 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 for factory—installed
`systems appears to be huge. In Japan, Nissan has
`been selling more than 1000 systems per month as
`an option on the Nissan Cedric. This option is a
`combination of navigation system and television
`(which can only be operated with the vehicle
`stopped). In Germany, Bosch began to sell the
`Travelpilot in 1989. In 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, perhaps less than US $500. 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 $100 million in 1994 (Frost &
`Sullivan 1989).
`
`Car navigation uses maps intensively. The map
`must provide information for:
`
`0
`
`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. The
`infancy of the technology is reflected in the meagre
`
`13
`
`13
`
`
`
`M White
`
`
`
`Fig. 43.2 The Honda Gyrocator screen (courtesy author).
`
`purchases the vehicle. In Japan, the Toyota Crown
`and the Nissan Cedric have offered factory—instal1ed
`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.1 and Figs. 43.1 and 43.2)
`
`
`
`
`
`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
`textually or by voice. Then applications 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 concerned.
`From this, it will become evident that navigation
`and related applications require a topologically
`encoded and seamless database, 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 Etak Navigator has
`been available since 1985. The Bosch Travelpilot, a
`derivative of the Etak Navigator, became available
`
`Fig. 43.1 The Nissan Cedric screen (courtesy
`author).
`
`In addition, there are several experimental
`
`14
`
`
`
`E
`
`42¢”?
`
`....~‘»
`
`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 CARIN
`(Thoone 1987), Clarion NAVI and the UK
`Autoguide (Catling 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’ GIS require and, at the same time,
`demand a faster response rate than available GIS
`offer. In addition, navigation algorithms and their
`implementation have involved substantial
`expenditure. The commercial stakes are high and,
`accordingly, secrecy prevails on the internal details
`of each vendor’s offerings.
`
`POSITION DETERMINATION
`
`Navigation includes determination of position as
`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 Travelpilot
`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.
`
`15
`
`15
`
`
`
`7|
`
`.....
`
`4'o
`
` _J
`Fig. 43.4 Dead reckoning— computing a new
`position from heading (h) and distance (d).
`
`For determining the heading, two
`measurements are taken. An absolute heading
`estimate is made using a solid—state compass (e. g.
`see Phillips 1987) and a relative heading is
`computed from the wheel sensor measurements. A
`solid state compass (i.e. a two-axis magnetometer)
`measures two components of the ambient magnetic
`field; from this the horizontal component of the
`earth’s magnetic field is computed. There are many
`physical considerations involved such as the
`magnetic flux focusing effect of the steel in the
`vehicle and the local magnetic declination.
`However, all mapping considerations eventually
`come down to using the approximate position of the
`vehicle, a model of the earth’s magnetic field and
`the measured magnetic field. An important
`consideration for in-vehicle applications is dip
`angle, the angle that the plane of the compass
`makes with the earth’s magnetic field vector. The
`earth’s magnetic field is horizontal only at the
`magnetic equator, which coincides approximately
`with the geographical equator. So the compass
`measures the magnetic field vector projected on to
`its own plane. While this is normally close to
`horizontal, local variations in ground slope caused
`by hills and the road crown may amount to several
`degrees and affect the compass/magnetic field
`relationship accordingly. Computation of the
`heading from compass measurements must take all
`these effects into consideration.
`The difference in the distance travelled on two
`opposing wheels depends on the change in heading.
`When travelling straight ahead (i.e. without heading
`change), the two wheels travel the same distance.
`When turning, the outside wheel travels further
`
`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
`Positioning System) receiver, a LORAN-C receiver
`and an optical speed sensor.
`A gyroscope (more commonly a ‘gyro’) is a
`spinning mass and the vehicle’s turning rate is
`measured indirectly by measuring forces resulting
`from the conservation of momentum; such forces
`can be experienced by holding a spinning 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
`inclinometer measures the angle of inclination of a
`stationary (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 inclinometer 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 (1986).
`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 comparing signals from multiple
`transmitters and determining receiver location from
`known transmitter positions and signal propagation
`times. The LORAN-C transmitters are based on the
`ground and the GPS 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
`
`16
`
`118
`
`16
`
`
`
`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 sensor
`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 combined 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 also 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 errors
`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
`information 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 error
`from dead reckoning. The path travelled is
`determined by dead reckoning or radio location and
`
`17
`
`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.
`
`
`
`Fig. 43.5 Map matching — identifying a DR path
`(dashed line) with streets on the map.
`
`By way of an example, one would eventually
`accumulate significant error using only DR while
`wandering along city streets. Through comparing
`the DR path to the map, however, the navigation
`algorithm can eliminate errors that accumulate from
`sensor noise. Etak pioneered the map matching
`approach (see Honey et al. 1989) for the Navigator.
`The Bosch Travelpilot uses the same approach and
`the Nissan Cedric uses a similar map matching
`method. Such map matching depends on the driver
`staying mainly on the roads; it is inappropriate for
`automatic guidance of a vehicle. In this approach,
`heading as well as position is determined as an
`output of map matching and is used for orienting
`the map displayed to the driver. Experience
`indicates that the impression given by a map display
`with a slightly ‘wrong’ orientation is that the
`computer is lost or will be soon — somewhat like the
`impression of a misaligned street name on a printed
`map. For this reason, map matching methods are
`used to orient and position the display even for
`absolute location methods, such as radio location.
`Other navigation approaches that have been
`tried require extensive infrastructure, such as
`
`17
`
`
`
`also be coupled with broadcast traffic information.
`In Japan, the Advanced Mobile Traffic Information
`and Communication System (AMTICS) project was
`a test of such a concept (Tsuzawa and Okamoto
`1989). The PATHFINDER project in the Los
`Angeles region is intended to gather information
`about alternative routes drivers select when
`
`provided with traffic congestion information
`(Wasielewski 1988).
`
`Display and report
`
`All of the commercially available systems display
`map and vehicle location information graphically on
`a dash-mounted CRT. Some work has been done to
`
`present instructions by voice, but this approach is
`still in early development stages. Regardless of the
`method, safety is paramount. Map displays in this
`context are a dashboard instrument and must
`
`provide the needed information at a glance and
`must not distract the driver. When audio systems
`become available, they will also be required to
`facilitate driving, but not distract the driver’s
`attention. As a result, the human interface must
`conform to dashboard instrumentation design
`guidelines. For visual displays, this includes letter
`and symbol sizes in terms of subtended angle for the
`driver and readability at a glance. In the case of
`audio output, sounds must be non-distracting and
`easily understood.
`So far as map displays in cars are concerned,
`heading—up orientation (i.e. displaying the map so
`that ‘up’ on the display is ‘ahead’ on the ground and
`hence left and right on the display show features
`that are left and right of the vehicle respectively)
`makes the display much simpler to understand and
`read at a glance. In the Etak Navigator and Bosch
`Travelpilot, the display is heading up with some
`hysteresis in the heading adjustment to avoid a
`‘jumpy’ display. The Nissan Cedric permits display
`at only the four cardinal headings and operates in a
`‘near heading up’ mode. In addition, more
`generalized views provided through smaller scale
`map presentations are also quite helpful to a driver
`for choosing routes or just learning context. All
`commercially available systems provide generalized
`views. For a map to be readable at a glance, very
`
`18
`
`120
`
`oauiurumnr‘
`
`‘‘
`
`C BLAUPUNKY
`
`Fig. 43.6 Etak map displays at three scales
`showing few feature labels (courtesy author).
`
`little annotation is possible. All three of the systems
`mentioned show only four or five feature labels at
`one time. Figure 43.6 shows three displays from the
`Travel pilot at various scales, each showing only a
`few labels. The labels shown were chosen by an
`algorithm that favours more important streets, the
`selected destination street and the street on which
`
`the car is currently placed.
`
`18
`
`
`
`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 pathfinding 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).
`
`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 determination, provide very fast retrieval
`and use an appropriate coordinate system.
`
`Storage media
`
`§§L££l_§lEE£I
`
`RHIZNnN
`HRYTE
`HHVTE PARK
`
`H!EH}YflH
`HICKERT
`
`AEANEEL
`:SFELL
`
`HIEKET
`
`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,
`
`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
`
`19
`
`19
`
`
`
`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 10 seconds. These
`relatively slow speeds impose noteworthy
`challenges and severe constraints for the retrieval
`software, which are discussed below.
`Digital maps also consume considerable space.
`Each 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. Etak’s cassette tape holds 3.5 Mb,
`which is sufficient for approximately the same
`information as shown in two typical folded paper
`street maps. Inevitably, 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-mapped 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
`upside-down image would not be 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’
`orientation described above.
`
`A more useful form of map encoding for
`navigation software is the vector encoding, in which
`linear features are encoded as directed line
`
`segments (vectors) or sequences of segments (see
`Egenhofer and Herring 1991 in this volume). This
`encoding is far more compact but is much more
`costly to acquire. It can support rudimentary map
`matching and display as well as variations in scale
`and orientation. Simply coding vectors (i.e. storing
`the equivalent of plotter commands) is not,
`however, sufficient for pathfinding nor is it
`adequate for sophisticated map matching that uses
`the network topology in its calculations. On the
`
`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
`example, 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 addition to applications that directly use
`topological information 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 vehicle’s
`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 const