find_lcp: Find the LCP between two points on a `Quadtree`

Description

Finds the least-cost path (LCP) from the start point (the point used to create the LcpFinder) to another point, using a Quadtree as a resistance surface.

Usage

# S4 method for Quadtree
find_lcp(
  x,
  start_point,
  end_point,
  use_orig_points = TRUE,
  xlim = NULL,
  ylim = NULL,
  search_by_centroid = FALSE
)
# S4 method for LcpFinder
find_lcp(x, end_point, allow_same_cell_path = FALSE)

Value

Returns a five column matrix representing the LCP. It has the following columns:

x: x coordinate of this point (centroid of the cell)
y: y coordinate of this point (centroid of the cell)
cost_tot: the cumulative cost up to this point
dist_tot: the cumulative distance up to this point - note that this is not straight-line distance, but instead the distance along the path
cost_cell: the cost of the cell that contains this point
id: the ID of the cell that contains this point

If no path is possible between the two points, a zero-row matrix with the previously described columns is returned.

Arguments

x: a LcpFinder or a Quadtree
start_point: two-element numeric vector; the x and y coordinates of the starting point. Not used if x is a LcpFinder since the start point is determined when the LcpFinder is created (using lcp_finder()).
end_point: two-element numeric vector; the x and y coordinates of the destination point
use_orig_points: boolean; if TRUE (the default), the path is calculated between start_point and end_point. If FALSE, the path is calculated between the centroids of the cells the points fall in.
xlim: two-element numeric vector (xmin, xmax); passed to lcp_finder(); constrains the nodes included in the network to those whose x limits fall in the range specified in xlim. If NULL the x limits of x are used
ylim: same as xlim, but for y
search_by_centroid: boolean; passed to lcp_finder(); determines which cells are considered to be "in" the box specified by xlim and ylim. If FALSE (the default) any cell that overlaps with the box is included. If TRUE, a cell is only included if its centroid falls inside the box.
allow_same_cell_path: boolean; default is FALSE; if TRUE, allows paths to be found between two points that fall in the same cell. See 'Details' for more.

Details

See the vignette 'quadtree-lcp' for more details and examples (i.e. run vignette("quadtree-lcp", package = "quadtree"))

Using find_lcp(<Quadtree>) rather than find_lcp(<LcpFinder>) is simply a matter of convenience - when a Quadtree is passed to find_lcp(), it automatically creates an LcpFinder and then uses find_lcp(<LcpFinder>) to get the path between the two points. This is convenient if you only want a single LCP. However, if you want to find multiple LCPs from a single start point, it is better to first create the LcpFinder object using lcp_finder() and then use find_lcp(<LcpFinder>) for finding LCPs. This is because an LcpFinder object saves state, so subsequent calls to find_lcp(<LcpFinder>) will run faster.

By default, if the end point falls in the same cell as the start point, the path will consist only of the point associated with the cell. When using find_lcp with a LcpFinder, setting allow_same_cell_path to TRUE allows for paths to be found within a single cell. In this case, if the start and end points fall in the same cell, the path will consist of two points - the point associated with the cell and end_point. If using find_lcp with a Quadtree, this will automatically be allowed if use_orig_points is TRUE.

Examples

Run this code

####### NOTE #######
# see the "quadtree-lcp" vignette for more details and examples:
# vignette("quadtree-lcp", package = "quadtree")
####################

library(quadtree)
habitat <- terra::rast(system.file("extdata", "habitat.tif", package="quadtree"))

# create a quadtree
qt <- quadtree(habitat, split_threshold = .1, adj_type = "expand")
plot(qt, crop = TRUE, na_col = NULL, border_lwd = .4)

# define our start and end points
start_pt <- c(6989, 34007)
end_pt <- c(33015, 38162)

# create the LCP finder object and find the LCP
lcpf <- lcp_finder(qt, start_pt)
path <- find_lcp(lcpf, end_pt)

# plot the LCP
plot(qt, crop = TRUE, na_col = NULL, border_col = "gray30", border_lwd = .4)
points(rbind(start_pt, end_pt), pch = 16, col = "red")
lines(path[, 1:2], col = "black")

# note that the above path can also be found as follows:
path <- find_lcp(qt, start_pt, end_pt)