Most map features rest on a handful of old algorithms. Is this point inside that zone? How far apart are these two cities? Can this GPS track be drawn with fewer points? Which ten places are nearest to me? Libraries answer all of these in one call, and that is the right way to do it in real work. It also means you can use them for years without knowing how they decide.
geo-algos is my learning project for looking inside. It implements classic geospatial algorithms from scratch in Rust, with no runtime dependencies. Each one is checked against a brute-force or independent reference with property tests. The README says it plainly, and so will I: for real work, use the geo and rstar crates. This one is for learning.
What it does
There are four modules:
| Module | What it does |
|---|---|
pip | Point in polygon with holes: ray casting (even-odd) and winding number (non-zero), with an explicit Boundary result |
distance | Haversine (sphere) and Vincenty inverse (WGS84 ellipsoid) with bearings and a convergence error |
simplify | Douglas-Peucker polyline simplification, iterative, with no recursion depth limit |
rtree | R-tree: Guttman insert with linear or quadratic split, STR bulk load, range query, best-first kNN |
What I built from scratch, and what it teaches
Point in polygon: two rules, and the edge cases. Ray casting counts how many edges a horizontal ray from the point crosses: odd means inside. The trap is a ray that passes exactly through a vertex. The fix is a half-open rule, so that vertex is counted once. The winding number (Sunday's version) uses only orientation tests. The two methods agree on simple rings and differ on self-intersecting ones: the centre of a pentagram is outside under even-odd and inside under non-zero, and there is a test for it. Polygon::locate checks the rings first, so a point exactly on an edge comes back as Boundary instead of an arbitrary answer.
Distances: sphere or ellipsoid. Haversine treats the Earth as a sphere of mean radius 6,371,008.8 m. It is simple, and it is off by up to about 0.5% compared with the ellipsoid. Vincenty's inverse formula works on the WGS84 ellipsoid and iterates on the longitude difference. It gives sub-millimetre accuracy and is checked against Vincenty's own Flinders Peak to Buninyong line (54,972.271 m). It has a known weakness: nearly antipodal points can fail to converge. Here that case is returned as VincentyError::NoConvergence instead of a wrong number.
Douglas-Peucker: a guarantee you can test. The algorithm keeps the endpoints, finds the point farthest from the chord between them, and recurses while that point is beyond epsilon. The textbook version is recursive; this one uses an explicit stack, so a very long line cannot overflow the call stack. The property test checks the guarantee itself: every dropped point is within epsilon of the segment that replaced it.
The R-tree: a spatial index. Nodes are stored in an arena (a Vec) and referenced by index, which avoids fighting the borrow checker over parent and child pointers. insert follows Guttman's paper: ChooseLeaf by least enlargement, then a split on overflow (quadratic PickSeeds/PickNext, or linear seeds), then adjusting bounding boxes up to the root. bulk_load is Sort-Tile-Recursive (STR), which packs nodes full when you have all the data up front. nearest is a best-first search with a min-heap keyed by MINDIST, so entries come out in exact distance order. And validate() checks the invariants: equal leaf depth, fan-out bounds and tight bounding boxes.
How to use it
Add it to a Rust project from GitHub:
cargo add --git https://github.com/AbdeldjalilChougui/geo-algos Or clone the repository and run what is there:
cargo test # unit tests + proptest checks cargo run --example demo # small tour of every module cargo bench # criterion benchmarks A short example from the README shows three of the modules:
use geo_algos::{haversine, LonLat, Point, Polygon, RTree, Entry, Rect}; let d = haversine(LonLat::new(3.0588, 36.7538), LonLat::new(-0.6417, 35.6971)); // ~352 km let sq = |a: f64, b: f64| vec![Point::new(a, a), Point::new(b, a), Point::new(b, b), Point::new(a, b)]; let donut = Polygon::new(sq(0.0, 10.0), vec![sq(4.0, 6.0)]); assert!(donut.contains(Point::new(1.0, 1.0))); assert!(!donut.contains(Point::new(5.0, 5.0))); // in the hole let tree = RTree::bulk_load(vec![Entry::point(Point::new(1.0, 2.0), "a")], 16); let near = tree.nearest(Point::new(0.0, 0.0), 1); The first line measures a distance between two longitude and latitude pairs, about 352 km. The polygon is a square with a square hole, so a point in the hole is not contained. The last two lines build an R-tree with a node capacity of 16 and ask for the nearest entry to the origin.
How it is tested
The tests are where the "checked against a reference" promise is kept. There are 39 unit tests next to the code: edge cases, boundaries, holes, a pentagram, degenerate inputs and known distances.
Then there are 8 proptest properties in tests/properties.rs. Property tests generate random inputs and check that a rule always holds:
- point in polygon against an analytic star-polygon reference, plus ray casting against winding number;
- holes against a closed-form predicate;
- the metric axioms for Haversine;
- Vincenty within 0.6% of Haversine;
- the Douglas-Peucker tolerance guarantee;
- R-tree range and kNN results against brute force, for insert-built trees (both splits) and STR trees.
The last one is the pattern I like most. A linear scan over all the points is slow and obviously correct, so it is the perfect judge for an index that is fast and easy to get subtly wrong.
The README also has a benchmark table, with an honest warning: it was measured with cargo bench -- --quick on a laptop that was busy with other builds, so the numbers are orders of magnitude only. With that warning: Haversine is around 0.23 µs and Vincenty around 2 µs per call, an STR bulk load of 50k points takes about 52 ms, and inserting the same 50k points one by one takes about 0.3 to 0.5 s.
Things to know
The README lists the limits, and they matter if you are tempted to use this beyond learning:
- This is a learning project. For real work use the
geoandrstarcrates. - Everything is plain
f64with no robust predicates. Boundary detection is exact only when the arithmetic is: vertices and axis-aligned edges work, but a point interpolated along a slanted edge may land a hair inside or outside. - The planar algorithms treat lon/lat degrees as flat x/y. Nothing handles the antimeridian, and the Douglas-Peucker
epsilonis in input units. - The R-tree has no deletion and no R*-tree reinsertion. kNN distance is measured to each entry's bounding rectangle.
- Hole validity (holes inside the exterior, not overlapping) is assumed and not checked.
What I learned
The first lesson is that geometry code is mostly about the cases a drawing does not show: the ray through a vertex, the point on an edge, the two points on opposite sides of the planet. The main idea of each algorithm fits in a paragraph. The rest of the code is there for those cases.
The second is that a slow reference is a great tool. Almost every module here is tested by comparing it with something simpler: brute force for the R-tree, a closed-form predicate for holes, Haversine as a sanity bound for Vincenty. When the two disagree on a random input, proptest shrinks it to a small example, and the bug is usually visible at once.
The third is specific to Rust. A tree with parent and child links is awkward with references and comfortable in an arena with indices.
And returning Boundary or NoConvergence as explicit results taught me something general: when an algorithm has an input it cannot answer well, say so in the type instead of returning a guess.
Get the code
The source, the demo example, the tests and the benchmarks are on GitHub: https://github.com/AbdeldjalilChougui/geo-algos. It is MIT licensed, and no external data is used.
Originally published at abdeldjalilchougui.biz.