Delaunay Triangulation: Auditable Mosaics

Delaunay triangulation turns a point field into a crisp generative mosaic, but a beautiful mesh is not evidence that its geometry is valid. This tutorial uses seeded integer points, bounded exact predicates, cavity inspection, and exportable topology receipts so every edition can be reproduced and challenged.

Delaunay triangulation needs an audit trail

A triangular mosaic can look convincing while containing flipped faces, duplicate edges, gaps, or points inside a triangle’s circumcircle. Delaunay triangulation gives the composition a geometric rule: for points in general position, each output triangle has an empty open circumcircle. The rule is only useful when the implementation can expose how it reached the mesh.

This tutorial uses Bowyer-Watson insertion. Begin with a supertriangle around every site. For each new point, find triangles whose circumcircles contain it, remove that cavity, count its boundary edges, and connect the new point to each boundary edge. Finally discard faces that touch the supertriangle.

Watson’s n-dimensional Delaunay tessellation paper is the algorithmic source for the incremental construction. Our artifact is a bounded two-dimensional teaching implementation, not a replacement for a mature geometry library.

The creative constraint is equally explicit: geometry is fixed before color. A seeded point field produces one mesh hash; palette, stroke, and texture can create editions without changing topology. Delaunay triangulation becomes both a compositional engine and a verifiable edition contract.

1. Mark strict-positive incircle faces as the cavity.
2. Count undirected cavity edges.
3. Keep edges seen exactly once.
4. Require one closed boundary loop.
5. Connect the new site and orient each replacement face CCW.

Reading rule: labels, values, patterns, and structure carry the conclusion; color is supplementary.

Generate seeded integer points first

Use a named 32-bit pseudo-random generator and map its output into integer coordinates inside a declared rectangle. Reject duplicate coordinate pairs and cap attempts, point count, and absolute coordinate magnitude. Stable insertion order is part of the work; sorting points later changes cavities and can change the selected diagonal in cocircular cases.

Integers let the lab evaluate orientation and incircle determinants with BigInt under a bounded contract. They also make a receipt readable: every site is an exact pair rather than a decimal emitted by platform math. The visual can still place those sites at subpixel screen positions through the SVG viewBox.

The earlier Delaunay low-poly portrait tutorial samples an image to preserve subject edges. Here the intent is different: author a generative mosaic from an abstract site field and preserve the mesh’s provenance. Both need robust predicates, but their sampling decisions answer different visual questions.

Include the seed, generator name, bounds, duplicate policy, and ordered point list in the export. Hash the canonical JSON, not a screenshot. A viewer can then reconstruct the exact field, while an artist can publish several surface treatments without implying that each is a separate random discovery.

Use orientation before every incircle test

The signed orientation determinant tells whether points a, b, c turn counterclockwise, clockwise, or are collinear. Normalize every stored triangle to counterclockwise order. The sign of the incircle determinant depends on that orientation; testing a clockwise face without correction reverses the meaning of inside and outside.

Geometric predicates are decisions, not decoration. A tiny rounding difference can change a cavity boundary, which changes later faces and eventually the entire mosaic. Shewchuk’s paper on robust geometric predicates explains why naive floating-point determinant evaluation can return the wrong sign near degeneracy and presents adaptive methods.

Our bounded integer lab takes a narrower route: every input coordinate and supertriangle vertex remains within declared limits, and determinant products use arbitrary-precision BigInt. That makes signs exact for this contract. Rendering converts coordinates only after topology is complete.

Collinear triples are rejected as faces. A zero incircle determinant means cocircularity; the lab uses a documented strict-inside rule and stable insertion order instead of pretending the Delaunay triangulation is unique. Export tie counts. Numeric honesty includes saying when the geometry admits more than one valid diagonal.

Inspect each Bowyer-Watson cavity

For the current point, evaluate the exact incircle sign against every live counterclockwise face. Mark strict positive results as bad triangles. Their union forms the cavity. Count each undirected edge from those faces; edges seen once form the boundary, while edges seen twice are internal and disappear.

Sort boundary edges by their canonical endpoint key before retriangulation. Deterministic order does not change valid topology, but it keeps face arrays and hashes stable. Connect each boundary edge to the inserted point, orient the new face counterclockwise, and reject zero-area faces.

Figure one freezes one insertion: removed faces use a hatch, the once-counted polygon is drawn heavily, and replacement triangles radiate from the new site. Its visible table repeats the same edge counts so meaning does not depend on color.

A malformed cavity should stop the build. Require at least one removed face, one closed boundary loop, and exactly two incident boundary edges per boundary vertex. The Bowyer-Watson algorithm is simple enough to animate, which makes it tempting to trust the animation. Delaunay triangulation deserves structural checks at the moment an error is still local and explainable.

Audit topology and empty circumcircles

After removing supertriangle faces, audit the finite mesh independently from its constructor. Every triangle must contain three distinct in-range site indices and have positive orientation. Every undirected edge must have one incident face on the convex hull or two in the interior; an edge with three faces is non-manifold.

Check that triangle interiors do not overlap except at shared boundaries. Then run the Delaunay condition: for every face, every non-vertex site must be outside or, under the declared tie policy, on its circumcircle. Use the same exact sign convention but a separately written loop so the audit cannot simply echo a cached constructor decision.

Euler’s relation supplies another checksum for a connected planar triangulation. With V sites, E unique edges, F finite triangular faces, and H hull vertices, expect E = 3V−3−H and F = 2V−2−H when assumptions hold. Report the values instead of only a green badge.

Figure two is an audit matrix: CCW faces, edge incidence, hull relation, empty circumcircle, unique points, and stable hash. A generative mosaic should fail closed if any row fails. Art direction begins after geometry approval, not as a way to hide a broken seam.

Turn one mesh into accountable editions

Assign triangle color from deterministic features: centroid position, area rank, distance to one or more focal sites, or a hash of sorted vertex IDs. Avoid consuming the point generator again during styling; one accidental random call would make geometry and palette order-dependent. Give the palette its own seed or use a pure mapping.

The median-cut vs k-means palette guide helps when colors are derived from a reference image. This article uses authored palettes, so its receipt names the exact swatches and mapping rule. The distinction matters: a palette can be reproducible without claiming perceptual optimality.

Figure three keeps one mesh hash while showing mineral, nocturne, and paper editions. Vertex dots and edge emphasis change alongside fill, but triangle identity remains visible. The semantic equivalent lists each palette and states that topology is invariant.

Treat generated background art as atmosphere, not evidence. The article’s raster artwork is text-free and supports the editorial mood; the inline SVG figures and lab receipts carry the technical claim. This separation lets an expressive surface coexist with exact Delaunay triangulation without asking an AI-generated image to prove geometry.

Export accessible SVG and provenance

Export triangles as SVG paths or polygons in canonical face order with a stable viewBox. Round display coordinates only when serializing the already verified integer topology. Give the root SVG a title and description, connect the visible caption, and provide a non-color-only table of mesh counts and audit outcomes.

The W3C SVG accessibility mapping specification defines how SVG elements and attributes participate in accessibility APIs. Implementation and assistive-technology support still require browser testing. A title and description are a starting contract, not proof that a dense mosaic is understandable without an accompanying explanation.

The SVG vs Canvas generative-art comparison can guide the rendering choice. SVG suits this bounded edition because faces remain inspectable and downloadable. For tens of thousands of animated triangles, Canvas or WebGPU may render faster, but the same topology receipt should remain available as structured data.

Bundle seed, ordered points, bounds, tie rule, triangles, hull, audit results, palette, generator version, and named FNV-1a 32-bit mesh and edition hashes in JSON. The local lab also exports the SVG. Delaunay triangulation becomes reproducible when the picture and the construction record travel together.

Publish the mosaic with its receipt

The standalone lab creates 8 to 80 unique integer sites, runs bounded BigInt orientation and incircle predicates, records every insertion cavity, and presents the final mesh under three palettes. Its negative fixtures include duplicate points, collinear faces, a flipped orientation, a non-manifold edge, and a point intentionally placed inside a reported circumcircle.

Controls never load a file or request the network. Changing a seed recomputes the complete receipt locally. JSON includes all geometry and gates; SVG includes the title, description, visible legend, mesh hash, and edition identifiers. Exports are deterministic for the same declared settings.

The Voronoi stippling study offers a useful next experiment because Voronoi and Delaunay structures are dual under appropriate conditions. Do not merge the intents: stippling optimizes sample density against tone, while this generative mosaic audits an incremental triangle mesh.

For publication, retain the source receipt, exported asset, and chosen palette beside the social crop. Re-run the negative corpus after predicate, generator, or serialization changes. Revisit when coordinate bounds or SVG accessibility behavior changes. The result is not merely a pleasing tessellation; it is a Delaunay triangulation edition whose seed, topology, failure policy, and surface choices can all be inspected.

Runnable local artifact — The lab proves its own bounded integer-point construction and declared tie policy; it is not a general computational-geometry library, a proof for unbounded coordinates, or a fabrication specification.

Generate unique bounded integer points, insert them through a supertriangle, orient every triangle CCW, validate closed degree-two cavities, remove supertriangle faces, audit topology and overlap, then export explicit FNV-1a 32-bit geometry and edition hashes.