Spatial Context: An Introduction to Fundamental Computer Algorithms for Spatial Analysis

ISBN-13: 9781138029637 / Angielski / Twarda / 2016 / 218 str.

Christopher Gold;¬Abar;¬Abar

Opis

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.

The book starts with some of the basics of manipulating coordinate representations so that the resulting object descriptions may be usefully combined and queried. The first chapter should be of value to research students in fields with limited prerequisites in mathematics and computing.

The book then considers the concepts necessary to express the spatial relationships between both 2D and 3D entities, whether points, lines, polygons or polyhedra, so that they may be queried, grouped or combined. A unifying theme is a discussion of the various types of boundaries between regions of space, based on the Voronoi diagram and its dual, the Delaunay triangulation, and various available static, dynamic and kinetic algorithms. Applications, including surface interpolation, crusts and skeletons, contour and watershed handling, scanned map processing and solid line-work for urban mapping, are then described: this leads to the Unified Spatial Model for 2D mapping and GIS.

The last section examines 3D space both simple shell models for building exteriors as well as true 3D, where volumetric elements may be defined, such as rooms and corridors. Shell models require some introduction to basic CAD structures, and solid 3D requires advanced edge-based data structures. Both of these application areas lead to straightforward modelling techniques and emphasize the moral of this book: the spatial dual is the context. Example application areas described include geology, geography, forestry, surveying, cosmology, CAD and many others."

Spis treści

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 

O autorze

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.