Skip to contents

Changelog

Source: NEWS.md

wkpool 0.4.0

  • 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).

Triangles (experimental)

  • 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.

Periodic x (antimeridian)

  • 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).

Constructors and naming

Performance

Quotient boundary semantics

  • 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.

Compiled arc kernel (first src/)

  • 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.

Exact coordinate identity and linear internals

  • 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).

Path provenance (.path)

  • 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.

Native emitters

  • 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_handle: a wkpool is wk-handleable

  • 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.

CRS round trip

wkpool 0.3.0

CRAN release: 2026-03-05

  • Removed as_decido() which wasn’t fully worked out.

  • Fixed wkpool() which never worked before.

  • Added check_wkpool helper function.

wkpool 0.2.0

Round-trip to wk

Arc-node topology

Arcs are the “uninterrupted lines” — sequences of segments passing only through degree-2 vertices. Useful for line simplification, network extraction, and efficient storage.

wkpool 0.1.0

Initial release. Vertex pool topology for wk-handleable geometry.

Core functions

Topology discovery

Cycle and winding analysis

Triangulation export

  • as_pslg() exports to RTriangle format (P, S matrices)
  • as_decido() exports to decido format (0-indexed)

vctrs integration

  • wkpool is a vctrs rcrd: subset, combine operations work
  • plot.wkpool() for quick visualization

Design principles

  • Segments are the atomic primitive — the waist of the hourglass
  • Observe, don’t correct — represent truth, fixing is separate
  • Minted .vx integers for stable vertex identity
  • Feature provenance tracked via .feature