Triangles for spatial data in R

Triangles are everywhere in spatial work: drawing polygons, joining up points, interpolating, terrain, and the meshes behind spatial models. This is a friendly guide to what triangulation is, which R package to reach for, and why the choice matters.

One county filled with triangles three ways: ear cutting, Delaunay of sample points, and a refined constrained mesh

One county, three kinds of triangulation. Start here to see why they differ.

Start here

What a triangulation is, the three questions most people are really asking ("fill my polygon", "connect my points", "keep my edges and make nice triangles"), the traps that catch people out, and which package to try first.

How the engines differ

The same small examples through ear cutting, GEOS and a full mesher, side by side; what silicate and anglr tried before; and why laridae is built on CGAL.

Package survey

A reference to about 35 R packages: the algorithm and library behind each, what it takes and returns, and what it can and cannot do, with a look at Python.

Notes

What "2D", "3D" and "2.5D" mean to different people, triangles on the sphere, and what interpolation on a triangle mesh does and does not promise.

Grids as meshes

Every grid is already a mesh. Triangulate its points instead and the answer depends on the frame: one polar grid block, Delaunay in longitude and latitude, in its projection and on the sphere.

Polygon validity

What makes a polygon invalid under OGC, ESRI and s2 rules, the three ways a repair can read it, what GEOS make_valid does from R and Python, and why a mesh needs no repair.

Drawing each boundary once

Stroked polygons draw every shared border twice. Shared edges as a table of owners give county, state and country lines from one layer, each drawn once, and show where vertices stop matching.

Sizing fields and map projections

A mesh that is uniform in one projection is graded on the ground. When that can replace a sizing field, why only conformal projections keep shape, and what still needs the mesh engine.

Benchmark

For developers: speed, memory and mesh quality on country boundaries, from 23 thousand to 6.8 million vertices.

Gridded data has its own thorny word. Regular in what? is a short companion book on why a grid is regular, rectilinear or curvilinear only in a frame, and on the communities and software that blur the difference.

Edges have the same problem. Curves: bigcurve and s2 is a gentle guide to what the edge between two longitude, latitude points means, how s2 measures it on the sphere, and how bigcurve draws it in any map projection with just enough vertices.

Development drafts

Working notes that render nicely but may change, move or be dropped.

Triangles in GeoArrow

What building meshes with wkpool, laridae and cdtr suggests for storing triangles in GeoArrow: storage forms, vertex identity, provenance, constraints and depth.

Proposal: geoarrow.triangles

The same idea in the shape of a GeoArrow spec proposal: one extension type, proposed text for the spec, a Parquet default, open questions and reference checks.

math.gl terrain, read from the mesh side

The math.gl terrain roadmap against our mesh work: where it meets the mesh spec, cdtr and laridae, and the questions we are testing on our side first.

Breaklines in terrain meshes

Delatin against a constrained TIN from cdtr, on an analytic cliff and the Hobart coast: sample error, surface error and coastline height, with a deck.gl viewer.

Polygons are just lines

A polygon is segments plus a fill rule, and rings can be derived. Why that holds in the plane, from a dimension count, and where it stops: volumes, graphs in xyz and the sphere.

Reprojection meshes for raster tiles

How map libraries mesh the warp for raster tiles, measured on polar, hemispheric and antimeridian cases, with what a screen-pixel tolerance and constrained seeds change.

ST_* functions on a triangle mesh

Which ST_* functions run natively on a mesh, which need only its indices, which need one more index and which fall back to polygons, with a prototype checked and timed against sf.

ST_* on a mesh with wkpool and geos

24 ST_* functions on a mesh with no sf in the path, checked and timed against the geos package, including the full DE-9IM matrix computed from triangle indices alone.

What geoarrow.triangles needs for ST_*

A plan: a row as a feature, what the metadata must promise, what a binding caches, seven kernels, joins across two meshes, and the steps to take on our side first.

Warp Mesh Casebook

Interactive: a screen grid (ortho-cog-viewer) against source tiles (deck.gl-raster style) at the pole, the horizon, the antimeridian and in interrupted Goode, with live error heat.

Under the hood, trianglewins is a test harness: it runs the same inputs through laridae (CGAL), cdtr (CDT), trowel (spade) and RTriangle (Triangle) and checks the results with code that belongs to none of them. See the repository. The development roadmap lives in hypertidy/meshcore.