Spatial Context: An Introduction to Fundamental Computer Algorithms for Spatial Analysis, 1st Edition (Hardback) book cover

Spatial Context

An Introduction to Fundamental Computer Algorithms for Spatial Analysis, 1st Edition

By Christopher Gold

CRC Press

218 pages

Purchasing Options:$ = USD
Hardback: 9781138029637
pub: 2016-05-31
eBook (VitalSource) : 9781315375113
pub: 2018-04-17
from $107.97

FREE Standard Shipping!


Many disciplines are concerned with manipulating geometric (or spatial) objects in the computer – such as geology, cartography, computer aided design (CAD), etc. – and each of these have developed their own data structures and techniques, often independently. Nevertheless, in many cases the object types and the spatial queries are similar, and this book attempts to find a common theme.


Chris Gold has devoted much of his research career to techniques of spatial analysis. In this new book many of his most important contributions are assembled in one place for the first time, along with related material, and covering applications that range across the environmental and social sciences. The book will be of great interest to researchers from across those disciplines, as well as to specialists in computer graphics, computational geometry, photogrammetry, cartography, and remote sensing.

Unlike many competing books, the author of this one has chosen to present algorithms descriptively, rather than in code or pseudocode. This makes the book eminently readable, but perhaps of most interest to those who are able to turn the descriptions into code, or to value them as insights into what goes on under the hood of geographic information technologies. The text is very well illustrated with black-and-white diagrams, and mathematical notation is clear and easy to follow.

Spatial context is a concept of great interest to social scientists as they try to understand how behavior is determined by an individual's surroundings. Obesity, drug use, housing segregation, and many other aspects of human behavior depend to some degree on the environment in which the individual lives, and yet much previous research has failed to find accurate ways of capturing spatial context. An individual's ZIP code, for example, is often taken as a convenient but necessarily inacccurate basis for estimating the spatial factors that influence behavior. This book will be helpful to researchers interested in finding better solutions to the problem of characterizing spatial context.

Mike Goodchild, Emeritus Professor and Research Professor of Geography at the University of California, Santa Barbara, USA.

The author of the present book is a well-known expert in this eld. His book starts with a presentation of useful geometric primitives like predicates for 3-dimensional intersection detection. The next, and central, topic are geometric structures of immense value to modeling. Most prominently feature the Voronoi diagram, the Delaunay triangulation and the medial axis (or: skeleton). They contain a lot of information about a given scene and are, therefore, widely used in computer science, GIS, mathematics, natural sciences, economics, and ecology. The author discusses surprising properties of these structures, emphasizing general concepts like duality. The third part of the book is devoted to more practically oriented methods used in 2- and 3-dimensional GIS.

In this book, the author presents a rather personal view. His selection of topics, the decision not to include complexity questions or numerical problems, and the wealth of beautiful gures make reading easy. The author's enthusiasm jumps out at his readers and keeps them motivated. This book provides, in a pleasurable way, insight into topics that are not widely known nor easily accessible. Thus, it presents a very nice introduction to spatial analysis.

Rolf Klein, Professor at the University of Bonn. In: Zentralblatt MATH 1376.68001.

Table of Contents




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?


About the Author

Professor Christopher Gold has worked on the development of GIS methods since the 1970s, and is particularly concerned about the integration of geographical analysis and algorithms, and cooperation with the Computer Science community. As well as his current emphasis on spatial data structures and algorithms, he has had extensive experience in applications such as forestry, geology, landscape modelling and marine navigation. Professor Gold has been active for over 30 years in the development of spatial data structures, spatial models of perception and adjacency, Geo-informatics applications, and algorithms.

He has approximately 200 publications and presentations in many fields – GIS (Geographic Information Science), Computer Science, Geology, Forestry and others. He is known in the Geo-informatics community for his work on spatial data structures, Voronoi diagrams, dynamic mapping and 3D modelling, and within the Computational Geometry community for his work on GIS applications. He has been active in Mathematics conferences, in Geology and Engineering workshops, and in Forestry. He has made presentations or organized workshops in Canada, USA, Europe and China. Gold has received a variety of honours from Canadian and Asian associations, and has collaborated with a wide variety of researchers in Europe, North America and Asia. He has supervised approximately 20 research students and research assistants.

About the Series

ISPRS Book Series

The International Society for Photogrammetry and Remote Sensing (ISPRS) Book Series comprises significant scientific publications in photogrammetry and remote sensing, and related disciplines. Each volume in the series is prepared independently and focuses on a topical theme. Volumes are published on an occasional basis, according to the emergence of noteworthy scientific developments. The material included within each volume is peer-reviewed rigorously, ensuring strong scientific standards.

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
MATHEMATICS / Geometry / General
TECHNOLOGY & ENGINEERING / Remote Sensing & Geographic Information Systems