---
title: "wkpool: Topology-based Geometry Handling"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{wkpool: Topology-based Geometry Handling}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
library(wkpool)
```

## 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, which wastes space and
needs spatial predicates (GEOS) to rediscover adjacency.

## Basic workflow

Create two adjacent squares sharing an edge:

```{r basic-setup}
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

```{r establish}
pool <- establish_topology(geoms)
pool
```

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

### Inspect the raw state

```{r report-before}
topology_report(pool)
```

### Access the pool components

```{r accessors}
pool_vertices(pool)
pool_segments(pool)
pool_feature(pool)
```

### Merge coincident vertices

```{r merge}
pool <- merge_coincident(pool)
topology_report(pool)
```

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

## Adjacency discovery

### Shared edges

```{r shared-edges}
find_shared_edges(pool)
```

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):

```{r internal-boundaries}
find_internal_boundaries(pool)
```

### Neighbour graph

```{r neighbours}
find_neighbours(pool)
```

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

```{r cycles}
cycles <- find_cycles(pool)
cycles
```

### Classify by winding

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

```{r winding}
# Area of the first cycle
cycle_signed_area(cycles[[1]], pool_vertices(pool))

# Classify all cycles
classify_cycles(pool)
```

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

```{r arc-node}
vertex_degree(pool)
find_nodes(pool)
find_arcs(pool)
arc_node_summary(pool)
```

The two squares share an edge and each square carries its own copy of
it, so the shared vertices have degree 4 and the shared edge comes back
as two arcs, one per square. In the quotient graph a duplicated
boundary counts once: the shared edge is a single arc, and its end
vertices stay nodes because three distinct edges meet there. On a
coverage with long shared boundaries the difference is large (on
silicate's `inlandwaters`, 5,418 arcs and 2,619 nodes by default, 201
arcs and 13 nodes in the quotient graph). Use `quotient = TRUE` for
polygon coverages.

```{r arc-node-quotient}
find_nodes(pool, quotient = TRUE)
find_arcs(pool, quotient = TRUE)
```

## Round-trip to WKT

Convert topology back to standard geometry formats:

```{r round-trip}
# Arcs as linestrings
arcs_to_wkt(pool)

# Cycles as polygons
cycles_to_wkt(pool)

# Raw segments
segments_to_wkt(pool, type = "linestring")[1:3]
```

## Periodic x (antimeridian)

Longitude wraps. Two hemispheres that meet at -180 and 180 have two
copies of the seam, and plain merging keeps them apart. With
`period_x = 360` the copies fuse and the seam becomes an ordinary shared
boundary (coordinates are not moved):

```{r period-x}
hemi <- wk::as_wkb(c(
  "POLYGON ((-180 -60, 0 -60, 0 60, -180 60, -180 -60))",
  "POLYGON ((0 -60, 180 -60, 180 60, 0 60, 0 -60))"
))
hp <- establish_topology(hemi)
nrow(find_shared_edges(merge_coincident(hp)))
nrow(find_shared_edges(merge_coincident(hp, period_x = 360)))
```

## Triangulation

Triangles can share the same vertex pool. `pool_triangulate()`
(experimental) ear cuts each polygon and returns a `wkpool_tri`, and
`as_pslg()` with `pool_holes()` gives the input for constrained Delaunay
engines such as RTriangle. See
`vignette("triangulation", package = "wkpool")`.

```{r tri, eval = requireNamespace("decido", quietly = TRUE), fig.width = 6, fig.height = 4}
tri <- pool_triangulate(pool)
plot(tri, asp = 1)
```

## Subsetting and combining

Pools support `[` subsetting; the full vertex pool is retained:
```{r subset}
pool[1:4]
```

Combine pools from different sources:

```{r combine}
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)
```

## Building a pool from tables

`wkpool(vertices, segments)` assembles a pool from a vertex table and a
segment table, the same shapes that `pool_vertices()` and
`pool_segments()` return. This is the way in for data that is already
indexed, such as a mesh read from another format:

```{r from-tables}
v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
s <- data.frame(.vx0 = 1:4, .vx1 = c(2:4, 1L), .feature = 1L)
wkpool(v, s)
```

## Visualization

```{r plot, fig.width = 6, fig.height = 4}
plot(pool)
```

## Related Work

### Core topology/vertex-pool (hypertidy ecosystem)

| Package | Where | Relationship to wkpool |
|---------|-------|------------------------|
| [silicate](https://CRAN.R-project.org/package=silicate) | CRAN | Topological models: `SC` (edge-vertex), `ARC` (shared boundaries), `PATH`, `TRI`. Its `silicate2` branch routes geometry through wkpool |
| [unjoin](https://CRAN.R-project.org/package=unjoin) | CRAN | Vertex deduplication via data frame normalization, used internally by silicate |
| [wk](https://CRAN.R-project.org/package=wk) | CRAN | Path/geometry indexing via `wk_coords()` |

### Mesh/triangulation

| Package | Where | Notes |
|---------|-------|-------|
| [decido](https://CRAN.R-project.org/package=decido) | CRAN | Ear cutting, the engine for `pool_triangulate()` (experimental) |
| [RTriangle](https://CRAN.R-project.org/package=RTriangle) | CRAN | Shewchuk's Triangle, constrained Delaunay with quality refinement; takes `as_pslg()` and `pool_holes()` |
| [laridae](https://github.com/hypertidy/laridae) | GitHub | Constrained Delaunay and meshing with CGAL |
| [meshcore](https://github.com/hypertidy/meshcore) | GitHub | Mesh tables and `tri_mesh()` over further constrained Delaunay engines |
| [sfdct](https://CRAN.R-project.org/package=sfdct) | CRAN | RTriangle wrapper for sf objects |

### Adjacency (computed, not stored)

| Package | Where | Approach |
|---------|-------|----------|
| [sfdep](https://CRAN.R-project.org/package=sfdep) | CRAN | `st_contiguity()` computes on-demand |
| [sf](https://CRAN.R-project.org/package=sf) | CRAN | `st_touches()`, `st_relate()` via GEOS, recomputed each time |

**Key distinction**: wkpool differs from sf/spdep by *storing* topology (shared
edges are explicit) rather than *computing* it on demand via GEOS. It is the
lightweight, `wk`-native machinery under silicate's approach.