CONTENTS
Preface ix
Acknowledgements xiii
Author xv
1. Introduction 1
How Computers Solve Problems 2
How Computers Represent the World: Data Modelling 5
The Structure of a Computer 10
Pseudocode and Computer Programming 15
Further Reading 21
2.Databases 23
What Are Databases and Why Are They Important? 23
Relational Database 29
Storing Spatial Data in a Relational Database 32
Solutions to the Problems of Storing Spatial Data in RDBMS 35
Further Reading 37
3. Vector Data Structures 39
Simple Storage of Vector Data 39
Topological Storage of Vector Data 49
So What Is Topology? 54
And How Does It Help? The Example of DIME 57
More on Topological Data Structures 60
And a Return to Simple Data Structures 64
Further Reading 67
4. Vector Algorithms for Lines 69
Simple Line Intersection Algorithm 69
Why the Simple Line Intersection Algorithm WouldNot Work: A Better Algorithm 74
Dealing with Wiggly Lines 78
Calculations on Lines: How Long Is a Piece of String? 81
Line Intersection: How It Is Really Done 84
Further Reading 935
5.Vector Algorithms for Areas 95
Calculations on Areas: Single Polygons 95
Calculations on Areas: Multiple Polygons 98
Point in Polygon: Simple Algorithm 101
and Back to Topology for a Better Algorithm 105
Further Reading 108
6.The Efficiency of Algorithms 109
How Is Algorithm Efficiency Measured? 109
Efficiency of the Line Intersection Algorithm 112
More on Algorithm Efficiency 114
Further Reading 116
7.Raster Data Structures 119
Raster Data in Databases 120
Raster Data Structures: The Array 123
Saving Space: Run Length Encoding and Quadtrees 127
Data Structures for Images 132
Further Reading 139
8.Raster Algorithms 141
Raster Algorithms: Attribute Query for RunLength Encoded Data 141
Raster Algorithms: Attribute Query for Quadtrees 144
Raster Algorithms: Area Calculation 153
Further Reading 159
9.Data Structures for Surfaces 161
Data Models for Surfaces 162
Algorithms for Creating Grid Surface Models 166
Algorithms for Creating a Triangulated Irregular Network 174
Grid Creation Revisited 180
Further Reading 183
10.Algorithms for Surfaces 185
Elevation, Slope and Aspect 185
Hydrological Analysis Using a TIN 192
Determining Flow Direction Using a Gridded DEM 195
Using the Flow Directions for Hydrological Analysis 199
Further Reading 205
11.Data Structures and Algorithms for Networks 207
Networks in Vector and Raster 207
Shortest Path Algorithm 209
Data Structures for Network Data 216
Faster Algorithms for Finding the Shortest Route 225
Further Reading ,234
12.Strategies for Efficient Data Access 235
Tree Data Structures 238
Indexing and Storing 2D Data Using Both Coordinates 244
Space-Filling Curves for Spatial Data 250
Spatial Filling Curves and Data Clustering 252
Space-Filling Curves for Indexing Spatial Data 255
Caching 265
Further Reading 269
13.Heuristics for Spatial Data 271
Travelling Salesman Problem 272
Location Allocation 277
Metaheuristics 283
Computability and Decidability 288
Further Reading 293
Conclusion 295
Glossary 297
References 305
Index 313