← Harrison Wolf

Geometry engine

Cutting complicated shapes into triangles, and turning scattered points into the meshes and regions games and mapping software rely on.

Language
C++, std library only
Original foundation
about one month
Tests
1,027 assertions · 13 suites (at the pictured commit)
Speed
1,500 sites / 0.055 s
repo

By the last checkpoint before agent-authored C++ entered the tree, I had independently built a working standard-library C++ geometry library from a bare Bash terminal using Vim and Make: 2,383 tracked C++ lines across 33 source and header files, covering points, lines, triangles, polygons, collision and containment, an original ear-clipping triangulator, random polygon generation, CLI drivers, and early visualization support. I later directed and reviewed coding-agent work that substantially revised the ear clipper and implemented the current Bowyer–Watson Delaunay and Voronoi layers, the custom TDD harness and much of its suite coverage, browser viewers, benchmarks, and terrain applications.

01Triangulation

The nominal algorithms are straightforward; the boundary cases are not. The predicate implementations explicitly handle collinear inputs, duplicate points, and orientation with scale-aware epsilon checks. In the tested near-degenerate cases, a near-touch resolves without a crossing or degenerate mesh.

A single non-convex 15-vertex polygon from the engine's random generator, filled gray The same 15-vertex polygon cut into 13 colored triangles by the ear-clipping algorithm
One 15-vertex polygon from the engine's random generator (left), and the same polygon cut into 13 triangles by the ear-clipper (right) — n−2, as a simple polygon must give. The red boxes below mark the near-touch.
Close-up of the near-touch on the raw polygon: two edges within about 0.06 units without crossing The same near-touch on the triangulated polygon: no gap or overlap
The near-touch magnified: raw polygon (left) and its triangulation (right). The two edges pass about 0.06 units apart and never cross.

The same predicates, caught deciding. With debug tracing on, every verdict prints its evidence: the determinant, the epsilon it was weighed against (size-scaled for the in-circle tests), and the call.

Debug trace: three collinear-test verdicts, each printing orient2d determinant zero against a scaled epsilon, ending in the input being rejected as collinear
Collinear input, rejected with the decision logged: orient2d = 0 against the epsilon, three times, then a refusal instead of a degenerate mesh.
Debug trace of in-circle tests on near-degenerate input: each line prints circumcenter, squared radius, margin, and epsilon, with INSIDE (bad edge) and outside verdicts interleaved
Near-degenerate points, |det| = 1e-8 against eps = 1e-9: every in-circle test prints center, radius², margin, and epsilon before calling INSIDE or outside. Margins swing from millions down to ~50 — the edge cases are where the epsilon scaling earns its keep.
The end of the TDD harness run: delaunay-predicate, triangulation, voronoi, and export suites all green, ending in Ran 1027 assertions / All tests passed
The harness that pins it all down: 1,027 assertions across the 13 suites — predicates, both triangulations, the Voronoi dual, and the export path — all green.

02Delaunay & Voronoi

One run through the engine at a legible scale: 70 sites, seed 7. The raw input, its Delaunay triangulation, the Voronoi dual, and the two overlaid. Every Voronoi vertex is the circumcenter of a triangle — often outside its own triangle, since only acute triangles contain their circumcenters.

70 raw input sites The same 70 sites, Delaunay-triangulated The Voronoi diagram of the 70 sites Delaunay and its Voronoi dual overlaid
Sites → Delaunay (125 triangles, 194 edges, Euler-exact) → Voronoi dual → both overlaid.
Delaunay in faint lines overlaid with its Voronoi dual in ink, 300 sites
And at density: 300 sites, triangulated and dualized end to end. The counts check exactly against Euler's formula (581 triangles, 880 edges).

03Measured performance

The published benchmark studio keeps exact generated inputs, raw process output, per-run resource logs, manifests, checksums, and validation results. The compute metric covers triangulation, finite Voronoi construction, and topology validation; it excludes input generation, startup, and serialization.

Median triangulation, Voronoi, validation, and total compute time for 30 runs of one 1,500-site input
One fixed 1,500-site input, 30/30 successful runs: compute-only median 0.0551 s (range 0.0396–0.0771 s), identical input and topology hashes every time. Median peak RSS 4,710 KiB. Manifest and raw logs.
Compute time for uniform, clustered, jittered-grid, and near-collinear 1,024-site inputs across three seeds
Input-shape study: four deterministic families, three seeds each, five repetitions — 60/60 successful. Seed-level case medians, so timing noise isn't mistaken for input evidence. Full research bundle.
Per-phase timing for 20,000 sites: Bowyer-Watson 5.56 s, Voronoi dualization 0.49 ms, Delaunay validation 10.11 s, total 15.7 s, 39,965 triangles, validation passed
And where the time actually goes, at 20,000 sites: triangulation 5.6 s, dualization 0.5 ms, then 10.1 s re-proving every circumcircle empty — the O(N²) validation pass costs more than the construction it checks.

Full detail — build, algorithms, tests — in the README: github.com/harrisonwolf/planar-geometry-engine

← Back to the portfolio