GIS A Computing Perspective Second Edition TThhiiss ppaaggee iinntteennttiioonnaallllyy lleefftt bbllaannkk GIS A Computing Perspective Second Edition Michael Worboys University of Maine USA Matt Duckham University of Melbourne Australia CRC PR ESS Boca Raton London New York Washington, D.C. CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2004 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20160421 International Standard Book Number-13: 978-0-203-48155-4 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http:// www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com ToHelen, andtomyparents,RitaandJohn MD ToMoira andtoBethan,Colin,Ruth,Sophie,Tom,andWilliam MW TThhiiss ppaaggee iinntteennttiioonnaallllyy lleefftt bbllaannkk Preface Geographicinformationsystems(GISs)arecomputer-basedinformation systems that are used to capture, model, store, retrieve, share, manipu- late, analyze, and present geographically referenced data. This book is aboutthetechnology,theories,models,andrepresentationsthatsurround geographic information and GISs. This study (itself often referred to as GIS or geographic information science) has emerged in the last two decadesas an exciting multi-disciplinaryendeavor,spanningsuch areas as geography, cartography, remote sensing, image processing, environ- mental sciences, and computing science. The treatment in this text is unashamedly biased toward the computational aspects of GIS. Within computingscience, GIS is a special interest of fields such as databases, graphics, systems engineering, and computational geometry, being not onlyachallengingapplicationarea,butalsoprovidingfoundationalques- tionsforthesedisciplines. Theunderlyingquestionfacingthismultidisciplinarytopicis“What isspecialaboutspatialinformation?”Inthisbook,weattempttoprovide answers at several different levels: the conceptual and formal models needed to understand spatial information; the representations and data structuresneededtosupportadequateperformanceinGISs;thespecial- purpose interfaces and architectures required to interact with and share spatialinformation;andtheimportanceofuncertaintyandtimeinspatial information. The task of computingpractitionersin the field of GISis to provide theapplicationexperts,whethergeographers,planners,utilityengineers, orenvironmentalscientists,withasetoftools,basedarounddigitalcom- putertechnology,thatwillaidtheminsolvingproblemsintheirdomains. These tools will include modeling constructs, data structures that will allow efficient storage and retrieval of data, and generic interfaces that maybecustomizedforparticularapplicationdomains. Thebookinevitablyreflectstheinterestsandbiasesofitsauthors,in particularemphasizingspatialinformationmodelingandrepresentation, as well as developingsome of the more formalthemes usefulin under- standingGIS.Wehavetriedtoavoiddetaileddiscussionofparticularcur- rentlyfashionablesystems,andconcentrateinsteaduponthefoundations and generalprinciplesof the subjectarea. We have also triedto givean overviewofthefieldfromtheperspectiveofcomputingscience. Not every topic can be covered and we have deliberately neglected two areas, leaving these to people expert in those domains. The first is the historical background. The development of GIS has an interesting history, stretching back to the 1950s. Readers who wish to pursue this topic will find an excellent introduction in Coppock and Rhind (1991), and more in-depth perspectives from many of the pioneers of GIS in Foresman (1998).The other area that is given scant treatmentis spatial analysis, which requires specialized statistical techniques and is judged to be specifically the province of the domain experts. Introductions to spatial analysis include Unwin (1981), Fotheringham et al. (2002), and O’Sullivan and Unwin (2002). The bibliographic notes in Chapter 1 providefurtherreferencestotextsonspecificaspectsofspatialanalysis. WHOSHOULDREADTHISBOOK Thisbookisintendedforreadersfromanybackgroundwhowishtolearn somethingabouttheissuesthatGISengendersforcomputingtechnology. The readerdoesnothave to be a specialist computingscientist: the text developsthenecessarybackgroundinspecialistareas,suchasdatabases, as it progresses. However, some knowledge of the basic components andfunctionalityofadigitalcomputerisessentialforunderstandingthe importance of certain key issues in GIS. Where some aspect of general computingbearsa directrelevanceto our development,the background is given in the text. This book can be used as a teaching text, taking readersthroughthemainconceptsbymeansofdefinitions,explications, and examples.However,the moreadvancedresearcheris notneglected, and the bookincludes an extensivebibliographythat readerscan use to followupparticulartopics. CHANGESTOTHESECONDEDITION Thesecondeditionofthisbookwaswrittenwiththeaim ofmakingthe bookmoreaccessibleto a wideraudience,atthesame timeasretaining thecoreoftriedandtestedmaterial.Chapters1–6havebeenextensively revised, updated, and reformatted from the first edition, although in a fast-moving high-technology area like GIS it was encouraging to find thatthesefundamentalaspectsofGIShaveremainedlargelyunchanged. Chapters 7–10 present almost entirely new material, covering GIS ar- chitectures, GIS interfaces, uncertainty in geospatial information, and spatiotemporalinformationsystems.Thebibliography,index,andallthe diagramshavealsobeencompletelyrevised. In addition to the changes in content, we have tried to produce a moreattractiveandreadableformatforthe book.Thefollowingsection containsmoredetailsontheformattingconventionsusedinthisbookand onthestructureofthebook.Thespelling,grammar,andusageinsecond edition has also changed, from British to American English. We hope thatthischangewillfurtherimprovethe accessibilityof thisbookto an internationalaudience. FORMATTINGUSEDINTHISBOOK Severalformattingconventions,newtothesecondedition,havebeenused in thisbook.Materialthatisrelevantto themainthemesinthetext,but not essential to the reader, is included in gray inset boxes at the top of a page. Typically insets contain more challengingmaterial, and provide some background to each topic, as well as references and links, which readersmaywishtopursue.Alistofinsetsisincludedinthebook’sfront matter. Every chapter begins with a brief summary, outlining the major ideasinthatchapterandhighlightingsomeimportanttermsintroducedin the chapter. At its close every chapter ends with itemized bibliographic notes, providing some key references that readers can follow up. The section numbers alongside the bibliographic notes refer to the relevant sectionsinthemaintext. Throughoutthis book, we have used margin text to allow rapid ref- erence to important terms. When an important term is first defined or introduced, that term will appear in the margin. A corresponding entry canbefoundintheindex,withthepagereferenceinboldtypeface.This enables the reader to use the index rather like an extensive glossary of termsused in this book.Each indexterm hasatmostone boldtypeface pagereference,andatermcanberapidlylocatedwithinapagebyfinding thecorrespondingmarginentry.Inadditiontonormal-andbold-typeface indexentries,thoseindexentriesthatappearinitalicsrefertotermsthat appearwithinagrayinsetbox. STRUCTUREOFTHISBOOK Figure 0.1 indicates the overall structure of interdependencies between chapters.ReadersmayfindithelpfultorefertoFigure0.1totailortheir useofthisbooktotheirownparticularinterests. Chapter1: Motivationandintroductionto GIS;preparatorymaterialon generalcomputing. Chapters2–3: Background material on general databases and for- malismsforspatialconcepts. Chapters4–6: Exposition of the core material, forming a progression from high-level conceptual models, through representations and algorithms, to indexes and access methods that allow acceptable performance. Chapters7–8: Discussion of the types of system architecturesand user interfacesneededforGIS.