Table of Contents
Preface
Acknowledgements
Introduction
Chapter 1 Preliminaries
1.1 How to live with coordinates
1.1.1 Vectors, geometry
1.1.2 Simple vector algebra
1.1.3 CCW predicates (2D)
1.1.4 Sidedness, barycentric coordinates
1.1.5 Area, volume, intersection calculations
1.1.6 3D sidedness and intersection
1.1.7 Computer graphics
1.2 Graphs
1.2.1 Graphs, overview: Planar graphs, duality
1.2.2 Graph traversal
1.3 Dominance
1.3.1 Dominance, Voronoi, circle tests, parabolic uplifting
1.3.2 Incremental algorithm
1.3.3 The VD/DT on the sphere
Chapter 2 Models of space
2.1 Models of space: Introduction
2.2 The cosmic spatial model
2.3 Back to earth
2.3.1 First there were fields
2.3.2 Then there were things
2.3.3 Then there were connected things
2.3.4 Then there were continuous things
2.3.5 Then there were sidedness and direction
2.3.6 Boundaries: Two-sidedness and Voronoi cells
2.3.7 Duality
2.3.8 Coordinates
2.3.9 The observer
2.3.10 The computer
2.4 Spatial data structures
2.5 PAN graphs and quad-edges
2.6 Introduction to geographic boundaries
Chapter 3 Points
3.1 Single-cell analysis: Labelled and unlabelled
3.1.1 Context
3.1.2 Nearest-point interpolation
3.1.3 Labelled skeletons
3.2 Triangulation – TIN modelling
3.3 Passive interpolation: The problem
3.4 The dynamic algorithm: Point deletion
3.5 Invasive methods: Sibson interpolation
3.6 Postscript: Accuracy – The Kriging approach
3.7 Moving points: The kinetic algorithm
3.7.1 Free-Lagrange flow modelling
3.7.2 Kinetic GIS – The marine GIS
Chapter 4 Boundaries
4.1 Class I: Lines of points
4.1.1 Crust and skeleton test
4.1.2 Polygon ‘shapes’
4.1.3 Contours – skeleton enrichment
4.1.4 Contours – skeleton point elevation
4.1.5 Watersheds
4.1.6 Interpolating from contours: Sibson interpolation
4.1.7 Slopes: The forgotten need
4.1.8 Runoff modelling
4.2 Class II: Cluster boundaries, or ‘fat’ void boundaries
4.2.1 Clusters
4.3 Class III: Double-point boundaries
4.3.1 Labelled skeleton – map digitizing
4.3.2 Scanned map processing
4.3.3 Hierarchical VD – Spatial indexing
4.4 Class IV: Solid line segments – half-line pairs
4.4.1 Complex objects
4.4.2 The constrained DT and the line segment VD
4.4.3 Basic queries with the line segment VD
4.4.4 Dynamic map partitioning
4.4.5 The kinetic line segment model and map updating
Chapter 5 2D GIS
5.1 Spatial decision support systems
5.2 The unified spatial model
5.2.1 Discrete objects: points
5.2.2 Impermeable linear features
5.2.3 Skeleton: grouped contexts
5.2.4 Buffer: clipped contexts
5.2.5 Overlays
5.2.6 Networks
5.2.7 Combining them all
5.2.8 Mobile points
5.3 Other Voronoi techniques
Chapter 6 3D GIS
6.1 3D boundary faces
6.1.1 Embedded Spaces
6.1.2 CAD and Quad-Edges
6.1.3 TIN models and building extrusion
6.1.4 Bridges and tunnels
6.1.5 The Extended TIN
6.1.6 LiDAR building models: the walls
6.1.7 LiDAR building models: simple roof modelling
6.1.8 LiDAR building models: compound roofs
6.2 Solid 3D: Real volumes
6.2.1 3D VD/DT
6.2.2 The augmented quad-edge and the dual half-edge
Chapter 7 Conclusions
7.1 What have we learned?
Index
