GIS

GIS#

Reference of geospatial algorithms and open-source tooling for geospatial analysis. The discipline runs from cartography and basic spatial joins through routing, geostatistics, terrain analysis, remote sensing, and large-scale spatial ML.

For data sources (basemaps, imagery, geocoders), see Map Sources. For positioning and tracking math, see Triangulation. For the operator’s GEOINT discipline, see 0X47 - Spatial.

Algorithms#

Geometry primitives#

Algorithm

Use

Point-in-polygon

Ray-casting / winding-number; boost.geometry, GEOS, Shapely.

Polygon clipping

Sutherland-Hodgman, Vatti, Greiner-Hormann; intersection / union / difference / symmetric difference.

Polygon offsetting

Buffer / inflate; Minkowski-sum.

Convex hull

Graham scan, QuickHull, Chan’s algorithm; n log n.

Concave hull

Alpha-shapes, knn-based, ChiShapes.

Triangulation

Delaunay, constrained Delaunay, ear-clipping.

Voronoi diagrams

Fortune’s sweep; dual of Delaunay.

Bounding shapes

AABB / OBB / minimum-area-rectangle / smallest-enclosing-circle.

Line simplification

Douglas-Peucker, Visvalingam-Whyatt.

Curve fitting

Bezier, B-spline; rdp + smoothing for GPS tracks.

Geometry validity

GEOS makeValid; OGR Force-RHR.

Spatial indexing#

Index

Use

R-tree

Bulk-load (STR) for static data; PostGIS GIST default.

Quadtree

Recursive partition; image / raster.

Geohash

Z-order encoding to a string; cheap range queries.

H3 (Uber)

Hexagonal hierarchical grid.

S2 (Google)

Quad sphere grid; 64-bit cell IDs; well-suited for global indexing.

KD-tree

k-NN in low-D point sets.

Ball-tree

k-NN with arbitrary metrics.

Hilbert curves

Space-filling curve for clustering nearby items.

Spatial joins / overlay#

Operation

Notes

Spatial join

Intersect / contains / within / touches / crosses / overlaps; dimensionally extended 9-intersection (DE-9IM).

Overlay

Union, difference, symmetric difference between two layers.

Dissolve

Merge contiguous polygons sharing an attribute value.

Aggregation

Sum / mean of a value across a partitioning polygon set.

Map algebra

Arithmetic on raster cells (Tomlin’s framework).

Distances / proximity#

Algorithm

Notes

Euclidean

Planar; for projected coordinate systems.

Haversine

Great-circle on a sphere; ~0.5% error vs. ellipsoid.

Vincenty

Iterative ellipsoidal great-circle; standard before 2010s.

Karney’s algorithm

Vincenty’s modern replacement; no convergence issues.

Geodesic

Following the earth’s surface curvature.

Manhattan / taxicab

On a grid.

Chebyshev

Max of dx / dy; chess-king distance.

Travel-time / -dist

Routing-engine output (OSRM / Valhalla / GraphHopper).

Cost-distance

Raster-based; cheapest path through varied resistance.

Routing / shortest-path#

Algorithm

Notes

Dijkstra

Single-source shortest path on non-negative-weight graphs.

A*

Heuristic-guided Dijkstra; great with admissible heuristic (Haversine).

Bidirectional

Search from both ends; halves expansion.

Contraction Hier.

CH; pre-process the graph for fast queries; OSRM default.

ALT (A*+landmarks)

ALT heuristics for road graphs.

Hub Labels

Pre-computed labels; fastest static-graph queries.

Time-dependent

Routing with time-of-day-varying edge weights (traffic).

Multi-modal

Combine driving, transit, walking, cycling.

TSP / VRP

NP-hard; Concorde, OR-Tools, LKH.

Terrain and DEM#

Algorithm

Notes

Slope / aspect

First-derivative of elevation; gdaldem.

Hillshade

Cast simulated sunlight; great visualization.

Curvature

Second-derivative; profile / planar.

Watershed

Hydrological basin delineation; pour-points + flow-dir.

Stream extraction

Strahler order; Horton-Strahler ranking.

Viewshed

Line-of-sight from observer point.

Terrain ruggedness

TRI, VRM, roughness.

Visibility graph

For pathfinding around obstacles.

TIN

Triangulated irregular network from point clouds.

LiDAR processing

PDAL; ground-vs-vegetation classification (CSF, PMF, SMRF).

Geostatistics#

Algorithm

Notes

IDW

Inverse-distance weighting interpolation.

Kriging

BLUP from a fitted variogram; ordinary, universal, indicator variants.

Co-kriging

Multi-variate kriging.

Gaussian Processes

ML kriging cousin; modern Bayesian framing.

Spline

Thin-plate / regularised spline interpolation.

Trend surface

Polynomial regression on (x,y).

Moran’s I

Spatial autocorrelation; global + local (LISA).

Geary’s C

Alternative spatial autocorrelation.

G / G* statistic

Local hot-spot detection.

SAR / GWR

Spatial / geographically-weighted regression.

Clustering / spatial ML#

Algorithm

Notes

DBSCAN / HDBSCAN

Density-based; finds arbitrarily-shaped clusters.

OPTICS

Ordering-based density variant.

ST-DBSCAN

Spatio-temporal extension.

k-means

Fast partitioning; bad on geographic shapes alone.

Hot-spot analysis

Getis-Ord G* on aggregated counts.

Spatial regression

Geographically-weighted, MGWR; PySAL.

PySAL

Python spatial analysis library.

H3 / S2 binning

Aggregate point data into hex cells before classification.

Remote sensing#

Algorithm

Notes

NDVI / NDWI

Vegetation / water indices; per-band arithmetic.

Pan-sharpening

Brovey / Gram-Schmidt / IHS; fuse high-res pan + low-res multispec.

Atmospheric corr.

Sen2Cor (Sentinel-2), LaSRC (Landsat); convert reflectance.

Cloud masking

Fmask, s2cloudless.

Change detection

Image differencing, post-classification, CCDC, BFAST.

Classification

Random forest, SVM, U-Net / DeepLabv3+ / SegFormer for semantic segmentation.

Object detection

YOLO / DETR adapted to overhead imagery (tiled inference).

Spectral unmixing

LSU, NMF; per-pixel material composition.

SAR processing

SNAP toolbox; speckle filtering, ortho-correction, coherence, interferometry (InSAR).

Time-series

Landsat archive analysis (Google Earth Engine, openEO).

Open-source tools#

Desktop / GUI#

Tool Notes#

QGIS The flagship; full GIS; Python plugin ecosystem. GRASS GIS Older; strong raster + LiDAR. SAGA GIS Long-running; geomorphometry strong. gvSIG Java desktop GIS. uDig Eclipse-based; legacy. ===================================================================

Libraries#

Library

Notes

GDAL / OGR

Format conversion; CLI + bindings.

GEOS

Computational geometry; powers PostGIS.

PROJ

Coordinate-system transforms.

Shapely

Python geometry on top of GEOS.

Fiona

Python vector I/O on top of OGR.

Rasterio

Python raster I/O on top of GDAL.

GeoPandas

Pandas-shaped vector dataframes.

xarray + rioxarray

N-D arrays for raster / image cubes.

PyProj

Python PROJ wrapper.

PyGEOS / GeoArrow

Vectorised geometry ops.

Mercantile

Tile arithmetic.

Folium

Leaflet wrapper; Jupyter maps.

PyDeck

deck.gl wrapper; WebGL.

GeoStack

Apache; cloud-native.

EarthPy

Tutorial-friendly raster + vector.

WhiteboxTools

C / Rust; geomorphometry.

PyVista

3-D vector / mesh visualization.

Server / API#

Tool

Notes

PostGIS

Spatial extension to PostgreSQL.

SpatiaLite

Spatial extension to SQLite.

DuckDB Spatial

Spatial extension to DuckDB; columnar analytics.

GeoServer

OGC services (WMS / WFS / WMTS / WCS / WPS).

MapServer

Older OGC server; lightweight.

GeoNetwork

Metadata catalog (CSW).

pygeoapi

OGC API features / coverages / records server.

TileServer GL

Vector tiles via MapLibre styles.

Tegola, Tippecanoe, planetiler

Vector-tile generators.

Martin

Postgres -> vector tiles.

TerracottaTiles

COG -> raster tile server.

Cloud / scale-out#

Tool

Notes

Google Earth Engine

Petabyte-scale planetary archive + analysis (free for research / non-commercial).

openEO

Standardized cloud EO API; multiple backends (CDSE, EODC, Sentinel Hub).

Microsoft Planetary Computer

Azure-hosted EO data + STAC; Hub UI.

AWS Open Data

Hosted Sentinel, Landsat, NAIP, MODIS as COG.

Sentinel Hub

Commercial EO API; processing graphs.

Up42, Skywatch

EO marketplaces.

Apache Sedona

Spatial extensions to Spark.

GeoMesa

Spatial Hadoop / Accumulo / HBase.

Apache Baremaps

OSM tile pipeline.

Web clients#

Library

Notes

MapLibre GL JS

Vector-tile client; the open continuation of Mapbox GL JS.

Mapbox GL JS

Commercial vector-tile client.

Leaflet

Lightweight raster / vector map.

OpenLayers

Full-featured OGC-compatible.

Cesium

3-D globe.

deck.gl

WebGL data visualization.

kepler.gl

Uber visualization on deck.gl.

QGIS Web Client / Q

WC2 publish QGIS projects to the web.

Specialty#

Tool

Notes

PDAL

LiDAR / point cloud processing.

SAGA

GRASS-adjacent; geomorphometry.

ESA SNAP

Sentinel toolbox; SAR + optical.

Orfeo Toolbox (OTB)

Remote sensing.

QGIS LASTools

LiDAR plugins.

GMT

Generic Mapping Tools (cartography / publication).

PROJ pipelines

Custom coordinate transforms.

Open Drone Map

Photogrammetry from drone imagery.

WebODM

ODM web frontend.

Operator notes#

  • Coordinate systems matter. Always check the CRS before spatial joins; mismatch produces silent garbage.

  • Projected vs. geographic, distance and area in geographic CRS (EPSG:4326) is degrees, not meters. Reproject before measurement.

  • PostGIS first, Postgres + PostGIS handles 90% of small- to-medium analytics without leaving SQL.

  • Cloud-Optimized GeoTIFF + STAC, the modern pattern for petabyte raster archives; rio-cogeo to convert, stac-fastapi to serve.

  • Vector tiles + MapLibre, the open client default in 2026.

  • Earth Engine, still the easiest route to multi-decade Landsat / Sentinel analysis without owning compute.

References#

Contents