trianglewins / benchmark

trianglewins: triangulation at scale

Four constrained Delaunay backends for R on country boundaries from geoBoundaries (sds::CGAZ()), from Kosovo (23 thousand vertices) to the whole world (6.8 million). Times are medians of repeated runs, each job in its own R process.

Findings

• Constrained triangulation scales the same way in all four. On the polygon datasets the times are within a factor of about 1.5 of each other up to South America (634 thousand vertices, about 2.1 to 2.7 s), except trowel there (6.2 s). For the whole world (6.8 million vertices, 10.1 million triangles) RTriangle took 36 s, laridae 41 s, cdtr 51 s and trowel 174 s. All four produce the same triangle count on every polygon dataset.
• trowel slows down sharply on large, unordered input. On a million points it takes 152 s, where the others take 2 to 4 s. Its 100 thousand point run is already 13 times slower than the others. mesh_new() inserts points one at a time in input order, so spade walks a long way to find each point. laridae had the same problem until it sorted points spatially before inserting them. Sorting the points or using spade's bulk load should close most of the gap.
• A live mesh pays off for edits. Adding 1000 points to the world mesh took 0.09 s in laridae and 0.57 s in trowel. Rebuilding with those points took 44 s in RTriangle and 49 s in cdtr, so a live handle is several hundred times faster. On South America the insert took 13 ms in laridae and 76 ms in trowel, against 2.2 to 2.4 s for a rebuild.
• cdtr uses the least memory. Peak memory for the world was 2.4 GB for cdtr, 3.1 GB for trowel, 5.5 GB for RTriangle and 5.6 GB for laridae. Inserting into laridae's world mesh peaked at 8.9 GB. These figures include R's own copies of the input and output tables.
• RTriangle is still the fastest refiner, but the gap narrows at scale. Area refinement on South America took 2.2 s in RTriangle, against 4.0 s in cdtr, 4.3 s in laridae and 7.7 s in trowel. trowel stalled on southern Africa: it took 17.7 s, stopped incomplete, and left triangles with a 0 degree minimum angle.
• No backend reaches the quality bound on large coastlines. With a 20 degree minimum angle added, every backend stops short on every dataset from Indonesia (254 thousand vertices) upward, either at the 100 thousand Steiner point budget or at the edge-length floor. Only 15 to 75 percent of triangles meet the angle bound. Quality times on large inputs therefore measure how far each backend gets within that budget, not the cost of finishing.
• Shared borders given twice cost little. southern_africa_rings (every border twice, 475 thousand vertices before merging) took 3 to 12 percent longer than the merged version in laridae, cdtr and trowel, and produced the same triangles. RTriangle refuses it ("Duplicated vertices in P").
• No timeouts and no crashes. All 180 jobs completed within 900 s and 12 GB. The 4 errors are RTriangle's refusals of duplicated vertices.

Time against input size

Seconds (log scale) against input vertices (log scale), polygon datasets only. Constrained: the triangulation of the vertices and segments, outside removed. Area: refined until no triangle exceeds bounding box area / 100000. Quality: the same area bound plus a 20 degree minimum angle. A run that timed out or ran out of memory has no point.

Delaunay of points

Points sampled from the world's boundary vertices, no segments, meshed over their convex hull.

Editing a mesh: 1000 new points

laridae and trowel add 1000 points to a live constrained mesh (only the insert is timed). cdtr and RTriangle have no handle, so the time is a rebuild with the points included.

Peak memory

Peak resident memory of the job's R process (MB, log scale), including the input tables.

All runs

Datasets

Method

Inputs come from sds::CGAZ(), the geoBoundaries CGAZ ADM0 GeoParquet (CC BY 4.0). Rings are converted by bench/cgaz_pslg.py into a vertex table and a segment table: exactly repeated vertices are merged and repeated segments dropped, so shared borders appear once (except southern_africa_rings, which keeps every ring in full). Coordinates are longitude and latitude, triangulated as planar xy (coordinate dimension 2; the output is triangles, topological dimension 2). Each backend is called through the same adapter as the rest of trianglewins, so times include reading the result tables back into R. Every refinement has a Steiner budget of 100000 vertices. The area and angle columns are computed from the output; segment preservation and the empty-circle test run on inputs up to 50000 vertices. Code: bench/ in mdsumner/trianglewins.