Van Kreveld M., Nievergelt J., Roos T., Widmayer P. (eds.) Algorithmic Foundations of Geographic Information Systems

Подождите немного. Документ загружается.

Lecture Notes in Computer Science

Edited by G. Goos, J. Hartmanis and J. van Leeuwen

1340

Advisory Board: W. Brauer D. Gries J. Stoer

Marc van Kreveld Jtirg Nievergelt

Thomas Roos Peter Widmayer

(Eds.)

Algorithmic Foundations

of Geographic

Information Systems

~ Springer

Series Editors

Gerhard Goos, Karlsruhe University, Germany

Juris Hartmanis, Cornell Universitg NY, USA

Jan van Leeuwen, Utrecht University, The Netherlands

Volume Editors

Marc van Kreveld

Utrecht University, Department of Computer Science

RO. Box 80.089, 3508 TB Utrecht, The Netherlands

E-mail: marc@cs.ruu.nl

Jtirg Nievergelt

Thomas Roos

Peter Widmayer

ETH Zentrum, Department of Computer Science

CH-8092 Ztirich, Switzerland

E-mail: {jn/roos/widmayer } @inf.ethz.ch

Cataloging-in-Publication data applied for

Die Deutsche Bibliothek - CIP-Einheitsaufnahme

Algorithmic foundations of geographic information systems / Marc

van Kreveld ... (ed.). - Berlin ; Heidelberg, New York ; Barcelona ;

Budapest ; Hong Kong ; London ; Milan ; Paris ; Santa Clara ;

Singapore ; Tokyo : Springer, 1997

(Lecture notes in computer science ; Vol. 1340)

ISBN 3-540-63818-0

CR Subject Classification (1991): H.2, H.3, E.1, E.2,F.2, J.2

ISSN 0302-9743

ISBN 3-540-63818-0 Springer-Verlag Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is

concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,

reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication

or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,

in its cun'ent version, and permission for use must always be obtained from Springer -Verlag. Violations are

liable for prosecution under the German Copyright Law.

O Springer-Verlag Berlin Heidelberg t997

Printed in Germany

Typesetting: Camera-ready by author

SPIN 10647927 06/3142 - 5 4 3 2 1 0 Printed on acid-free paper

Preface

Algorithmic

Foundations of GIS

This volume aims to bring together the two lines of research whose interaction

promises to have significant practical impact in the near future: the application-

oriented discipline of Geographic Information Systems (GIS) and the technicM

discipline of geometric computation, or in particular, geometric algorithms and

spatiM data structures. GIS are complex systems consisting of a database part

and a spatial data handling part. Spatial data handling in current GIS is less

well-developed than the database aspects, and it is in relation to the spatial

aspects that geometric algorithms and modeling can stimulate progress in GIS.

GIS include many geometry-related problems such as spatial data storage and

retrieval, visualization of spatial data, overlay of maps, spatial interpolation, and

generalization.

Geometric Algorithms and GIS

Algorithms research has been an integral part of computer science since its be-

ginnings. The goal is to design well-defined procedures that solve well-defined

problems, and analyze their efficiency. Numerical algorithms were studied most

thoroughly in the first phase of automated computation, and data management

algorithms for sorting and searching became prominent in the 1960s. In the

second half of the 1970s the systematic study of geometric algorithms gave birth

to the discipline known today as computational geometry. The motivation for

studying geometric algorithms comes from areas like robotics, computer graph-

ics, automated manufacturing, VLSI design, and GIS.

The collaboration of GIS research and computational geometry has intensi-

fied in recent years, for several reasons. Firstly, the availability of geographic

data in digital form is increasing rapidly. The acquisition of geographic data and

the digitizing of maps are laborious, time-consuming tasks, and without appro-

priate digital data, GIS cannot operate effectively. Secondly, improved hardware

now makes it possible to store and process large amounts of geographic data and

to produce high-quality maps on computers. Thirdly, the research community in

computational geometry, after having laid the conceptual and technicM founda-

tion, has recently shifted its attention toward more practical and more applied

solutions.

Collaboration of GIS and Computational

Geometry

The time is right for further development of the spatial components of GIS, as a

result of joint efforts from computational geometry and GIS. What should such a

collaboration look like? Many standard geometric problems and solutions, even

those without any explicit reference to geography, are useful to GIS. Storing

polygonal subdivisions on primary or background storage for efficient window-

ing queries is one example. Implementation and testing of data structures and

query algorithms reveals their usefulness to GIS. Most of the basic algorithms

developed in computational geometry, however, are not directly applicable to

GIS. This is because standard geometric problems are often simplified to such

an extent that they neglect important requirements of GIS. In addition, many

problems arising in GIS have not yet been formalized in sufficient detail for the

design of efficient algorithms.

As an example, consider generalization of maps. When the scale of a map

is reduced, less information can be shown on the map, so it is necessary to

remove or simplify certain objects on the map. However, it is far from clear

which objects to remove or simplify. Different cartographers would produce

different maps, if they were to generalize a map manually. A first step towards

an automated map generalization method is the modeling of what should be

generalized, when this is necessary, and how. These modeling questions cannot

be answered by someone without cartographic knowledge. On the other hand,

computational geometers are trained to abstract a problem into a form that is

well defined. The joint knowledge of a cartographer and a geometer can result

in a good model, a specification, for automated map generalization. Given such

a specification, algorithms can be designed and implemented to compute the

desired output.

There are several staxldard geometric structures and algorithms useful in GIS,

with or without some modifications. These include topological data structures

like the doubly-connected edge list or quad edge structure, spatial data structures

like the quadtree and R-tree, the Voronoi diagram, the Delaunay triangulation.,

map overlay and buffer computation, and visualization algorithms. Most of these

structures and algorithms are also used in other fields like computer graphics and

robotics. They are well documented in textbooks or other standard texts.

Chapters in this

Volume

This volume on algorithmic foundations of GIS contains a collection of survey

papers on algorithms for spatial data. Standard texts on GIS and computational

geometry are a starting point and not discussed in their generality here. But for

completeness, references to those works are included.

Chapter 1 traces the history of the development of geometric computing,

and illustrates some of its characteristic features. It explains how apparently

simple algorithms pose difficult technical problems in the presence of degenerate

data configurations. This fact turns the implementation of correct and robust

algorithms, even if their logical structure is simple and clear, into a challenge

that few programmers can meet successfully. Thus, basic geometric algorithms

must be made available to application programmers in the form of program

libraries developed by specialists. We present an example.

Chapter 2 discusses tile use of Voronoi diagrams in GIS. It presents a general

framework for handling fully dynamic and kinematic Voronoi diagrams for points

and extended spatial objects~ The Voronoi approach greatly simplifies some of

the basic traditional GIS queries, such as map overlay and proximity queries,

and even allows new types of higher level queries.

Chapter 3 contains a treatment of digital elevation models in GIS, with em-

phasis on TINs and algorithms. Although gridded elevation models are more

widely used in current GIS than TINs, the advantages of TINs cannot be ig-

nored. The grid is usually chosen for its simplicity, but this chapter shows that

simple algorithms can solve the basic computations on the TIN model as well.

Chapter 4 gives a treatment of the visualization of terrains. Techniques for

hidden surface removal like depth-sorting and visibility map computation are

covered. The chapter also describes levels of detail in terrains to allow for a

hierarchical multiresolution model.

Chapter 5 discusses the cartographically challenging problem of generaliza-

tion. An overview is given of the types of generalization, the various approaches

that have been attempted, and recent developments. Since generalization is a

task that first needs a proper modeling, emphasis is placed on the modeling

aspects.

Chapter 6 contains an extensive overview of spatial data structures that can

be used on background storage. The design of such a structure obviously depends

on the queries it should support efficiently. All structures are based on either

an organization of the data objects or on an embedding of the underlying space.

Design principles are usually based on common sense and simplicity.

Chapter 7 is dedicated to the design and analysis of space-filling curves in

GIS. It presents an approach to theoretically evaluate the performance of range

queries under a practical cost model that takes into account the number and

locality of the data accesses.

Chapter 8 gives a treatment of algorithms on background storage. The as-

sumption is that in GIS the amount of data that is input for an algorithm is

often too large to fit in main memory. External memory algorithms attempt

to minimize the number of block exchanges between main and external mem-

ory, since this affects the running time of the algorithm much more than the

processing time itself. Several of these algorithms were based on common data

structures for main memory, but have been adapted to work well on secondary

storage.

Chapter 9 covers techniques for realizing precision and robustness in geomet-

ric computing. Standard geometric algorithms assume that real numbers can be

stored and exact computation can be done. In practice, these assumptions are

false, leading to false output and unexpected behavior of theoretically correct

Vll

algorithms. There have been important developments recently in this practical

aspect of geometric computing. To guarantee consistent output of a geometric

algorithm, various advanced techniques may be needed.

As the editors of the book we take the opportunity to thank the contributing

authors for their chapters, which in our opinion are excellent texts to be used

for graduate student courses on GIS and applied geometric algorithms.

This book originated from the CISM Advanced School on the Algorithmic

Foundations of Geographic Information Systems, which was held in Udine, Italy,

from September 16 to 20, 1996. During the school, course material was dis-

tributed. Later, these course notes were revised and rewritten to form the chap-

ters of this book. We thank the CISM for their support in the organization of

the school, and their hospitality during the school. Finally, we acknowledge the

support of the CGAL-project (ESPRIT IV LTR Project No. 21957), which has

its homepage at http ://www. cs. ruu. nl/CGAL/.

October 1997

Marc van Kreveld

Jiirg Nievergett

Thomas Roos

Peter Widmayer

International Centre for Mechanical Sciences

Centre International des Sciences M~caniques

CISM Palazzo del Torso

Piazza Garibaldi 18

33100 Udine, ItMy

E-maih cismOhydrus, cc .uniud. it

WWW: http ://www .uniud. it/cism/homepage, htm

VIII

Contents

Introduction

Software

Jiirg Nievergelt

to Geometric Computing: From Algorithms to

History of Geometry ......................... 1

1.1 Geometry: A Tool for Processing Spatial Data ...... 1

Geometry Enters the Computer Age ................ 4

The Interplay of Algorithm and Data Structure .......... 6

Degeneracy, Robustness, and the Quest for Perfection ...... i0

The XYZ GeoBench: A Program Library for Algorithm Animation 13

5.1 Architecture and Components of the GeoBench ...... 13

5.2 User Interface and Algorithm Animation .......... 14

5.3 Interchangeable Arithmetic and Parameterized Floating

Point Arithmetic ....................... 16

5.4 The Program Library: Experimental Performance Evalu-

ation .............................. 17

Conclusion

..............................

2. Voronoi Methods in GIS

Christopher M. Gold, Peter R. RemmeIe, and T. Roos

Introduction and Historical Background .............. 21

Voronoi Diagrams .......................... 23

2.1 Static Voronoi Diagrams ................... 23

2.2 Kinematic Voronoi Diagrams ................ 25

2.3 Dynamic Voronoi Diagrams ................. 26

GIS - A New Approach ....................... 27

3.1

3.2

3.3

3.4

3.5

3.6

Conclusions

Traditional GIS Operations ................. 28

Separating the Topology from the Map Data ....... 29

The Intersection Problem .................. 30

Update Management ..................... 31

Navigation and Interpolation ................ 32

Map Partitioning and Parallel Processing ......... 32

.............................. 32

3. Digital Elevation Models and TIN Algorithms

Marc van Kreveld

1 Introduction .............................. 37

2 Terrain Models and Representation ................. 38

2.1 The Regular Square Grid .................. 38

2.2 The Contour Line Model .................. 39

2.3 The Triangulated Irregular Network Model ........ 40

2.4 Hierarchical Models ..................... 41

3 Access to TINs ............................ 42

3.1 Traversal of a TIN ...................... 42

3.2 Efficient Access to a TIN .................. 44

3.3 Windowing .......................... 46

4 Conversion between Terrain Models ................ 46

4.1 From Point Sample to TIN ................. 46

4.2 From Grid to TIN ...................... 47

4.3 From Contour Line to TIN ................. 52

5 Mathematical Computations on Terrains .............. 53

5.1 Adding and Subtracting Terrains .............. 53

5.2 Squaring a Terrain ...................... 54

6 Computation of Contour Lines ................... 55

6.1 Direct Computation of Contour Lines ........... 55

6.2 Preprocessing for Contour Lines .............. 56

6.3 Classification ......................... 59

7 Topographic Features ........................ 62

7.1 Points on Terrains ...................... 63

7.2 Valleys and Ridges ...................... 63

7.3 Curvature ........................... 64

7.4 Drainage Information .................... 66

8 Miscellaneous Applications ..................... 70

8.1 Paths in Terrains ....................... 70

8.2 Viewshed Analysis ...................... 70

8.3 Temporal Aspects of Terrains ................ 71

8.4 Statistical Analysis of Elevation Data ........... 71

9 Conclusions .............................. 72

4. Visualization of TINs

Mark de Berg

1 Introduction .............................. 79

2 The Basics .............................. 80

3 Hidden-Surface Removal ....................... 82

3.1 Depth-Sorting Methods ................... 83

3.2 Object-Space Methods .................... 86

4 Levels of Detail ............................ 90

5 Other Issues .............................. 96

Generalization of Spatial Data:

rithms

Robert Weibel

Principles and Selected Algo-

Introduction .............................. 99

What is Generalization and Why Does It Matter? ........ 100

2.1 The Issue of Scale Change .................. 100

2.2 Defining Generalization ................... 101

2.3 Motivations of Generalization ................ 102

3 Different Views of Digital Generalization .............. 103

3.1 Generalization as a Sequence of Modeling Operations . . 104

3.2 Generalization Strategies .................. 105

4 Conceptual Frameworks of Generalization ............. 107

4.1 The Model by Brassel and Weibel ............. 107

4.2 The Model by McMaster and Shea ............. 108

4.3 A Closer Look at Generalization Operators ........ !09

5 Generalization - The Role of Algorithms .............. 111

6 The Choice of Spatial Data Models - Raster or Vector? ..... 113

7 Basic Algorithms - Context-Independent Generalization ..... 114

7.1 Object Selection/Elimination ................ 114

7.2 Line Simplification ...................... 116

7.3 Line Smoothing ........................ 124

8 Operator Sequencing ......................... 125

9 Model Generalization - The Example of TIN Filtering ...... 126

10 An Assessment of Basic Algorithms ................. 129

10.1 What's Wrong with Basic Algorithms? ........... 130

10.2 What Should Be Improved? ................. 130

11 Constraint-Based Methods ...................... 131

12 Methods for Structure and Shape Recognition ........... 133

12.1 Motivation and Objectives .................. 133

12.2 Characterization and Segmentation of Cartographic Lines 133

12.3 Terrain generalization .................... 135

13 Alternative Data Representations and Data Models ........ 137

13.1 Representations for Geometric Primitives ......... 139

13.2 Complex Data Models .................... 140

14 Conclusions .............................. 144

Spatial Data

Structures: Concepts and Design

Choices

Jiirg Nievergelt and Peter Widmayer

153

Goals and Structure of this Survey ................. 153

Data Structures Old and New, and the Forces that Shaped Them 155

2.1 Prehistory, Logical vs. Physical Structure ......... 155

2.2 Early Scientific Computation: Static Data Sets ...... 157

2.3 Commercial Data: Batch Processing of Dynamic Sets, Sin-

gle Key Access ........................ 157

2.4 Transaction Processing: Interactive Multikey Access to

Dynamic Sets ......................... 158

×l