trianglewins / dev draft

Triangles in GeoArrow: notes from wkpool, laridae and cdtr

Development draft, October 2026; revised 14 October after feedback from the GeoArrow side on the dictionary form. Written for the GeoArrow discussion about storing triangles, from what we learned building triangle meshes in R. Not a spec; a list of what worked, what broke, and one possible shape.

The proposal-shaped version is Proposal: geoarrow.triangles.

The remark that started this:

we have to solve triangles in GeoArrow too at some point... we can dictionary-encode points maybe and store as a fixed-size list or struct of geoarrow.point

Dictionary-encoding the points is the right instinct. It is the vertex pool that wkpool is built on: one table of unique vertices, and geometry as integer references into it. The notes below are about the details that decide whether that works in practice.

1. Four ways to store triangles

form layout keeps adjacency Parquet notes
A. soup fixed_size_list<geoarrow.point, 3> per triangle no yes simplest; same information as WKB TRIANGLE; every shared vertex repeated (about 6 times in a typical mesh)
B. per-feature mesh struct of vertices: list<point> and triangles: list<fixed_size_list<uint32, 3>>, indices local to the row within a feature yes like glTF or PLY; one row is one mesh
C. two tables a vertex table and a triangle table of three vertex ids across features yes the form in our mesh spec
D. dictionary fixed_size_list<dictionary<int32, geoarrow.point>, 3>, one mesh per Arrow array across batches no (decode to A) rows are triangles, the dictionary is the vertex pool

Form D is the one GeoArrow has in mind: one mesh per Arrow array, each row a triangle, the dictionary holding the vertices. It is form C folded into a single column, and it has the right properties for Arrow:

What we found when testing it (script):

Form B is still useful, in addition. It is what a scalar function returns: an ST_Earcut(wkb) or ST_Triangulate(wkb) maps one geometry to one mesh, so its output must be a per-row value. Rows can get big for detailed polygons, which is the cost of a scalar result. Form C is the interchange form for writing to Parquet or a database.

2. Say how vertices were matched

Two points are "the same vertex" only by some rule. We use a ladder:

  1. exact float equality of the input coordinates;
  2. tolerance or snapping;
  3. noded, as GEOS does, where crossings become vertices;
  4. exact, with constructed points held as rationals (CGAL's exact kernel).

Dictionary-encoding by equality is rung 1 only. A mesh should record which rung produced its vertex ids, for example in field metadata ("vertex_identity": "exact_float"), so a reader knows whether two nearby vertices are meant to be one.

Why this matters: we triangulated 60 random segments with integer endpoints twice. With crossings computed in double (CGAL's Epick kernel) there were 398 crossing vertices, but only 15 lay exactly on their input segments, and 4 were spurious near-duplicates (one pair 1.9e-14 apart) where three segments meet. With exact constructions there were 394, all exactly on their segments. The exact run uses lari_cdt(exact = TRUE) on the laridae exact-cdt branch, and the check uses euclid's exact has_on().

If exact values need to travel, they can: numerator and denominator as string columns (x_num, x_den, y_num, y_den) beside the nearest doubles. That is plain data, unlike an exact number behind a pointer.

3. Constructed vertices are not input

A constrained triangulation adds vertices: crossings where input segments intersect, and Steiner points from refinement. A reader needs to tell them apart, and to trace mesh edges back to the input.

4. Triangles alone lose the polygon

A set of triangles does not say which edges were boundaries, or which triangles are inside a hole. Keep two more things:

5. Conventions worth fixing early

These are the decisions in our mesh spec (v0.1); they cost nothing to agree on and are painful to change later.

6. Indexed triangles pay off

Indexing is not only about size. In wkpool, drawing 40,000 triangles from the vertex pool with one indexed polygon() call took 0.4 s, against 74 s when each triangle was cast to its own polygon geometry first. Renderers (deck.gl, WebGL, glTF) want indexed triangles too, so forms B, C and D feed them directly.

7. Traps we hit

A possible shape

For discussion only. The mesh as one array (form D), with optional sibling columns:

triangles:   fixed_size_list<dictionary<int32, geoarrow.point>, 3>  -- CCW
constrained: fixed_size_list<bool, 3>    -- optional; edge k is v[k] -> v[k+1]
depth:       int32                       -- optional, per triangle
field metadata: vertex_identity

For a scalar function returning one mesh per geometry (form B):

struct<
  vertices:    list<geoarrow.point>,
  triangles:   list<fixed_size_list<uint32, 3>>,   -- CCW, 0-based, row-local
  constraints: list<fixed_size_list<uint32, 2>>,   -- optional
  depth:       list<int32>                         -- optional, per triangle
>

and for Parquet or a database, the two-table form C with the same column names, the triangle table keyed to the vertex table.

Where this comes from