Find the shortest path between start and end points within a polygon

Usage

cnt_path(skeleton, start_point, end_point)

Arguments

skeleton: an output from cnt_skeleton() function
start_point: one or more starting points. It should be of the same class as the skeleton parameter
end_point: one ending point of the same class as skeleton and start_point parameters.

Value

a list of sf, sfc, SpatVector or geos_geometry class objects of a LINESTRING geometry

Details

The function connects start and end points with weighted shortest paths on an undirected skeleton graph using igraph::shortest_paths(). The skeleton of a closed polygon provides the potential routes.

It is important to note that multiple starting points are permissible, but there can only be one ending point. Should there be two or more ending points, the algorithm will return an error.

Neither starting nor ending points are required to be located on the edges of a polygon (i.e., snapped to the boundary); they can be positioned wherever possible inside the polygon.

By default, the algorithm identifies the closest nodes of the polygon's skeleton to the starting and ending points and then connects them using the shortest path possible along the skeleton. Therefore, if more precise placement of start and end points is necessary, consider executing cnt_skeleton() with keep = 1. In doing so, the resulting skeleton may be more detailed, increasing the likelihood that the starting and ending points are already situated on the skeleton paths.

For exact boundary terminals, pass the same boundary points to cnt_skeleton() as anchors. Those anchors become degree-one graph nodes, so cnt_path() returns zero endpoint distance from the supplied points rather than nearest-node snaps.

Every start point's nearest skeleton node must be connected to the end point's nearest node. Using anchors in cnt_skeleton() ensures that terminal nodes exist, but it does not make a multi-component skeleton globally connected. If any requested route is empty, cnt_path() stops without returning partial paths.

Examples

library(sf)
#> Linking to GEOS 3.12.1, GDAL 3.8.4, PROJ 9.4.0; sf_use_s2() is TRUE
library(geos)
# Load Polygon and points data
polygon <-
  sf::st_read(
    system.file("extdata/example.gpkg", package = "centerline"),
    layer = "polygon",
    quiet = TRUE
  ) |>
  geos::as_geos_geometry()

points <-
  sf::st_read(
    system.file("extdata/example.gpkg", package = "centerline"),
    layer = "polygon_points",
    quiet = TRUE
  ) |>
  geos::as_geos_geometry()

# Find polygon's skeleton
pol_skeleton <- cnt_skeleton(polygon)

# Connect points (nearest-node snapping)
pol_path <-
  cnt_path(
    skeleton = pol_skeleton,
    start_point = points[2],
    end_point = points[1]
  )

# Exact boundary terminals via anchors
boundary <- geos::geos_boundary(polygon)
is_boundary <- geos::geos_equals(
  geos::geos_intersection(boundary, points),
  points
)
anchors <- points[is_boundary]
anchored_skeleton <- cnt_skeleton(polygon, keep = 1, anchors = anchors)
anchored_path <- cnt_path(anchored_skeleton, anchors[1], anchors[2])

# Plot
plot(polygon)
plot(pol_skeleton, col = "blue", add = TRUE)
plot(points[1:2], col = "red", add = TRUE)
plot(pol_path, lwd = 3, add = TRUE)