New vignette “Triangulation”: ear cutting with
pool_triangulate(), the PSLG route (as_pslg()
with pool_holes()) to RTriangle, and taking its triangles
back onto a vertex pool with new_wkpool_tri(), on
silicate’s inlandwaters. The other vignettes now cover
periodic x, wkpool(vertices, segments) and triangle pools,
and point to it.
pool_holes() returns a point inside each hole even
when the hole is not convex: the centroid of an ear of the hole ring,
clear of every pool vertex, instead of the mean of the ring’s vertices,
which could fall outside the hole and make RTriangle erase the polygon
around it (on inlandwaters this lost most of the area).
Holes filled exactly by another polygon of the pool (enclaves) are no
longer returned, since they are not holes of the coverage.
plot() for wkpool_tri accepts
xlab and ylab, and sets the plot extent from
the triangles drawn rather than the whole vertex pool, so a subset is
drawn at its own extent.
New plot() method for wkpool_tri: one
polygon() call indexing the vertex pool, filled by feature
(40,000 triangles draw in about 0.4 s to png, where casting to wk
polygons and plotting those took over a minute).
New, experimental wkpool_tri class: a vector of
triangles (.vx0, .vx1, .vx2,
.feature, .part) on the same kind of vertex
pool as a wkpool. pool_triangulate(x, engine = "decido")
ear-cuts each polygon of a pool using its path provenance; ear cutting
creates no vertices, so the vertex table is passed through unchanged.
merge_coincident() accepts a wkpool_tri
(triangulate first, merge later gives the same result as merging first).
pool_triangles() and tri_segments() give the
triangle table and the triangle edges as a wkpool;
wk_handle() presents one POLYGON per triangle, with crs and
geodesic carried. ‘decido’ is suggested.
wkpool_tri is experimental and may change in a later
release. In particular the part is stored as a .part field
on each triangle (the simplest option); the alternative is a
.path field pointing at the outer ring’s path, recovering
feature and part from pool_paths() as segments do.
merge_coincident() and topology_report()
gain period_x (default NULL, behaviour
unchanged). With period_x = 360, vertices are keyed on
x %% 360, so the two copies of a +-180 seam fuse (and 0 to
360 data fuses at 0 and 360); after merging, the seam is an ordinary
shared boundary for find_shared_edges(),
find_internal_boundaries() and quotient arcs. The period is
never inferred from the crs. Coordinates are not moved, so geometry
emitted from a fused pool jumps by one period across the seam. With a
tolerance, x is wrapped, snapped, then wrapped again (#3).wkpool(vertices, segments) is now exported and
documented: the user-level constructor from a vertex table and a segment
table, as returned by pool_vertices() and
pool_segments() (#2).
New pool_holes(), the same function as
hole_points() under a name that matches the other
pool_*() accessors. hole_points() is kept
(#1).
cycles_to_wkb() / cycles_to_wkt() build
all polygons in one wk::wk_polygon() call and all
multipolygons in one wk::wk_collection() call, instead of
looping over features and parts (10,000 hexagons: 5.7 s to 0.16 s). The
fallback for pools without path provenance matches cycle edges to
segments with one vctrs::vec_match() instead of a scan per
cycle. Output is unchanged.
establish_topology() and
merge_coincident() no longer build hash tables to look up
vertex ids: pools they mint have .vx = 1..n, where an id is
its own position, so validation in new_wkpool() and the
segment remap use it directly (other pools fall back to
match()). On 1M line coordinates
merge_coincident() drops from 0.35 s to 0.12 s, and the
vertex pipeline is now faster than silicate’s PATH0() on
every benchmark input (see bench/README.md).
find_cycles(), classify_cycles(),
hole_points() and find_neighbours() no longer
scale quadratically: on 10,000 hexagons
find_neighbours(type = "edge") drops from 19 s (13 GB
allocated) to 0.03 s and classify_cycles() from 8.3 s to
0.23 s. find_shared_edges(),
find_internal_boundaries() and
topology_report() key edges with vctrs instead of
paste(). Results are unchanged, except that
find_neighbours() output no longer carries a stray
out.attrs attribute and the features column of
find_shared_edges() is a plain named list.
bench/ holds a benchmark against silicate (not part
of the built package).
vertex_degree(), find_nodes(),
find_arcs(), as_arcs(),
arc_node_summary(), arcs_to_wkt() and
arcs_to_wkb() gain a quotient argument
(default FALSE, behaviour unchanged). In the quotient graph, duplicated
shared boundaries - the same undirected vertex pair carried by more than
one feature - count once: the first occurrence keeps its direction,
multiplicity is discarded whatever its count. A vertex interior to a
shared boundary has quotient degree 2 (the degree-2 invariant holds at
this level, including for vertices minted by densification), true
junctions remain nodes, and find_arcs(x, quotient = TRUE)
yields the TopoJSON-style arc decomposition of a polygon layer: each
shared border once, not once per feature.
Characterization guards pin the default duplicated-boundary and antimeridian-seam semantics as explicit contracts: boundary-interior vertices are degree-4 by default, seams of a +-180 split stay distinct through merge, and merge keys are exact coordinates with no wrapping of any kind.
find_arcs() now runs on a cpp11 kernel (wkpool’s
first compiled code, LinkingTo: cpp11 only, no system requirements). The
algorithm, adjacency ordering, node ordering and output are identical to
the pure-R implementation, which is retained as the executable
specification (find_arcs_walk_r, internal) and pinned to
the kernel by conformance tests across nodes, loops, open lines, holes,
grids, subsets and shuffled pools.
Scale: the pathological all-nodes grid at 2.56 million segments runs in about 1 second (was ~10x that in R after the linear rewrite, and unboundedly worse before it); 2 million segments of long arcs walk in under a second, with remaining time dominated by the R-side dense-id mapping. Real-world effect: the CGAZ world admin boundaries (~10M segments) drop from ~44s to a few seconds.
merge_coincident() now groups vertices on the
double-precision bit pattern (via vctrs::vec_group_id())
instead of formatted text keys. This fixes a silent correctness bug: the
old keys went through as.character() at ~15 significant
digits, so distinct doubles differing only beyond printable precision
merged even at tolerance = 0. Exact now means
exact.
When the pool carries z, vertices are keyed on all
coordinate columns: equal x/y with different z no longer merge silently.
Tolerance is documented honestly as a snap grid (cell size
tolerance), not a distance guarantee, and canonical
vertices keep their original coordinates.
topology_report() computes its counts directly from
vertex groups instead of performing a full internal
merge_coincident() plus
find_shared_edges().
The quadratic idioms are gone: find_arcs() uses
dense integer adjacency with amortized cursors and a preallocated walk
buffer (was: character-keyed lists grown with c() in
loops); pool_combine() remaps by position with per-input
offsets (was: character-named lookup tables and growing vectors);
as_arcs() and vertex_degree() are vectorized.
On a 160x160 grid of squares (102400 segments) find_arcs()
drops from minutes to under half a second, and all core verbs now scale
linearly.
pool_compact() remap corrected for pools whose
segment order does not follow pool order (latent indexing
assumption).
establish_topology() now mints a .path
id per segment - one id per input ring or linestring - with a sidecar
paths table (.path, .feature,
.part, .ring, captured from
wk::wk_coords() identifiers). Provenance survives
subsetting, merge_coincident(), pool_compact()
and pool_combine() (which offsets path ids to keep them
unique), and is exposed via the new accessors pool_path()
and pool_paths(). new_wkpool() gains
path and paths arguments.
find_cycles() uses provenance when present: a cycle
is a path whose segment chain closes. Rings are recovered exactly, in
input order and input winding, robust to segment reordering (chains are
rebuilt by connectivity), and a broken ring after subsetting is dropped
rather than mis-walked. The result carries a path attribute
mapping cycles to path ids. Pools without provenance keep the legacy
storage-order walk.
The winding-convention issue is resolved structurally: with
provenance, ring roles are known (the first ring of each part is the
exterior, later rings are its holes), so classify_cycles()
and hole_points() no longer guess from winding and the
convention argument is only consulted for provenance-free
pools. hole_points() on a simple polygon now returns
NULL as intended.
cycles_to_wkb(feature = TRUE) reconstructs original
feature structure exactly when provenance is present: rings grouped into
their original part (exterior first, then that part’s own holes), parts
grouped into POLYGON or MULTIPOLYGON features. This replaces the
heuristics (all holes with the first outer; holes dropped for multi-part
features) for established pools; provenance-free pools keep the old
behaviour.
All round-trip emitters (arcs_to_*(),
cycles_to_*(), segments_to_*()) are rebuilt on
wk’s C-level construction filters (wk::wk_linestring(),
wk::wk_polygon(), wk::wk_collection()). WKB is
now the primary product and WKT is derived from it; no coordinate text
is assembled anywhere in wkpool.
Consequences: WKB output preserves coordinates at full double precision (previously text formatting perturbed doubles at around the 15th significant digit); z vertex values are carried through all emitters (previously dropped); rings are closed by wk; crs and geodesic ride along by construction. WKT output uses wk’s writer (16 significant digits, trimmed) - use the WKB emitters when bit-exact coordinates matter.
Behaviour is otherwise unchanged. (The documented simplifications
in cycles_to_wkb(feature = TRUE) were retained at this
stage and have since been superseded by path provenance for established
pools - see above; they still describe the provenance-free
fallback.)
wk::wk_handle() is implemented for wkpool: a pool
presents as one LINESTRING per segment (length preserved), with crs and
geodesic attached. The wk ecosystem’s generic conversions now work
directly on a pool: wk::as_wkb(),
wk::as_wkt(), wk::wk_coords(),
wk::wk_meta(), geos::as_geos_geometry(), and
anything else built on wk_handle(). Arcs and cycles remain
explicit conversions.
The handled path is built natively from the pool
(wk::xy() indexed by the segment table, through wk’s
C-level linestring filter): no text round trip, coordinates at full
double precision, XYZ when the pool carries z.
A wkpool now participates in wk’s CRS propagation model. The CRS
and geodesic flag of the input are captured by
establish_topology() (via wk::wk_crs() and
wk::wk_is_geodesic()), carried through subsetting,
merge_coincident(), pool_compact(),
as_arcs() and pool_combine(), and restored
onto the output of segments_to_wkt(),
arcs_to_wkt(), cycles_to_wkt() and their WKB
counterparts.
Methods for wk::wk_crs(),
wk::wk_set_crs(), wk::wk_is_geodesic() and
wk::wk_set_geodesic() are provided for wkpool objects. The
CRS is opaque and carried, never interpreted, per wk
convention.
pool_combine() resolves the CRS across inputs with
wk::wk_crs_output(): inherit values give way to concrete
values, and combining pools with unequal concrete CRS is an
error.
new_wkpool() is now exported, so downstream packages
that construct pools directly (e.g. bigcurve) can do so through a
supported constructor that checks invariants and carries
crs/geodesic.
Removed as_decido() which wasn’t fully worked
out.
Fixed wkpool() which never worked before.
Added check_wkpool helper function.
arcs_to_wkt() / arcs_to_wkb() — arcs
become linestringscycles_to_wkt() / cycles_to_wkb() — cycles
become polygons, with hole nestingsegments_to_wkt() / segments_to_wkb() —
raw segments as linestrings, multilinestring, or pointsvertex_degree() counts segments touching each
vertexfind_nodes() identifies branch points and endpoints
(degree ≠ 2)find_arcs() extracts maximal segment sequences between
nodesas_arcs() returns wkpool with .arc column
for arc membershiparc_node_summary() reports arc/node structure
statisticsArcs are the “uninterrupted lines” — sequences of segments passing only through degree-2 vertices. Useful for line simplification, network extraction, and efficient storage.
Initial release. Vertex pool topology for wk-handleable geometry.
establish_topology() converts any wk-handleable
geometry to segments + vertex poolmerge_coincident() discovers shared vertices (exact or
tolerance-based)pool_vertices(), pool_segments(),
pool_feature() access the structurepool_combine() merges multiple pools with proper index
remappingpool_compact() removes unreferenced verticesfind_shared_edges() finds edges shared by multiple
featuresfind_internal_boundaries() finds edges traversed in
opposite directions (true shared boundaries)find_neighbours() builds adjacency from shared edges or
verticestopology_report() summarizes vertex/edge sharingfind_cycles() discovers closed rings from segment
connectivitycycle_signed_area() computes signed area (shoelace
formula)classify_cycles() identifies outer rings vs holes by
windingreverse_cycle() flips winding directionhole_points() extracts hole centroids for
triangulation"sf" (default) or
"ogc" winding rulesas_pslg() exports to RTriangle format (P, S
matrices)as_decido() exports to decido format (0-indexed)plot.wkpool() for quick visualization.vx integers for stable vertex identity.feature