Package {wkpool}


Title: Vertex Pool Topology for Well-Known Geometry
Version: 0.5.0
Description: Establishes and maintains vertex pool topology for geometry handled by 'wk'. Segments are the atomic unit, vertices are shared via integer references into a pool. Topology is made discoverable via coincident vertex detection while not requiring modification of the input data. Topological data models follow principles described in Worboys and Duckham (2004, ISBN:978-0415283755). The edge-based topology geometry decomposed into vertices and directed edge pairs is a simplification of the quad-edge case in Guibas and Stolfi (1985) <doi:10.1145/282918.282923>. Triangle pools on the same vertices answer common polygon questions (area, centroid, the DE-9IM relation between regions, point location, boundaries, clipping, union) from the triangles directly, with exact orientation tests after Shewchuk (1997) <doi:10.1007/PL00009321>.
License: MIT + file LICENSE
URL: https://hypertidy.github.io/wkpool/, https://github.com/hypertidy/wkpool
BugReports: https://github.com/hypertidy/wkpool/issues
Encoding: UTF-8
Imports: vctrs, wk (≥ 0.9.4)
Suggests: cdtr, decido, geos, knitr, nanoarrow, rmarkdown, RTriangle, silicate, spelling, testthat (≥ 3.0.0), traipse
VignetteBuilder: knitr
LinkingTo: cpp11
Config/testthat/edition: 3
Language: en-GB
Config/roxygen2/version: 8.1.1
NeedsCompilation: yes
Packaged: 2026-11-16 02:15:43 UTC; mdsumner
Author: Michael Sumner [aut, cre, cph]
Maintainer: Michael Sumner <mdsumner@gmail.com>
Repository: CRAN
Date/Publication: 2026-11-16 08:50:02 UTC

wkpool: Vertex Pool Topology for Well-Known Geometry

Description

Establishes and maintains vertex pool topology for geometry handled by 'wk'. Segments are the atomic unit, vertices are shared via integer references into a pool. Topology is made discoverable via coincident vertex detection while not requiring modification of the input data. Topological data models follow principles described in Worboys and Duckham (2004, ISBN:978-0415283755). The edge-based topology geometry decomposed into vertices and directed edge pairs is a simplification of the quad-edge case in Guibas and Stolfi (1985) doi:10.1145/282918.282923. Triangle pools on the same vertices answer common polygon questions (area, centroid, the DE-9IM relation between regions, point location, boundaries, clipping, union) from the triangles directly, with exact orientation tests after Shewchuk (1997) doi:10.1007/PL00009321.

Author(s)

Maintainer: Michael Sumner mdsumner@gmail.com [copyright holder]

Authors:

See Also

Useful links:


Summarize arc-node structure

Description

Summarize arc-node structure

Usage

arc_node_summary(x, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

quotient

Walk the quotient graph: duplicated shared boundaries collapse to a single undirected edge (first occurrence keeps its direction), so a boundary shared by two features becomes ONE arc rather than one per feature, and its interior vertices are degree-2 pass-throughs. This is the TopoJSON-style arc decomposition of a polygon layer. Default FALSE walks every segment.

Value

List with counts and degree distribution

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
arc_node_summary(merged)


Convert arcs to WKT linestrings

Description

Convert arcs to WKT linestrings

Usage

arcs_to_wkb(x, quotient = FALSE, ...)

arcs_to_wkt(x, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

quotient

Walk the quotient graph: duplicated shared boundaries collapse to a single undirected edge (first occurrence keeps its direction), so a boundary shared by two features becomes ONE arc rather than one per feature, and its interior vertices are degree-2 pass-throughs. This is the TopoJSON-style arc decomposition of a polygon layer. Default FALSE walks every segment.

...

Passed to wk::as_wkb()

Details

Each arc (maximal segment sequence between nodes) becomes a linestring.

Geometry is assembled natively via wk::wk_linestring() (WKB first, WKT derived from it): coordinates are emitted at full double precision, z is carried when the pool has it, and the pool's crs and geodesic flag are attached to the output.

Value

A wk_wkt vector of LINESTRING geometries

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
arcs_to_wkt(merged)


Convert arcs to a wkpool of arc segments

Description

Convert arcs to a wkpool of arc segments

Usage

as_arcs(x, arc_id = TRUE, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

arc_id

Logical: add .arc column to track arc membership?

quotient

Walk the quotient graph: duplicated shared boundaries collapse to a single undirected edge (first occurrence keeps its direction), so a boundary shared by two features becomes ONE arc rather than one per feature, and its interior vertices are degree-2 pass-throughs. This is the TopoJSON-style arc decomposition of a polygon layer. Default FALSE walks every segment.

Value

A wkpool with segments grouped by arc

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
as_arcs(merged)


Convert wkpool to a PSLG (planar straight line graph)

Description

Convert wkpool to a PSLG (planar straight line graph)

Usage

as_pslg(x, ...)

Arguments

x

A wkpool (will be passed through merge_coincident if not already)

...

passed to merge_coincident

Details

Produces a planar straight line graph for constrained Delaunay triangulation. The vertex pool maps directly to P, and segment indices map directly to S (both 1-indexed). Shared boundaries appear once per feature.

A PSLG does not record which side of a segment is inside. For RTriangle, pass hole points from pool_holes() as H. The triangles come back as vertex and index matrices, and new_wkpool_tri() puts them on a vertex pool again; see vignette("triangulation", package = "wkpool").

For ear cutting that keeps the feature of each triangle, see pool_triangulate() (experimental).

Value

A list with P (vertex matrix) and S (segment matrix), the form used by RTriangle::pslg()

Examples

x <- wk::as_wkb("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))")
pool <- establish_topology(x)
as_pslg(pool)


Classify cycles as outer rings or holes based on winding

Description

Classify cycles as outer rings or holes based on winding

Usage

classify_cycles(x, convention = c("sf", "ogc"))

Arguments

x

A wkpool (ideally after merge_coincident)

convention

Which winding convention to use when the pool has no path provenance: "sf" (default) or "ogc"

  • sf: negative area = outer, positive = hole

  • ogc: positive area = outer, negative = hole

Details

When the pool carries path provenance, ring roles are structural: the first ring of each part is the exterior and later rings are its holes, regardless of winding, and convention is not consulted. The signed area still reports the observed winding. Pools without provenance are classified by winding under the requested convention.

Value

A data frame with cycle index, signed area, and type (outer/hole); when path provenance is present, also .path and .feature

Examples

x <- wk::as_wkb(c(
  paste0(
    "MULTIPOLYGON (((0 0, 0 1, 0.75 1, 1 0.8, 0.5 0.7, ",
    "0.8 0.6, 0.69 0, 0 0), (0.2 0.2, 0.5 0.2, ",
    "0.5 0.4, 0.3 0.6, 0.2 0.4, 0.2 0.2)))"),
  "MULTIPOLYGON (((0.69 0, 0.8 0.6, 1.1 0.63, 1.23 0.3, 0.69 0)))"
))

pool <- establish_topology(x)
merged <- merge_coincident(pool)
classify_cycles(merged)


Calculate signed area of a cycle

Description

Calculate signed area of a cycle

Usage

cycle_signed_area(cycle, pool)

Arguments

cycle

Integer vector of .vx IDs forming a closed cycle

pool

Vertex pool data frame (from pool_vertices)

Details

Uses the shoelace formula to compute signed area. The sign indicates winding direction. For typical geographic data (Simple Features convention):

This is intrinsic to the geometry: we observe winding, not declare it.

Value

Numeric signed area.

Examples

x <- wk::as_wkb("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))")
pool <- establish_topology(x)
merged <- merge_coincident(pool)
cycles <- find_cycles(merged)
cycle_signed_area(cycles[[1]], pool_vertices(merged))


Convert cycles to WKT polygons

Description

Convert cycles to WKT polygons

Usage

cycles_to_wkt(x, feature = TRUE, convention = c("sf", "ogc"))

cycles_to_wkb(x, feature = TRUE, convention = c("sf", "ogc"), ...)

Arguments

x

A wkpool (ideally after merge_coincident)

feature

Logical: attempt to reconstruct original features? If TRUE, groups cycles by .feature and nests holes in outers. If FALSE, each cycle becomes a separate polygon.

convention

Winding convention: "sf" (default) or "ogc"; only consulted for pools without path provenance

...

Passed to wk::as_wkb()

Details

Converts cycles back to polygons. When feature = TRUE and the pool carries path provenance (minted by establish_topology()), the original feature structure is reconstructed exactly: rings are grouped into their original part (exterior first, then that part's holes) and parts into their original feature (POLYGON or MULTIPOLYGON), with winding emitted as stored and convention not consulted. Pools without provenance fall back to a heuristic that groups rings by feature and nests all holes with the first outer.

Geometry is assembled natively via wk::wk_polygon() and wk::wk_collection() (WKB first, WKT derived from it): coordinates are emitted at full double precision, rings are closed by wk, z is carried when the pool has it, and the pool's crs and geodesic flag are attached to the output.

Value

A wk_wkt vector of POLYGON geometries

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
cycles_to_wkt(merged)


Establish topology from any wk-handleable geometry

Description

Establish topology from any wk-handleable geometry

Usage

establish_topology(x, ...)

Arguments

x

Any geometry wk can handle (sf, sfc, wkb, wkt, geos, s2, xy, ...)

...

reserved for future use

Details

Vertices are minted as-is from the input coordinates. No snapping or deduplication is performed - the pool represents the exact truth of the input geometry. Use merge_coincident() afterwards to discover/establish shared topology.

Segments track their feature origin via .feature attribute, enabling discovery of shared boundaries and neighbour relations.

Segments also carry a minted .path id - one id per input ring or linestring - with a sidecar table (see pool_paths()) recording each path's feature, part and ring identity as captured from wk::wk_coords(). This provenance makes cycles, ring roles and feature structure recoverable exactly, in input order and input winding: see find_cycles(), classify_cycles() and cycles_to_wkt().

The coordinate reference system of the input (as reported by wk::wk_crs()) and its geodesic flag (wk::wk_is_geodesic()) are captured on the pool and travel with it through subsetting, merging and compaction, and back out through the round-trip functions.

Value

A wkpool object (segments with vertex pool)

Examples

x <- wk::as_wkb(c(
  paste0(
    "MULTIPOLYGON (((0 0, 0 1, 0.75 1, 1 0.8, 0.5 0.7, ",
    "0.8 0.6, 0.69 0, 0 0), (0.2 0.2, 0.5 0.2, ",
    "0.5 0.4, 0.3 0.6, 0.2 0.4, 0.2 0.2)))"),
  "MULTIPOLYGON (((0.69 0, 0.8 0.6, 1.1 0.63, 1.23 0.3, 0.69 0)))"
))

pool <- establish_topology(x)


Find arcs (maximal segment sequences between nodes)

Description

Find arcs (maximal segment sequences between nodes)

Usage

find_arcs(x, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

quotient

Walk the quotient graph: duplicated shared boundaries collapse to a single undirected edge (first occurrence keeps its direction), so a boundary shared by two features becomes ONE arc rather than one per feature, and its interior vertices are degree-2 pass-throughs. This is the TopoJSON-style arc decomposition of a polygon layer. Default FALSE walks every segment.

Details

Arcs are maximal paths through degree-2 vertices. They start and end at nodes (degree != 2) or form closed loops through degree-2 vertices.

Value

A list of integer vectors, each containing .vx IDs forming an arc

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_arcs(merged)


Find closed cycles (rings) in segment graph

Description

Find closed cycles (rings) in segment graph

Usage

find_cycles(x)

Arguments

x

A wkpool (ideally after merge_coincident)

Details

When the pool carries path provenance (minted by establish_topology()), a cycle is a path whose segment chain closes: rings are recovered exactly, in input order and input winding, robust to segment reordering, and the result carries a path attribute mapping each cycle to its path id. Pools without provenance fall back to walking the segment graph in storage order, which relies on segments being consecutive within each ring.

Each cycle is a vector of vertex IDs in traversal order. The cycle is closed (first vertex connects back to last via a segment).

Value

A list of integer vectors, each containing .vx IDs forming a closed cycle

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_cycles(merged)


Find the faces of a segment graph

Description

Enumerate the faces of the graph formed by a pool's segments: the regions it encloses (street blocks between roads, parcels between boundaries), plus one outer face for each connected component.

Usage

find_faces(x)

Arguments

x

A wkpool (ideally after merge_coincident()).

Details

Segments are taken as undirected edges. A boundary carried by more than one feature (the same pair of vertex ids) counts once, keeping the first segment, and segments from a vertex to itself are dropped. Run merge_coincident() first so that segments meeting at the same coordinates share a vertex: faces are traced through shared vertex ids only, so lines that cross without a shared vertex (a bridge over a road) do not split each other, and their faces can overlap.

Each edge gives two half-edges, one per direction. At each vertex the outgoing half-edges are ordered counter-clockwise by angle, and a walk always takes the next edge clockwise from the one it arrived on, which keeps the face on its left. Every half-edge lies on exactly one face, so the result has two rows per edge. Bounded faces are counter-clockwise (positive area); the outer face of each connected component is clockwise (negative area), or zero for a component that encloses nothing (a tree).

An edge with the same face on both sides (.bridge) is a dead end, or a bridge joining two parts of the graph; its two half-edges both appear in that face's walk. Drop those rows to keep only edges that separate two faces.

Only x and y are used.

Value

A data frame with one row per half-edge, in walk order face by face:

See Also

find_neighbours() for adjacency between input features, find_cycles() for the rings of polygon input.

Examples

## a square with a cross inside: four blocks
x <- wk::as_wkb(c(
  "LINESTRING (0 0, 1 0, 2 0, 2 1, 2 2, 1 2, 0 2, 0 1, 0 0)",
  "LINESTRING (1 0, 1 1, 1 2)",
  "LINESTRING (0 1, 1 1, 2 1)"
))
pool <- merge_coincident(establish_topology(x))
f <- find_faces(pool)
## bounded faces and their areas
unique(f[f$.face_area > 0, c(".face", ".face_area")])
## which blocks share an edge
unique(f[f$.face_area > 0 & f$.face != f$.adjacent, c(".face", ".adjacent")])

Find internal boundaries (edges shared by exactly 2 features, opposite direction)

Description

Find internal boundaries (edges shared by exactly 2 features, opposite direction)

Usage

find_internal_boundaries(x)

Arguments

x

A wkpool after merge_coincident

Details

Internal boundaries are edges where one feature has segment (v0 -> v1) and another feature has (v1 -> v0), i.e. they share the edge but traverse it in opposite directions. This is the defining characteristic of a shared polygon boundary.

Value

A wkpool containing only internal boundary segments

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_internal_boundaries(merged)


Build adjacency from shared edges

Description

Build adjacency from shared edges

Usage

find_neighbours(x, type = c("edge", "vertex"))

Arguments

x

A wkpool after merge_coincident

type

"edge" for features sharing an edge, "vertex" for features sharing any vertex

Value

Data frame of feature pairs that are neighbours

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_neighbours(merged)


Find nodes (vertices where degree != 2)

Description

Find nodes (vertices where degree != 2)

Usage

find_nodes(x, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

quotient

Count in the quotient graph: duplicated shared boundaries (the same undirected vertex pair carried by more than one feature) count once. A vertex interior to a shared boundary has quotient degree 2 - the degree-2 invariant holds at this level - while true junctions (three or more distinct edges) stay nodes. Default FALSE counts every segment.

Details

Nodes are branch points (degree 3+) or endpoints (degree 1). Degree-2 vertices are pass-through points within an arc.

Value

Integer vector of .vx IDs that are nodes

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_nodes(merged)


Find shared edges between features

Description

Find shared edges between features

Usage

find_shared_edges(x)

Arguments

x

A wkpool (ideally after merge_coincident)

Details

After merging coincident vertices, edges that were duplicated across features (e.g., shared polygon boundaries) will reference the same vertex pair. This function finds them and reports which features share each edge.

Value

Data frame of edges shared by multiple features

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
find_shared_edges(merged)


Merge coincident vertices in a pool

Description

Merge coincident vertices in a pool

Usage

merge_coincident(x, tolerance = 0, period_x = NULL)

Arguments

x

A wkpool, or a wkpool_tri (see pool_triangulate())

tolerance

Numeric tolerance for coordinate matching. Default 0 means exact match only.

period_x

NULL (default) for no wrapping, or a single positive number: x is treated as periodic with this period when deciding which vertices coincide (for example 360 for longitude in degrees). See 'Periodic x' below.

Details

With tolerance = 0, only exactly identical coordinates are merged - identity is the double-precision bit pattern (grouped at C level via vctrs), not a formatted representation, so values that differ only beyond printable precision remain distinct. The first occurrence becomes the canonical vertex; coordinates are never moved.

With a nonzero tolerance, coordinates are snapped to a grid of cell size tolerance for matching (the canonical vertex keeps its original coordinates). Note this is a snap grid, not a distance guarantee: two vertices within tolerance of each other that straddle a grid-cell boundary do not merge.

When the pool carries z, vertices are keyed on all coordinate columns: equal x/y with different z remain distinct vertices.

This is where you discover shared boundaries between polygons, network connectivity, mesh topology, etc.

Value

A wkpool (or wkpool_tri) with shared vertices merged (fewer unique vertices)

Periodic x

With period_x set, vertices are keyed on x %% period_x (then on the tolerance snap grid, if any, wrapped again so that the grid cell at the period boundary is the same cell as the one at zero). This fuses the two copies of a seam, for example x = -180 and x = 180 for longitude, and with period_x = 360 data in a 0 to 360 convention fuses at 0 and 360 in the same way. Once fused, a seam is an ordinary internal boundary: find_shared_edges(), find_internal_boundaries() and the quotient argument of find_arcs() treat it like any other shared boundary.

The period is never inferred: wkpool carries the crs without interpreting it, so it cannot know that x is longitude. The decision to fuse is made here, explicitly.

Coordinates are still never moved: the canonical vertex keeps the x of its first occurrence (say -180), and segments from the other side of the seam now reference it. The topology is correct on the cylinder, but geometry emitted from the pool (for example by cycles_to_wkb()) has coordinate jumps of about one period across the seam. Consumers that understand wrapping (s2, great-circle densification) are fine; a planar consumer needs the seam split again downstream.

Segments are identified by their two vertices, so on the cylinder a segment cannot say which way round it goes. Two segments whose ends fuse to the same pair but which run opposite ways around become the same edge, for example the edge from -180 to 0 in one feature and from 0 to 180 in another. This needs a segment that spans at least half the period, so densify long segments before merging with period_x.

Only x is periodic. Poles (where all x coincide on the sphere), periodic y, and any detection from the crs are out of scope.

Feature provenance (.feature) is preserved - segments keep their original feature assignment even after vertex merging.

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
topology_report(pool)
merged <- merge_coincident(pool)
topology_report(merged)

# two hemispheres, each with its own copy of the antimeridian
g <- 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))"
))
pool <- establish_topology(g)
nrow(pool_vertices(merge_coincident(pool)))
fused <- merge_coincident(pool, period_x = 360)
nrow(pool_vertices(fused))
find_shared_edges(fused)


Construct a wkpool from validated components

Description

A low-level constructor for wkpool objects, for use by packages that build pools directly (for example after refining or transforming an existing pool). Inputs are checked against the wkpool invariants: every segment endpoint must be a vertex id present in the pool.

Usage

new_wkpool(
  vertices,
  vx0,
  vx1,
  feature = NULL,
  path = NULL,
  paths = NULL,
  crs = NULL,
  geodesic = FALSE
)

Arguments

vertices

A data.frame with columns .vx (integer vertex ids), x, y, and optionally z.

vx0, vx1

Integer vectors of segment start/end vertex ids, each value present in vertices$.vx.

feature

Optional integer vector of feature ids, one per segment.

path

Optional integer vector of path ids, one per segment. A path is a maximal run of segments minted from one input ring or linestring; it is the provenance that lets cycles, ring roles and feature structure be recovered exactly.

paths

Optional data.frame describing the paths: columns .path, .feature, .part, .ring (as captured from wk::wk_coords() identifiers by establish_topology()).

crs

A CRS object (commonly an authority string such as "EPSG:4326"), carried but never interpreted, per wk's CRS propagation model. Use NULL for none, or wk::wk_crs_inherit().

geodesic

TRUE if segments should be interpreted as geodesics when coordinates are spherical, FALSE otherwise, NA to inherit.

Value

A wkpool object.

Examples

v <- data.frame(.vx = 1:3, x = c(0, 1, 1), y = c(0, 0, 1))
new_wkpool(v, vx0 = c(1L, 2L), vx1 = c(2L, 3L), crs = "EPSG:4326")


Construct a triangle pool

Description

A low-level constructor for wkpool_tri objects: a vector of triangles whose corners are vertex ids into a shared vertex pool, the same pool structure a wkpool uses for segments.

Usage

new_wkpool_tri(
  vertices,
  vx0,
  vx1,
  vx2,
  feature = NULL,
  part = NULL,
  paths = NULL,
  crs = NULL,
  geodesic = FALSE
)

Arguments

vertices

A data.frame with columns .vx (integer vertex ids), x, y, and optionally z.

vx0, vx1, vx2

Integer vectors of triangle corner vertex ids, each value present in vertices$.vx.

feature

Optional integer vector of feature ids, one per triangle.

part

Optional integer vector of part ids, one per triangle (the polygon within a multipolygon feature, as identified by wk::wk_coords()).

paths

Optional data.frame describing the input paths (see pool_paths()), carried from the segment pool.

crs

A CRS object (commonly an authority string such as "EPSG:4326"), carried but never interpreted, per wk's CRS propagation model. Use NULL for none, or wk::wk_crs_inherit().

geodesic

TRUE if segments should be interpreted as geodesics when coordinates are spherical, FALSE otherwise, NA to inherit.

Details

The wkpool_tri class is experimental: how a triangle records the polygon part it came from (currently a .part field) may change in a later release.

Value

A wkpool_tri object.

Examples

v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
new_wkpool_tri(v, vx0 = c(1L, 1L), vx1 = c(2L, 3L), vx2 = c(3L, 4L))


Plot a wkpool object

Description

Draws segments coloured by feature membership.

Usage

## S3 method for class 'wkpool'
plot(x, col = NULL, add = FALSE, ...)

Arguments

x

A wkpool object.

col

Colour(s) for segments. If NULL (default), segments are coloured by feature using a built-in palette.

add

Add to the current plot?

...

Further arguments passed to plot.default() (ignored when add = TRUE).

Value

Invisibly returns x.

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
plot(pool)


Plot a triangle pool

Description

Draws every triangle with one call to graphics::polygon(), indexing the vertex pool directly (triangles separated by NA). This avoids building geometry: on 40,000 triangles it draws in a fraction of a second, where casting to wk polygons and plotting those takes over a minute.

Usage

## S3 method for class 'wkpool_tri'
plot(x, col = NULL, border = "black", add = FALSE, xlab = "x", ylab = "y", ...)

Arguments

x

A wkpool_tri.

col

Fill colour(s), recycled over triangles. If NULL (default), triangles are coloured by feature using the same palette as plot.wkpool().

border

Border colour(s) for triangle edges, NA for none.

add

If TRUE, draw on the current plot.

xlab, ylab

Axis labels when add = FALSE.

...

Further arguments passed to plot.default() when add = FALSE.

Value

Invisibly returns x.

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0), (0.2 0.3, 0.2 0.5, 0.4 0.5, 0.2 0.3))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
if (requireNamespace("decido", quietly = TRUE)) {
  tri <- pool_triangulate(establish_topology(x))
  plot(tri)
  plot(tri, col = "grey", border = NA)
}


Combine wkpool objects

Description

Combine wkpool objects

Usage

pool_combine(...)

Arguments

...

wkpool objects to combine

Value

A single wkpool with merged pools and remapped segments

Examples

x <- wk::as_wkb("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))")
y <- wk::as_wkb("POLYGON ((2 0, 3 0, 3 1, 2 1, 2 0))")
pool_a <- establish_topology(x)
pool_b <- establish_topology(y)
pool_combine(pool_a, pool_b)


Compact a pool by removing unreferenced vertices

Description

Compact a pool by removing unreferenced vertices

Usage

pool_compact(x)

Arguments

x

A wkpool

Value

A wkpool with only referenced vertices, .vx remapped

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
compact <- pool_compact(merged)
nrow(pool_vertices(compact))


Get hole points for constrained triangulation

Description

pool_holes() and hole_points() are the same function: pool_holes() is the name that matches the other ⁠pool_*()⁠ accessors, and hole_points() is kept for existing code.

Usage

pool_holes(x, convention = c("sf", "ogc"))

hole_points(x, convention = c("sf", "ogc"))

Arguments

x

A wkpool (ideally after merge_coincident)

convention

Which winding convention to use when the pool has no path provenance: "sf" (default) or "ogc"

Details

For use with RTriangle::triangulate(). Each row is a point inside a hole, which tells the triangulator to exclude that region.

The point is found on a horizontal line across the hole: the middle of the widest stretch of that line that starts at the hole's boundary and crosses no segment of the pool. It is inside the hole even when the hole is not convex, where the centroid of the ring's vertices can fall outside it (and a triangulator would then erase the polygon around the hole instead), and it is clear of any island in the hole.

A hole that is exactly filled by another polygon in the pool (an enclave in a coverage, such as a lake island that is its own feature) is not a hole of the pool and is not returned.

When the pool carries path provenance, holes are identified structurally (non-first rings of their part) and convention is not consulted.

Value

A matrix of hole points, one point inside each hole cycle, or NULL if no holes

Examples

polygons_with_holes <- wk::as_wkb(c(
  paste0(
    "MULTIPOLYGON (((0 0, 0 1, 0.75 1, 1 0.8, 0.5 0.7, ",
    "0.8 0.6, 0.69 0, 0 0), (0.2 0.2, 0.5 0.2, ",
    "0.5 0.4, 0.3 0.6, 0.2 0.4, 0.2 0.2)))"),
  "MULTIPOLYGON (((0.69 0, 0.8 0.6, 1.1 0.63, 1.23 0.3, 0.69 0)))"
))

x <- establish_topology(polygons_with_holes)
merged <- merge_coincident(x)
pool_holes(merged)
if (requireNamespace("RTriangle", quietly = TRUE)) {
  pslg <- as_pslg(merged)
  holes <- pool_holes(merged)
  tri <- RTriangle::triangulate(
    RTriangle::pslg(P = pslg$P, S = pslg$S, H = holes)
  )
}


Access the triangles of a triangle pool

Description

Access the triangles of a triangle pool

Usage

pool_triangles(x)

tri_segments(x)

## S3 method for class 'wkpool_tri'
wk_handle(handleable, handler, ...)

Arguments

x

A wkpool_tri.

handleable

A wkpool_tri.

handler

A wk handler.

...

Passed on.

Details

A wkpool_tri is wk-handleable: it presents as one POLYGON per triangle (the handled vector has the same length as the triangle vector), with the pool's crs and geodesic flag attached.

Value

Examples

v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
tri <- new_wkpool_tri(v, vx0 = c(1L, 1L), vx1 = c(2L, 3L), vx2 = c(3L, 4L))
pool_triangles(tri)
tri_segments(tri)


Triangulate the polygons in a pool

Description

Triangulate each polygon of a wkpool() (built by establish_topology()) and return the triangles as a wkpool_tri on the same vertex pool.

Usage

pool_triangulate(x, engine = c("decido"), ...)

Arguments

x

A wkpool with path provenance (from establish_topology()).

engine

Triangulation engine, currently only "decido".

...

Unused.

Details

The wkpool_tri class is experimental: how a triangle records the polygon part it came from (currently a .part field) may change in a later release.

The "decido" engine is ear cutting (decido::earcut()), which never creates vertices: every triangle corner is an existing vertex of the pool, so the vertex table is passed through unchanged. Each polygon (each part of a multipolygon) is triangulated separately, with its first ring as the boundary and later rings as holes, using the path provenance recorded by establish_topology(). Paths that are not closed rings (linestrings) are ignored.

The pool can be triangulated before or after merge_coincident(). On a raw pool each ring's closing coordinate is its own vertex; it is dropped from the ring and never used by a triangle. Merging the triangle pool later with merge_coincident() gives adjacent features shared triangle corners.

Triangles are counter-clockwise.

For constrained Delaunay triangulation, with Steiner points added for quality or area, pass as_pslg() to RTriangle; see vignette("triangulation", package = "wkpool").

Value

A wkpool_tri.

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0), (0.2 0.2, 0.2 0.4, 0.4 0.4, 0.2 0.2))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
if (requireNamespace("decido", quietly = TRUE)) {
  tri <- pool_triangulate(pool)
  tri
  pool_triangles(tri)
  wk::as_wkt(tri)
}


Reverse a cycle's winding direction

Description

Reverse a cycle's winding direction

Usage

reverse_cycle(cycle)

Arguments

cycle

Integer vector of .vx IDs forming a closed cycle

Details

Flips the traversal direction of a cycle without changing coordinates. Useful for converting between winding conventions.

Value

The same vertices in reversed order (opposite winding)

Examples

x <- wk::as_wkb("POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))")
pool <- establish_topology(x)
merged <- merge_coincident(pool)
cycles <- find_cycles(merged)
reverse_cycle(cycles[[1]])


Convert wkpool segments to WKT

Description

Convert wkpool segments to WKT

Usage

segments_to_wkt(x, type = c("multilinestring", "linestring", "point"))

segments_to_wkb(x, type = c("multilinestring", "linestring", "point"), ...)

Arguments

x

A wkpool

type

Output type: "linestring" (segments as paths), "multilinestring" (all segments), or "point" (vertices only)

...

Passed to wk::as_wkb()

Details

Geometry is assembled natively via wk::wk_linestring() and wk::wk_collection() (WKB first, WKT derived from it): coordinates are emitted at full double precision, z is carried when the pool has it, and the pool's crs and geodesic flag are attached to the output.

Value

A wk_wkt vector

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
segments_to_wkt(pool)
segments_to_wkt(pool, type = "linestring")


Report topology diagnostics

Description

Report topology diagnostics

Usage

topology_report(x, tolerance = 1e-08, period_x = NULL)

Arguments

x

A wkpool

tolerance

Tolerance for "near miss" detection

period_x

NULL, or the period of x, as in merge_coincident(); duplicates and near misses are then counted with x wrapped.

Value

List of diagnostic information

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
topology_report(pool)


Triangles as an Arrow array

Description

Write a triangle pool as an Arrow array, built with nanoarrow, in the layout of the experimental geoarrow.triangles type: each triangle is three indices into one vertex dictionary (a struct of x and y) that every triangle shares, so a vertex used by many triangles is stored once and a shared boundary is a shared index.

Usage

tri_as_arrow(x, group = NULL, layout = c("feature", "triangle"))

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

layout

"feature" (one row per group) or "triangle" (one row per triangle; group is ignored).

Details

With layout = "feature" (the default) each row is one group (a polygonal feature) and its value is the list of the group's triangles: ⁠List<FixedSizeList<Dictionary<int32, Coordinate>>[3]>⁠. The list offsets are then the feature-to-triangle ranges, so an engine that evaluates ⁠ST_*⁠ per row needs no grouping column. A triangle in several groups is written in each of their rows (three more indices, no new vertices). With layout = "triangle" each row is one triangle (⁠FixedSizeList<Dictionary<int32, Coordinate>>[3]⁠), in pool order, the storage of the mesh itself.

Vertices are numbered by first appearance in the written triangles, and vertices no triangle uses are not written. The extension metadata holds "edges": "planar" and the pool's crs (as a string) when it has one. The geoarrow.triangles type is a draft and not part of GeoArrow; the layout may change.

Value

A nanoarrow_array.

See Also

tri_from_arrow() to read it back.

Examples

if (requireNamespace("nanoarrow", quietly = TRUE)) {
  v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
  tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                        vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
  a <- tri_as_arrow(tri)
  a$length
  back <- tri_from_arrow(a)
  tri_measures(back$mesh, back$group)
}


Boundary edges of groups of triangles

Description

The edges between a group and what is not in it, as a segment pool on the triangles' vertex pool. This is ST_Boundary() of the polygons the groups cover, with shared boundaries on shared vertices.

Usage

tri_boundary(x, group = NULL, once = FALSE)

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

once

Keep an edge shared by two groups only once?

Details

Each edge is directed with its group on the left, so outer boundaries run counter-clockwise and holes clockwise. With once = TRUE an edge between two groups is kept for the smaller group id only, so every line is drawn once (see find_arcs() to merge the edges into arcs).

Value

A wkpool of segments with the group as its feature.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
tri_boundary(tri)
## the middle edge once
length(tri_boundary(tri, once = TRUE))


Clip triangles by a rectangle

Description

Keep the parts of the triangles inside a rectangle, as triangles again: ST_ClipByBox2D() that returns a mesh.

Usage

tri_clip_rect(x, rect)

Arguments

x

A wkpool_tri.

rect

The rectangle: a wk::rct() or c(xmin, ymin, xmax, ymax).

Details

Triangles inside the rectangle are kept as they are, triangles outside are dropped, and each triangle that crosses a side is cut to a convex polygon and fanned back into triangles. New vertices where edges cross the sides are added to the vertex pool, and a point where a shared edge crosses a side is computed the same way from both of its triangles, so neighbouring pieces share it exactly. Slivers of zero area on a side are dropped.

Value

A wkpool_tri with the input vertices plus the new ones (origin column "clip" for new vertices when the pool has an origin column; use pool_compact() to drop unused vertices), keeping the feature and part of each source triangle. The source triangle row of each output triangle is in attribute "source".

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
clipped <- tri_clip_rect(tri, c(0.5, 0.25, 1.5, 0.75))
tri_measures(clipped)


Convex hulls of groups of triangles

Description

ST_ConvexHull() of the polygons the groups cover, from the triangles' vertices.

Usage

tri_convex_hull(x, group = NULL)

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

Value

A wk::wkb() vector of POLYGON, one per group id from 1 to the largest (⁠POLYGON EMPTY⁠ for a group with fewer than three distinct points), with the pool's crs. Rings are counter-clockwise.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
wk::as_wkt(tri_convex_hull(tri, rep(1L, 4)))


Dissolve triangles into polygons by group

Description

Merge the triangles of a triangle pool into one MULTIPOLYGON per group, along shared triangle edges. With the default group, the triangles of each feature are dissolved back into that feature's polygons.

Usage

tri_dissolve(x, group = NULL, ...)

Arguments

x

A wkpool_tri.

group

Integer group id per triangle (1-based, NA to leave a triangle out). The default is the triangles' feature, or one group when the pool has no feature.

...

Unused.

Details

group is one integer per triangle: a dense, 1-based group id, with NA for a triangle that belongs to no group (it is left out, and its edges become boundary). This is the set_id of a labelled mesh, so a mesh labelled by the covering input features (an overlay) dissolves into its pieces with tri_dissolve(x, set_id), while the table from set to features is kept by the caller. Element k of the result is group k; a group id with no triangles gives ⁠MULTIPOLYGON EMPTY⁠.

Triangles must be counter-clockwise and form a triangulation (no overlaps), with adjacent triangles sharing vertex ids: run merge_coincident() first on a pool whose triangles do not already share vertices. Triangles are joined only across an edge whose two triangles share both of its vertex ids, so triangles that touch at a vertex or along part of an edge stay separate.

Rings follow the edges of the triangles, so pieces that touch share vertices exactly. Outer rings are counter-clockwise and holes clockwise. A group has one polygon for each edge-connected part, and a boundary that passes through a vertex twice (a hole touching its outer ring, for example) is split there, so every ring is simple and rings meet only at points. Only x and y are used.

Value

A wk::wkb() vector of MULTIPOLYGON, one per group id from 1 to the largest in group, with the pool's crs.

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0), (0.2 0.3, 0.2 0.5, 0.4 0.5, 0.2 0.3))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
if (requireNamespace("decido", quietly = TRUE)) {
  tri <- merge_coincident(pool_triangulate(establish_topology(x)))
  ## back to the input polygons
  wk::as_wkt(tri_dissolve(tri))
  ## everything as one polygon, with the hole kept
  wk::as_wkt(tri_dissolve(tri, rep(1L, length(tri))))
}


Read triangles from an Arrow array

Description

Read an array written by tri_as_arrow() (or anything with the same storage: one shared dictionary of x, y coordinates indexed by fixed-size lists of three, optionally inside a list per feature) back into a triangle pool and its groups.

Usage

tri_from_arrow(x)

Arguments

x

A nanoarrow_array, or anything nanoarrow::as_nanoarrow_array() accepts (such as an Arrow Array).

Details

A triangle that appears in several rows (a triangle in several features) becomes one triangle of the pool, in several groups.

Value

A list with mesh, a wkpool_tri (with the feature of each triangle when every triangle is in one row), and group, a data frame of triangle (row of mesh) and group (row of the array), or NULL for the one-row-per-triangle layout.

Examples

if (requireNamespace("nanoarrow", quietly = TRUE)) {
  v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
  tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                        vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
  a <- tri_as_arrow(tri)
  a$length
  back <- tri_from_arrow(a)
  tri_measures(back$mesh, back$group)
}


Locate points in a triangle pool

Description

The triangle that holds each point: point in polygon (ST_Intersects() or ST_Contains() of a point) answered by point location on the mesh.

Usage

tri_locate(x, at)

Arguments

x

A wkpool_tri.

at

The points: any geometry wk::wk_handle() understands (its vertices are used, as wk::wk_coords() gives them), a two-column matrix, or a data frame or list with x and y.

Details

Triangles are bucketed on a uniform grid over the extent of the mesh, and each candidate is tested with an exact orientation sign, so a point on an edge or a vertex is decided the same way for every triangle that holds it, and goes to the lowest triangle row among them. A point inside no triangle, or with a missing coordinate, is NA. Triangles may be either orientation; a degenerate triangle (zero area) holds no point.

The feature of the polygon each point falls in is pool_feature(x)[tri_locate(x, at)], and the group of any grouping (as in tri_measures()) is found the same way.

Value

An integer vector with one triangle row of x per point, NA where no triangle holds it.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
pts <- wk::xy(c(0.75, 0.25, 1.5, 3), c(0.25, 0.75, 0.5, 0.5))
i <- tri_locate(tri, pts)
i
## the feature each point falls in
pool_feature(tri)[i]


Measures of groups of triangles

Description

Area, perimeter, centroid, a point inside, and extent of each group of triangles, computed from the triangles without forming polygons. These are what ST_Area(), ST_Perimeter(), ST_Centroid(), ST_PointOnSurface() and ST_Envelope() return for the polygons the groups cover.

Usage

tri_measures(x, group = NULL)

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

Details

The area is the sum of triangle areas and the centroid their area-weighted mean. The perimeter is the length of the edges whose other side is not in the group. The point inside is the centroid of the group's largest triangle, so it is inside the group by construction. Triangles must be counter-clockwise (a clockwise triangle counts negative area).

Value

A data frame with one row per group id from 1 to the largest, and columns group, area, perimeter, centroid_x, centroid_y, point_x, point_y, xmin, ymin, xmax, ymax. A group with no triangles has zero area and perimeter and NA elsewhere.

See Also

tri_dissolve() for the polygons themselves.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
tri_measures(tri)
## one group over both squares
tri_measures(tri, rep(1L, 4))


Neighbouring triangles

Description

The edge table of a triangle pool: for each triangle, the triangle on the other side of each of its three edges.

Usage

tri_neighbours(x)

Arguments

x

A wkpool_tri.

Details

Two triangles are neighbours across an edge when both hold its two vertex ids, in opposite order (as counter-clockwise triangles that share an edge do). An edge on the outside of the mesh, or one used by more than two triangles, has no neighbour. Run merge_coincident() first on a pool whose triangles do not already share vertex ids.

Value

An integer matrix with one row per triangle and three columns: column k is the triangle across the edge from corner k to corner k + 1 (corner 3 to corner 1 for the third), NA where there is none.

Examples

v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
tri <- new_wkpool_tri(v, vx0 = c(1L, 1L), vx1 = c(2L, 3L), vx2 = c(3L, 4L))
tri_neighbours(tri)


Overlay two layers in one mesh

Description

Put the features of two layers into one triangulation in which every place they meet is a shared vertex or edge, so that relations between them can be read from the mesh alone (see tri_overlay_relate()).

Usage

tri_overlay(x, y = NULL, x_group = NULL, y_group = NULL)

Arguments

x, y

Layers, as above. y may be NULL to put one layer alone into a mesh (lines or points have no mesh of their own).

x_group, y_group

Groups for a polygon layer (as group in tri_measures()); ignored for lines and points.

Details

A layer is one of:

The boundary edges of every polygon group and every line segment become constraints of one constrained Delaunay triangulation of all the layers' vertices and points (cdtr::cdt_triangulate()). Where constraints cross, the crossing point is added as a vertex (computed in floating point, so a relation that hinges on a crossing point is exact for the overlay rather than for the inputs). Each triangle of the overlay then belongs to the polygon groups that hold its centroid in the source mesh, and each line is followed along the overlay's fixed edges. The centroid is that of the largest triangle among those joined to it without crossing a constraint (they all lie in the same groups), so that slivers along a constraint are labelled from a triangle well inside.

Value

A wkpool_overlay: a list with

See Also

tri_overlay_relate()

Examples

if (requireNamespace("cdtr", quietly = TRUE)) {
  ## a unit square as two triangles, and a line across it
  v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
  sq <- new_wkpool_tri(v, vx0 = c(1, 1), vx1 = c(2, 3), vx2 = c(3, 4))
  ln <- wk::wkt(c("LINESTRING (-1 0.5, 2 0.5)", "LINESTRING (2 2, 3 3)"))
  ov <- tri_overlay(sq, ln)
  ov$groups
  tri_overlay_relate(ov)
}


Relations between the layers of an overlay

Description

The DE-9IM matrix (as ST_Relate() returns it) between features of the two layers of a tri_overlay(), or between features of its one layer, read from the overlay mesh's triangles, edges and vertices.

Usage

tri_overlay_relate(x, pairs = NULL)

Arguments

x

A wkpool_overlay from tri_overlay().

pairs

NULL for every pair of features (one from each layer, or two of the one layer) whose closures share a vertex, the pairs that are not disjoint; or a two-column matrix or data frame of feature ids, the first in layer x and the second in layer y (or both in x for a single layer).

Details

Every point of the plane is in one open triangle, open edge or vertex of the mesh, or outside it, and each of those is in the interior, boundary or exterior of a feature. For polygons the classes are those of tri_relate(). A line's interior is its edges and the vertices inside it, its boundary the vertices where an odd number of its edges end (the mod-2 rule that GEOS uses by default). A point set's interior is its vertices and it has no boundary. Each entry is the largest dimension of a cell in both classes.

Value

A data frame with columns x and y (feature ids in their layers) and relate (the nine-character DE-9IM string, interior, boundary and exterior of the first by those of the second).

Examples

if (requireNamespace("cdtr", quietly = TRUE)) {
  ## a unit square as two triangles, and a line across it
  v <- data.frame(.vx = 1:4, x = c(0, 1, 1, 0), y = c(0, 0, 1, 1))
  sq <- new_wkpool_tri(v, vx0 = c(1, 1), vx1 = c(2, 3), vx2 = c(3, 4))
  ln <- wk::wkt(c("LINESTRING (-1 0.5, 2 0.5)", "LINESTRING (2 2, 3 3)"))
  ov <- tri_overlay(sq, ln)
  ov$groups
  tri_overlay_relate(ov)
}


Prepare a triangle pool for repeated questions

Description

Compute once, and keep with the pool, what the ⁠tri_*()⁠ functions otherwise derive on every call: the triangles as rows of the vertex table, the edge table (tri_neighbours()), the membership of triangles in groups, and the boundary rings of each group that tri_dissolve() and tri_structure() read. This is the mesh counterpart of a prepared geometry in GEOS.

Usage

tri_prepare(x, group = NULL, rings = TRUE)

tri_is_prepared(x)

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

rings

Also compute the boundary rings of each group? Only for a group given per triangle (not a table of overlapping groups).

Details

The cache is an attribute of the returned pool. It is used only while the pool's vertices and triangles are unchanged (it is checked on every use) and only for the group it was prepared with; any other group is computed as usual. Subsetting or combining pools drops it.

Value

x, with the cache attached.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
p <- tri_prepare(tri)
tri_is_prepared(p)
tri_measures(p)
tri_structure(p)


Relations between groups of triangles

Description

The DE-9IM matrix (as ST_Relate() returns it) between pairs of groups of one triangle mesh, computed from shared triangles, edges and vertices alone, without reading coordinates.

Usage

tri_relate(x, group = NULL, pairs = NULL)

Arguments

x

A wkpool_tri.

group

Groups of triangles. Either one integer per triangle (a dense, 1-based group id, NA to leave a triangle out), or a data frame with columns triangle (row in x) and group, for groups that overlap (a triangle in several groups, as in an overlay). The default is the triangles' feature, or one group when the pool has no feature.

pairs

NULL for every pair of groups that share a vertex (all pairs that are not disjoint), or a two-column matrix or data frame of group ids.

Details

Every point of the plane lies in exactly one open triangle, open edge or vertex of the mesh, or outside it, and each of those lies wholly in the interior, boundary or exterior of a group. A triangle is interior when it is in the group. An edge is interior when the triangles on both sides are, boundary when one is (outside the mesh is never in a group). A vertex is interior when every triangle around it is in the group and it is not on the outside of the mesh, exterior when none is, and boundary otherwise. Each matrix entry is the largest dimension of a mesh element in both classes: "2" for a triangle, "1" for an edge, "0" for a vertex, "F" for none.

The answer is exact for the mesh as given. It equals the relation of the polygons the groups cover when the mesh was built so that every place two inputs meet is a shared vertex, as a constrained triangulation that resolves crossings does. Pairs of groups that share no vertex are disjoint, "FF2FF1212", and are not listed when pairs is NULL.

Value

A data frame with columns a, b (group ids) and relate (the nine-character DE-9IM string, interior, boundary, exterior of a by those of b).

Examples

## a 2 x 1 strip of unit squares and a group covering both
v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3))
g <- data.frame(triangle = c(1, 2, 3, 4, 1, 2, 3, 4),
                group = c(1, 1, 2, 2, 3, 3, 3, 3))
tri_relate(tri, g)


Parts and holes of groups of triangles

Description

The number of polygons (parts) and holes of each group, as ST_NumGeometries() and ST_NumInteriorRings() (summed over parts) give them for the dissolved groups. These need the boundary rings, so they are a read on a pool from tri_prepare() and a dissolve otherwise.

Usage

tri_structure(x, group = NULL)

Arguments

x

A wkpool_tri.

group

Integer group id per triangle (1-based, NA to leave a triangle out). The default is the triangles' feature, or one group when the pool has no feature.

Value

A data frame with one row per group id from 1 to the largest and columns group, n_parts, n_holes and n_rings.

Examples

v <- data.frame(.vx = 1:6, x = c(0, 1, 1, 0, 2, 2), y = c(0, 0, 1, 1, 0, 1))
tri <- new_wkpool_tri(v, vx0 = c(1, 1, 2, 2), vx1 = c(2, 3, 5, 6),
                      vx2 = c(3, 4, 6, 3), feature = c(1, 1, 2, 2))
p <- tri_prepare(tri)
tri_is_prepared(p)
tri_measures(p)
tri_structure(p)


Combine many wkpool vectors into one vector

Description

This is non-functional, wkpool does not currently support vec_c().

Usage

## S3 method for class 'wkpool'
vec_c(..., .ptype = NULL)

Arguments

...

Vectors to coerce.

.ptype

If NULL, the default, the output type is determined by computing the common type across all elements of ....

Alternatively, you can supply .ptype to give the output known type. If getOption("vctrs.no_guessing") is TRUE you must supply this value: this is a convenient way to make production code demand fixed types.

Details

Attempts to combine wkpool vectors with vec_c will suggest using [pool_combine()' instead.

Value

nothing, used for a message side-effect (see Details)

See Also

pool_combine()


Calculate vertex degree (number of segments touching each vertex)

Description

Calculate vertex degree (number of segments touching each vertex)

Usage

vertex_degree(x, quotient = FALSE)

Arguments

x

A wkpool (ideally after merge_coincident)

quotient

Count in the quotient graph: duplicated shared boundaries (the same undirected vertex pair carried by more than one feature) count once. A vertex interior to a shared boundary has quotient degree 2 - the degree-2 invariant holds at this level - while true junctions (three or more distinct edges) stay nodes. Default FALSE counts every segment.

Value

Named integer vector: names are .vx, values are degree

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
merged <- merge_coincident(pool)
vertex_degree(merged)


Handle wkpool objects with wk handlers

Description

A wkpool is wk-handleable: it presents as one LINESTRING per segment (so the handled vector has the same length as the pool vector), with the pool's crs and geodesic flag attached. This means the wk ecosystem's generic conversions work directly on a pool: wk::as_wkb(), wk::as_wkt(), wk::wk_coords(), geos::as_geos_geometry(), plotting, and anything else built on wk::wk_handle().

Usage

## S3 method for class 'wkpool'
wk_handle(handleable, handler, ...)

Arguments

handleable

A wkpool object.

handler

A wk handler.

...

Passed on.

Details

Vertices are emitted at full double precision, indexed directly from the pool (no text round trip). If the pool carries z, coordinates are emitted as XYZ.

Arcs and cycles remain explicit conversions (arcs_to_wkt(), cycles_to_wkt() and friends): the handled form is deliberately the segment vector itself.

Value

The result of the handler.

Examples

x <- wk::wkt(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  crs = "EPSG:4326"
)
pool <- establish_topology(x)
wk::as_wkt(pool)
wk::wk_coords(pool)
wk::wk_crs(wk::as_wkb(pool))


Create a wkpool from a vertex table and a segment table

Description

The user-level constructor: give a vertex table and a segment table (as returned by pool_vertices() and pool_segments()) and get a wkpool back. It is a thin wrapper around new_wkpool(), which checks that every segment endpoint is a vertex id present in the pool.

Usage

wkpool(vertices, segments, paths = NULL, crs = NULL, geodesic = FALSE)

Arguments

vertices

A data.frame with columns .vx (integer vertex ids), x, y, and optionally z.

segments

A data.frame with integer columns .vx0 and .vx1 (vertex ids), and optionally .feature and .path.

paths

Optional data.frame describing the paths: columns .path, .feature, .part, .ring (as captured from wk::wk_coords() identifiers by establish_topology()).

crs

A CRS object (commonly an authority string such as "EPSG:4326"), carried but never interpreted, per wk's CRS propagation model. Use NULL for none, or wk::wk_crs_inherit().

geodesic

TRUE if segments should be interpreted as geodesics when coordinates are spherical, FALSE otherwise, NA to inherit.

Value

A wkpool object.

See Also

new_wkpool() for the low-level constructor, establish_topology() to build a pool from wk geometry.

Examples

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)
pool <- wkpool(v, s)
pool

# round trip through the accessors
wkpool(pool_vertices(pool), pool_segments(pool))


Access components of a wkpool object

Description

Extract the vertex pool, segment table, or feature vector from a wkpool.

Usage

pool_vertices(x)

pool_segments(x)

pool_feature(x)

pool_path(x)

pool_paths(x)

Arguments

x

A wkpool object.

Value

Examples

x <- wk::as_wkb(c(
  "POLYGON ((0 0, 1 0, 1 1, 0 1, 0 0))",
  "POLYGON ((1 0, 2 0, 2 1, 1 1, 1 0))"
))
pool <- establish_topology(x)
pool_vertices(pool)
pool_segments(pool)
pool_feature(pool)


CRS and geodesic handling for wkpool

Description

A wkpool participates in wk's CRS propagation model: the CRS is an opaque object carried in an attribute, never interpreted, and checked for equality when pools are combined. Likewise the geodesic flag records whether segments should be interpreted as geodesics when coordinates are spherical. Both are captured from the input by establish_topology(), survive subsetting, merging and compaction, and are restored onto geometry produced by segments_to_wkt(), arcs_to_wkt(), cycles_to_wkt() and their WKB counterparts.

Usage

## S3 method for class 'wkpool'
wk_crs(x)

## S3 method for class 'wkpool'
wk_set_crs(x, crs)

## S3 method for class 'wkpool'
wk_is_geodesic(x)

## S3 method for class 'wkpool'
wk_set_geodesic(x, geodesic)

Arguments

x

A wkpool object.

crs

A CRS object (commonly an authority string such as "EPSG:4326"), or NULL.

geodesic

TRUE, FALSE, or NA (inherit).

Value

Examples

x <- wk::wkt("LINESTRING (0 0, 1 1)", crs = "EPSG:4326")
pool <- establish_topology(x)
wk::wk_crs(pool)
wk::wk_crs(wk::wk_set_crs(pool, "EPSG:3031"))