wkpool: Topology-based Geometry Handling

Why topology?

wkpool represents geometry as segments referencing a shared vertex pool. Topology emerges naturally: shared edges, neighbours, and ring structure become simple lookups.

Simple features store geometry as complete coordinate sequences per feature. Two adjacent polygons duplicate their shared boundary — wasteful in entropy and requiring spatial predicates (GEOS) to rediscover adjacency.

Basic workflow

Create two adjacent squares sharing an edge:

library(wk)
library(wkpool)

# Two adjacent unit squares
poly1 <- wkt("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))")
poly2 <- wkt("POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))")
geoms <- c(poly1, poly2)

Establish topology

pool <- establish_topology(geoms)
pool
#> <wkpool[8 segments, 10 vertices]>
#> [1] <segment: 1->2>  <segment: 2->3>  <segment: 3->4>  <segment: 4->5> 
#> [5] <segment: 6->7>  <segment: 7->8>  <segment: 8->9>  <segment: 9->10>

At this stage, vertices are indexed but not yet merged — the shared edge exists as duplicate coordinate pairs.

Inspect the raw state

topology_report(pool)
#> $n_vertices_raw
#> [1] 10
#> 
#> $n_vertices_unique
#> [1] 6
#> 
#> $n_duplicate_vertices
#> [1] 4
#> 
#> $n_near_miss_vertices
#> [1] 0
#> 
#> $n_segments
#> [1] 8
#> 
#> $n_shared_edges
#> [1] 1
#> 
#> $n_features
#> [1] 2

Access the pool components

pool_vertices(pool)
#>    .vx x y
#> 1    1 0 0
#> 2    2 1 0
#> 3    3 1 1
#> 4    4 0 1
#> 5    5 0 0
#> 6    6 1 0
#> 7    7 2 0
#> 8    8 2 1
#> 9    9 1 1
#> 10  10 1 0
pool_segments(pool)
#>   .vx0 .vx1 .feature
#> 1    1    2        1
#> 2    2    3        1
#> 3    3    4        1
#> 4    4    5        1
#> 5    6    7        2
#> 6    7    8        2
#> 7    8    9        2
#> 8    9   10        2
pool_feature(pool)
#> [1] 1 1 1 1 2 2 2 2

Merge coincident vertices

pool <- merge_coincident(pool)
topology_report(pool)
#> $n_vertices_raw
#> [1] 6
#> 
#> $n_vertices_unique
#> [1] 6
#> 
#> $n_duplicate_vertices
#> [1] 0
#> 
#> $n_near_miss_vertices
#> [1] 0
#> 
#> $n_segments
#> [1] 8
#> 
#> $n_shared_edges
#> [1] 1
#> 
#> $n_features
#> [1] 2

After merging, shared edge vertices reference the same pool indices.

Adjacency discovery

Shared edges

find_shared_edges(pool)
#>   edge_key .vx0 .vx1 .feature segment_idx features
#> 2      2-3    2    3        1           2     1, 2
#> 8      2-3    2    3        2           8     1, 2

Returns segment indices that appear in multiple features.

Internal boundaries

For polygon data, shared edges with opposite winding indicate true internal boundaries (not self-shared rings):

find_internal_boundaries(pool)
#> <wkpool[2 segments, 6 vertices]>
#> [1] <segment: 2->3> <segment: 3->2>

Neighbour graph

find_neighbours(pool)
#>   feature_a feature_b
#> 3         1         2

Returns a data frame of feature pairs that share an edge.

Ring and cycle analysis

Topology enables ring discovery without parsing WKT structure.

Find closed cycles

cycles <- find_cycles(pool)
cycles
#> [[1]]
#> [1] 1 2 3 4
#> 
#> [[2]]
#> [1] 2 5 6 3

Classify by winding

Signed area distinguishes outer rings from holes. Following the SF convention, negative area indicates an outer ring, positive indicates a hole:

# Area of the first cycle
cycle_signed_area(cycles[[1]], pool_vertices(pool))
#> [1] 1

# Classify all cycles
classify_cycles(pool)
#>   cycle area type
#> 1     1    1 hole
#> 2     2    1 hole

Use reverse_cycle() to flip winding if needed.

Arc-node topology

Arcs are maximal sequences of segments passing through degree-2 vertices. Nodes are vertices where degree ≠ 2 (branch points or endpoints).

vertex_degree(pool)
#> 1 2 3 4 5 6 
#> 2 4 4 2 2 2
find_nodes(pool)
#> [1] 2 3
find_arcs(pool)
#> [[1]]
#> [1] 2 1 4 3
#> 
#> [[2]]
#> [1] 2 3
#> 
#> [[3]]
#> [1] 2 5 6 3
#> 
#> [[4]]
#> [1] 2 3
arc_node_summary(pool)
#> $n_vertices
#> [1] 6
#> 
#> $n_nodes
#> [1] 2
#> 
#> $n_arcs
#> [1] 4
#> 
#> $degree_distribution
#> deg
#> 2 4 
#> 4 2 
#> 
#> $arc_length_distribution
#> arc_lengths
#> 1 3 
#> 2 2 
#> 
#> $mean_arc_length
#> [1] 2

Round-trip to WKT

Convert topology back to standard geometry formats:

# Arcs as linestrings
arcs_to_wkt(pool)
#> <wk_wkt[4]>
#> [1] LINESTRING (1 0, 0 0, 0 1, 1 1) LINESTRING (1 0, 1 1)          
#> [3] LINESTRING (1 0, 2 0, 2 1, 1 1) LINESTRING (1 0, 1 1)

# Cycles as polygons
cycles_to_wkt(pool)
#> <wk_wkt[0] with CRS=NA>

# Raw segments
segments_to_wkt(pool, type = "linestring")[1:3]
#> <wk_wkt[3]>
#> [1] LINESTRING (0 0, 1 0) LINESTRING (1 0, 1 1) LINESTRING (1 1, 0 1)

Triangulation integration

The pool maps directly to constrained triangulation inputs.

RTriangle (PSLG)

pslg <- as_pslg(pool)
str(pslg)
#> List of 2
#>  $ P: num [1:6, 1:2] 0 1 1 0 2 2 0 0 1 1 ...
#>  $ S: int [1:8, 1:2] 1 2 3 4 2 5 6 3 2 3 ...

For polygons with holes, use hole_points() to generate interior points that tell the triangulator which regions to exclude:

# A polygon with a hole
holed <- wk::as_wkb(
  "POLYGON ((0 0, 4 0, 4 4, 0 4, 0 0), (1 1, 3 1, 3 3, 1 3, 1 1))"
)
hp <- establish_topology(holed)
hp <- merge_coincident(hp)
pslg_h <- as_pslg(hp)
holes <- hole_points(hp)
tri <- RTriangle::triangulate(
  RTriangle::pslg(P = pslg_h$P, S = pslg_h$S, H = holes)
)

Subsetting and combining

Pools support [ subsetting — the full vertex pool is retained:

pool[1:4]
#> <wkpool[4 segments, 6 vertices]>
#> [1] <segment: 1->2> <segment: 2->3> <segment: 3->4> <segment: 4->1>

Combine pools from different sources:

pool_a <- establish_topology(wk::wkt("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))"))
pool_b <- establish_topology(wk::wkt("POLYGON ((5 5, 6 5, 6 6, 5 6, 5 5))"))
pool_combine(pool_a, pool_b)
#> <wkpool[8 segments, 10 vertices]>
#> [1] <segment: 1->2>  <segment: 2->3>  <segment: 3->4>  <segment: 4->5> 
#> [5] <segment: 6->7>  <segment: 7->8>  <segment: 8->9>  <segment: 9->10>

Visualization

plot(pool)