Skip to content

Chapter 7: Spatial Mathematics and Computational Geometry

Spatial mathematics and computational geometry

Spatial mathematics turns geometry into dependable computation. It explains why spatial predicates can be tricky, why floating-point tolerances matter, and why a seemingly simple operation like buffering or intersecting polygons can fail in surprising ways.

Companion visual reference: Spatial Data Structure Visual Atlas

Learning Goals

  • Understand vectors, matrices, topology, predicates, and graph concepts.
  • Explain common geometry algorithms such as point-in-polygon and line intersection.
  • Recognize numerical robustness issues in spatial software.
  • Use libraries instead of hand-rolling fragile geometry code.

Theory

Computational geometry represents shapes and relationships algorithmically. Spatial software relies on predicates such as intersects, contains, within, touches, overlaps, and crosses. These predicates must behave consistently even with complex polygons, holes, multipart features, and nearly coincident coordinates.

Topology describes relationships that do not depend on exact measurement. Geometry describes coordinates and shape. Robust software needs both.

Math

Core math includes vector operations, dot products, cross products, matrix transformations, orientation tests, polygon area formulas, convex hulls, Voronoi diagrams, triangulation, graph traversal, interpolation, and spatial statistics.

Floating-point arithmetic is central. Exact equality is often unsafe because coordinates may be transformed, rounded, simplified, or digitized.

Key computation patterns:

dot product:
dot(a, b) = sum(i=1..d) a_i * b_i

2D orientation test:
orient(a, b, c) = sign((b_x - a_x) * (c_y - a_y)
                      - (b_y - a_y) * (c_x - a_x))

polygon area:
area = 0.5 * abs(sum(i=1..n) (x_i * y_(i+1) - x_(i+1) * y_i))

point-in-polygon ray crossing:
inside = (number_of_ray_crossings % 2) == 1

buffer definition:
buffer(G, r) = { p | distance(p, G) <= r }

These equations are deceptively simple. Production geometry code must handle invalid rings, holes, multipart geometries, boundary cases, numeric precision, CRS choice, and tolerance. Use proven geometry libraries, then write known-answer tests around them.

See also: Math and Algorithms Reference

Tools of the Trade

  • GEOS, JTS, Shapely, PostGIS.
  • CGAL for computational geometry.
  • NetworkX and pgRouting for graphs.
  • SciPy, NumPy, scikit-learn for numerical and spatial analysis.
  • QGIS geometry checker.

Examples of Real-World Solutions

  • A zoning app uses polygon intersection to identify applicable regulations.
  • A service area tool buffers road networks by travel time.
  • A hydrology model uses flow direction and connected raster cells.
  • A telecom app uses Voronoi-like service regions as a first approximation.

Working Practice Examples

  1. Implement point-in-polygon using a library, then test boundary cases.
  2. Create an invalid self-intersecting polygon and repair it.
  3. Compare buffer results at different CRS choices.
  4. Build a small road graph and calculate shortest paths.

Common Failure Modes

  • Hand-written geometry algorithms used in production.
  • Assuming polygon boundaries are unambiguous.
  • Forgetting holes and multipart geometries.
  • Buffering in degrees.
  • Treating topology errors as rare instead of routine.

Works Cited

de Berg, Mark, et al. Computational Geometry: Algorithms and Applications. 3rd ed., Springer, 2008.

Preparata, Franco P., and Michael Ian Shamos. Computational Geometry: An Introduction. Springer, 1985.

"The Shapely User Manual." Shapely, https://shapely.readthedocs.io/. Accessed 9 May 2026.

"GEOS." GEOS Contributors, https://libgeos.org/. Accessed 9 May 2026.

GeoInformatica Consulting logo