You are previewing GIS Fundamentals, Second Edition, 2nd Edition.
O'Reilly logo
GIS Fundamentals, Second Edition, 2nd Edition

Book Description

With GIS technology increasingly available to a wider audience on devices from apps on smartphones to satnavs in cars, many people routinely use spatial data in a way which used to be the preserve of GIS specialists. However spatial data is stored and analyzed on a computer still tends to be described in academic texts and articles which require specialist knowledge or some training in computer science. Developed to introduce computer science literature to geography students, GIS Fundamentals, Second Edition provides an accessible examination of the underlying principles for anyone with no formal training in computer science.

See What’s New in the Second Edition:

  • Coverage of the use of spatial data on the Internet
  • Chapters on databases and on searching large databases for spatial queries
  • Improved coverage on route-finding
  • Improved coverage of heuristic approaches to solving real-world spatial problems
  • International standards for spatial data

The book begins with a brief but detailed introduction to how computers work and how they are programmed, giving anyone with no previous computer science background a foundation to understand the remainder of the book. As with all parts of the book there are also suggestions for further sources of reading. The book then describes the ways in which vector and raster data can be stored and how algorithms are designed to perform fundamental operations such as detecting where lines intersect. From these simple beginnings the book moves into the more complex structures used for handling surfaces and networks and contains a detailed account of what it takes to determine the shortest route between two places on a network. The final sections of the book review problems, such as the "Travelling Salesman" problem, which are so complex that it is not known whether an optimum solution exists.

Using clear, concise language, but without sacrificing technical rigour, the book gives readers an understanding of what it takes to produce systems which allow them to find out where to make their next purchase and how to drive to the right place to collect it.

Table of Contents

  1. Preliminaries
  2. Preface
    1. Learning Features
    2. Structure of the Book
    3. Changes from the First Edition
  3. Acknowledgements
  4. Author
  5. Chapter 1 Introduction
    1. 1.1 How Computers Solve Problems
    2. 1.2 How Computers Represent the World: Data Modelling
    3. 1.3 The Structure of a Computer
    4. 1.4 Pseudocode and Computer Programming
    5. Further Reading
      1. Figure 1.1
      2. Figure 1.2
      3. Figure 1.3
      4. Figure 1.4
      5. Figure 1.5
      6. Figure 1.6
      7. Figure 1.7
      8. Figure 1.8
      9. Figure 1.9
  6. Chapter 2 Databases
    1. 2.1 What Are Databases and Why Are They Important?
    2. 2.2 Relational Database
    3. 2.3 Storing Spatial Data in a Relational Database
    4. 2.4 Solutions to the Problems of Storing Spatial Data in RDBMS
    5. Further Reading
      1. Figure 2.1
      2. Figure 2.2
      3. Figure 2.3
      4. Figure 2.4
      5. Figure 2.5
      6. Figure 2.6
      7. Figure 2.7
      8. Figure 2.8
      9. Figure 2.9
      10. Figure 2.10
      11. Figure 2.11
      12. Figure 2.12
      13. Figure 2.13
  7. Chapter 3 Vector Data Structures
    1. 3.1 Simple Storage of Vector Data
    2. 3.2 Topological Storage of Vector Data
    3. 3.3 So What Is Topology?
    4. 3.4 And How Does It Help? The Example of DIME
    5. 3.5 More on Topological Data Structures
    6. 3.6 And a Return to Simple Data Structures
    7. Further Reading
      1. Figure 3.1
      2. Figure 3.2
      3. Figure 3.3
      4. Figure 3.4
      5. Figure 3.5
      6. Figure 3.6
      7. Figure 3.7
      8. Figure 3.8
      9. Figure 3.9
      10. Figure 3.10
      11. Figure 3.11
      12. Figure 3.12
      13. Figure 3.13
      14. Figure 3.14
      15. Figure 3.15
      16. Figure 3.16
      17. Figure 3.17
      18. Figure 3.18
      19. Figure 3.19
      20. Figure 3.20
      21. Figure 3.21
      22. Figure 3.22
      23. Figure 3.23
      24. Figure 3.24
      25. Figure 3.25
      26. Figure 3.26
      27. Figure 3.27
      28. Figure 3.28
      29. Figure 3.29
      30. Figure 3.30
      31. Figure 3.31
  8. Chapter 4 Vector Algorithms for Lines
    1. 4.1 Simple Line Intersection Algorithm
    2. 4.2 Why the Simple Line Intersection Algorithm Would Not Work: A Better Algorithm
    3. 4.3 Dealing with Wiggly Lines
    4. 4.4 Calculations on Lines: How Long Is a Piece of String?
    5. 4.5 Line Intersection: How It Is Really Done
    6. Further Reading
      1. Figure 4.1
      2. Figure 4.2
      3. Figure 4.3
      4. Figure 4.4
      5. Figure 4.5
      6. Figure 4.6
      7. Figure 4.7
      8. Figure 4.8
      9. Figure 4.9
      10. Figure 4.10
      11. Figure 4.11
      12. Figure 4.12
      13. Figure 4.13
      14. Figure 4.14
      15. Figure 4.15
      16. Figure 4.16
  9. Chapter 5 Vector Algorithms for Areas
    1. 5.1 Calculations on Areas: Single Polygons
    2. 5.2 Calculations on Areas: Multiple Polygons
    3. 5.3 Point in Polygon: Simple Algorithm
    4. 5.4 ... and Back to Topology for a Better Algorithm
    5. Further Reading
      1. Figure 5.1
      2. Figure 5.2
      3. Figure 5.3
      4. Figure 5.4
      5. Figure 5.5
      6. Figure 5.6
      7. Figure 5.7
      8. Figure 5.8
      9. Figure 5.9
      10. Figure 5.10
      11. Figure 5.11
      12. Figure 5.12
  10. Chapter 6 The Efficiency of Algorithms
    1. 6.1 How Is Algorithm Efficiency Measured?
    2. 6.2 Efficiency of the Line Intersection Algorithm
    3. 6.3 More on Algorithm Efficiency
    4. Further Reading
      1. Figure 6.1
      2. Figure 6.2
      3. Figure 6.3
      4. Figure 6.4
      5. Figure 6.5
  11. Chapter 7 Raster Data Structures
    1. 7.1 Raster Data in Databases
    2. 7.2 Raster Data Structures: The Array
    3. 7.3 Saving Space: Run Length Encoding and Quadtrees
    4. 7.4 Data Structures for Images
    5. Further Reading
      1. Figure 7.1
      2. Figure 7.2
      3. Figure 7.3
      4. Figure 7.4
      5. Figure 7.5
      6. Figure 7.6
      7. Figure 7.7
      8. Figure 7.8
      9. Figure 7.9
      10. Figure 7.10
      11. Figure 7.11
      12. Figure 7.12
      13. Figure 7.13
      14. Figure 7.14
      15. Figure 7.15
      16. Figure 7.16
      17. Figure 7.17
  12. Chapter 8 Raster Algorithms
    1. 8.1 Raster Algorithms: Attribute Query for Run Length Encoded Data
    2. 8.2 Raster Algorithms: Attribute Query for Quadtrees
    3. 8.3 Raster Algorithms: Area Calculations
    4. Further Reading
      1. Figure 8.1
      2. Figure 8.2
      3. Figure 8.3
      4. Figure 8.4
      5. Figure 8.5
      6. Figure 8.6
      7. Figure 8.7
      8. Figure 8.8
      9. Figure 8.9
      10. Figure 8.10
  13. Chapter 9 Data Structures for Surfaces
    1. 9.1 Data Models for Surfaces
    2. 9.2 Algorithms for Creating Grid Surface Models
    3. 9.3 Algorithms for Creating a Triangulated Irregular Network
    4. 9.4 Grid Creation Revisited
    5. Further Reading
      1. Figure 9.1
      2. Figure 9.2
      3. Figure 9.3
      4. Figure 9.4
      5. Figure 9.5
      6. Figure 9.6
      7. Figure 9.7
      8. Figure 9.8
      9. Figure 9.9
      10. Figure 9.10
      11. Figure 9.11
      12. Figure 9.12
      13. Figure 9.13
      14. Figure 9.14
      15. Figure 9.15
      16. Figure 9.16
      17. Figure 9.17
      18. Figure 9.18
      19. Figure 9.19
      20. Figure 9.20
  14. Chapter 10 Algorithms for Surfaces
    1. 10.1 Elevation, Slope and Aspect
    2. 10.2 Hydrological Analysis Using a TIN
    3. 10.3 Determining Flow Direction Using a Gridded DEM
    4. 10.4 Using the Flow Directions for Hydrological Analysis
    5. Further Reading
      1. Figure 10.1
      2. Figure 10.2
      3. Figure 10.3
      4. Figure 10.4
      5. Figure 10.5
      6. Figure 10.6
      7. Figure 10.7
      8. Figure 10.8
      9. Figure 10.9
      10. Figure 10.10
      11. Figure 10.11
      12. Figure 10.12
      13. Figure 10.13
      14. Figure 10.14
      15. Figure 10.15
      16. Figure 10.16
  15. Chapter 11 Data Structures and Algorithms for Networks
    1. 11.1 Networks in Vector and Raster
    2. 11.2 Shortest Path Algorithm
    3. 11.3 Data Structures for Network Data
    4. 11.4 Faster Algorithms for Finding the Shortest Route
    5. Further Reading
      1. Figure 11.1
      2. Figure 11.2
      3. Figure 11.3
      4. Figure 11.4
      5. Figure 11.5
      6. Figure 11.6
      7. Figure 11.7
      8. Figure 11.8
      9. Figure 11.9
      10. Figure 11.10
      11. Figure 11.11
      12. Figure 11.12
      13. Figure 11.13
      14. Figure 11.14
      15. Figure 11.15
      16. Figure 11.16
      17. Figure 11.17
      18. Figure 11.18
      19. Figure 11.19
      20. Figure 11.20
      21. Figure 11.21
      22. Figure 11.22
      23. Figure 11.23
      24. Figure 11.24
      25. Figure 11.25
      26. Figure 11.26
      27. Figure 11.27
  16. Chapter 12 Strategies for Efficient Data Access
    1. 12.1 Tree Data Structures
    2. 12.2 Indexing and Storing 2D Data Using Both Coordinates
    3. 12.3 Space-Filling Curves for Spatial Data
    4. 12.4 Spatial Filling Curves and Data Clustering
    5. 12.5 Space-Filling Curves for Indexing Spatial Data
    6. 12.6 Caching
    7. Further Reading
      1. Figure 12.1
      2. Figure 12.2
      3. Figure 12.3
      4. Figure 12.4
      5. Figure 12.5
      6. Figure 12.6
      7. Figure 12.7
      8. Figure 12.8
      9. Figure 12.9
      10. Figure 12.10
      11. Figure 12.11
      12. Figure 12.12
      13. Figure 12.13
      14. Figure 12.14
      15. Figure 12.15
      16. Figure 12.16
      17. Figure 12.17
      18. Figure 12.18
      19. Figure 12.19
      20. Figure 12.20
      21. Figure 12.21
      22. Figure 12.22
      23. Figure 12.23
      24. Figure 12.24
      25. Figure 12.25
      26. Figure 12.26
      27. Figure 12.27
  17. Chapter 13 Heuristics for Spatial Data
    1. 13.1 Travelling Salesman Problem
    2. 13.2 Location Allocation
    3. 13.3 Metaheuristics
    4. 13.4 Computability and Decidability
    5. Further Reading
      1. Figure 13.1
      2. Figure 13.2
      3. Figure 13.3
      4. Figure 13.4
      5. Figure 13.5
      6. Figure 13.6
      7. Figure 13.7
      8. Figure 13.8
      9. Figure 13.9
      10. Figure 13.10
      11. Figure 13.11
      12. Figure 13.12
      13. Figure 13.13
      14. Figure 13.14
      15. Figure 13.15
      16. Figure 13.16
      17. Figure 13.17
      18. Figure 13.18
  18. Conclusion
  19. Glossary
  20. References