A live constrained Delaunay mesh for R: a handle you keep editing. Add points and segments at any time (crossings are inserted for you), remove them, refine toward a minimum angle or maximum area, refine again after an edit, and read the mesh back as plain tables whenever you like. Built on the spade Rust crate via extendr.
It is the incremental sibling of cdtr, which does the same job in one shot with no Rust toolchain; the two speak the same three tables (vertices, segments, triangles with constraint depth).
# remotes::install_github("hypertidy/trowel")
install.packages("trowel", repos = c('https://hypertidy.r-universe.dev', 'https://cloud.r-project.org')) # needs cargo and rustc
library(trowel)
x <- c(0, 1, 1, 0, 0.25, 0.75, 0.75, 0.25)
y <- c(0, 0, 1, 1, 0.25, 0.25, 0.75, 0.75)
m <- mesh_new(x, y, 1:8, c(2, 3, 4, 1, 6, 7, 8, 5))
m
#> <trowel mesh> 8 vertices, 10 triangles, 8 segments (8 constraint edges)
op <- par(mfrow = c(1, 3), mar = c(0.5, 0.5, 2, 0.5))
plot(m, main = "constrained")
## a diagonal across the hole: two crossings are inserted
id <- mesh_add_points(m, c(0.1, 0.9), c(0.1, 0.9))
mesh_add_segments(m, id[1], id[2])
#> [1] 9
plot(m, main = "+ a crossing segment")
mesh_refine(m, max_area = 0.01, min_angle = 25)
plot(m, main = "+ refine")
par(op)
m
#> <trowel mesh> 86 vertices, 138 triangles, 9 segments (58 constraint edges)
Every vertex has a stable id and an origin; every triangle has a depth, the number of constraint boundaries between it and the outside.
head(mesh_vertices(m))
#> id x y origin
#> 1 1 0.00 0.00 input
#> 2 2 1.00 0.00 input
#> 3 3 1.00 1.00 input
#> 4 4 0.00 1.00 input
#> 5 5 0.25 0.25 input
#> 6 6 0.75 0.25 input
table(mesh_vertices(m)$origin)
#>
#> input steiner
#> 10 76
table(mesh_triangles(m)$depth)
#>
#> 1 2
#> 100 38
head(mesh_segments(m), 4) # the chain of vertex ids along each segment
#> segment position vertex
#> 1 1 1 1
#> 2 1 2 19
#> 3 1 3 15
#> 4 1 4 66
Attributes ride on vertices and are interpolated onto crossings and Steiner points as they are created.
z <- 2 * x + 3 * y
m2 <- mesh_new(x, y, 1:8, c(2, 3, 4, 1, 6, 7, 8, 5), PA = cbind(z = z))
mesh_refine(m2, max_area = 0.01)
v <- mesh_vertices(m2)
range(v$z - (2 * v$x + 3 * v$y))
#> [1] 0 0
Rebuilding is what the one-shot tools do; here an edit followed by a
refine only has new work to do near the edit. On the sf North Carolina
counties (1255 vertices, 1357 constraint edges, area-refined to about
7700 triangles), a bulk constrained build is 2.4 ms (Triangle 2.7, cdtr
3.9), bulk plus refine is 12.6 ms (Triangle 4.5, cdtr 12.9), and a
re-refine after inserting one point is 8.4 ms against a 12.3 ms cdtr
rebuild. Most of that 8.4 ms is refining the region outside the
constraints and then discarding it: spade’s refiner keeps an internal
excluded-face set but does not let the caller supply one, and its own
outer-face detection misreads coverages. With that hook the re-refine
would be about 2 ms; it is the obvious upstream contribution. Numbers
from inst/benchmarks/bench.R.
Milestones 1 and 2 of the design note (bulk load, extractors, round trip; stable ids through add/remove; crossings with interpolated attributes; refine with chain repair) are done. Regional refinement and per-layer depth are the open questions.