Find the LCP between two points on a Quadtree

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.

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

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.

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.

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.

See also

lcp_finder() creates the LCP finder object used as input to this function. find_lcps() calculates all LCPs whose cost-distance is less than some value. summarize_lcps() outputs a summary matrix of all LCPs that have been calculated so far.

Examples

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