Calculating FETE paths with maximum distance

[coconn41]

When using create_FETE_lcps(), is there a way to calculate least-cost-paths from all points to all other points within a certain specified distance? The Circuitscape toolbox for ArcGIS allows to truncate by a specified distance. In this way, it would no longer be "from everywhere to everywhere," but rather, from everywhere to everywhere within X distance. I could not find a specific argument that handles this.

Notably, the only surefire way to truncate based on distance is to calculate least-cost-paths FETE anyways, and then filter them after calculation. However, this creates unnecessary calculations thereby increasing the computation time.

Looking at the code for create_FETE_lcps(), it could feasibly incorporate testing the euclidean distance between location points and skipping if greater than your X distance. Such a code could appear in your foreach() loop here:

  lcp_network <- foreach::foreach(i = 1:nlocs, .errorhandling = "remove", .combine = "rbind", .packages = c("sf", "terra")) %dopar% {

#Test euclidean distance here, if greater than your max lcp distance, skip the lcp calculation

    lcp <- create_lcp(x = x,
                      origin = locations[i,, drop = FALSE],
                      destination = locations[-i,, drop = FALSE],
                      cost_distance = cost_distance)

    lcp$origin_ID <- i
    lcp$destination_ID <- (1:nlocs)[-i]

    return(lcp)
  }

I am open to making such an addition and can submit a fork request.

[josephlewis]

Hi @coconn41,

Thanks for raising this question.

My one concern with filtering by euclidean distance is that you're effectively eliminating potential connections that would be within a specific time/energy expenditure. This is normally what is of interest when conducting least-cost path analyses. But I understand the potential use-case.

As an alternative for the suggested code, it might be possible to do this check before the foreach, i.e. test the distance of each point and then filter before supplying the locations to the foreach loop. I'll look into this though.

If speed is of concern and you don't want the least-cost paths but distances it might be worth looking into the R package cppRouting, You can convert your leastcostpath conductanceMatrix via:

conductanceMatrix2 <- summary(conductanceMatrix$conductanceMatrix)
# cppRouting requires cost rather than conductance so we take the inverse of conductance
conductanceMatrix2$x <- 1 / conductanceMatrix2$x

  directed_graph <-makegraph(conductanceMatrix2,directed=TRUE)

  accum_vals <- get_distance_matrix(Graph=directed_graph, from=points, to=points, allcores=FALSE)

Hope that helps.

I'll do some thinking in the meantime.

Kind regards, Joe

[coconn41]

Hi @josephlewis, thanks for the quick reply!

I see the use of the cppRouting package for creating a distance network - this may prove useful to an analysis I plan to do later.

The use-case I'm thinking of is for between-patch animal movement where an animal has a maximum distance that they may travel between habitat patches (nodes). It will save computation time to remove the calculations of least-cost-paths between patches (nodes) further than this maximum distance. I understand that least-cost-paths calculated after filtering by a maximum euclidean distance may still be larger than the maximum distance, but those can be filtered post-analysis.

To build off of your idea, perhaps something like an st_buffer() and then st_intersects() prior to the loop to test which points are near other points?

[coconn41]

@josephlewis My thought is something like this:

We can create a buffer for all data points and create a list of which points are within a certain distance using a combination of st_buffer() and st_intersects():

library(sf)
library(tmap)
library(dplyr)

set.seed(1)
ex_data = data.frame(id = c(1:10),
                     latitude = runif(n = 10,
                                      min = 42,
                                      max = 43),
                     longitude = runif(n = 10,
                                       min = -78,
                                       max = -75)) %>%
  mutate(id = as.character(id)) %>%
  st_as_sf(coords=c('longitude','latitude')) %>%
  st_set_crs(4326)

buffer_ex_data = st_buffer(ex_data,dist=70000)

tm_shape(buffer_ex_data)+
  tm_polygons(alpha=.5) +
tm_shape(ex_data)+
  tm_dots(size=2.5,
          shape=1) +
tm_shape(ex_data) +
  tm_text(text = 'id',
          col = 'red')

near_list = st_intersects(x = buffer_ex_data,
                          y = ex_data)

near_list[[1]]
#> [1] 1 2 9

tm_shape(buffer_ex_data %>% filter(id=="1"))+
  tm_polygons(alpha=.5) +
  tm_shape(ex_data)+
  tm_dots(size=2.5,
          shape=1) +
  tm_shape(ex_data) +
  tm_text(text = 'id',
          col = 'red')

From there, we can alter the foreach loop to cycle through the list, rather than cycling through all points:

for(i in 1:length(near_list)){
  for(j in 1:length(near_list[[i]])){
    lcp <- create_lcp(x = x,
                      origin = locations[i,, drop = FALSE],
                      destination = locations[j,, drop = FALSE],
                      cost_distance = cost_distance)
  }
}

I'm not sure exactly how this would fit in to your code, but I can envision some sort of truncate = FALSE default argument, that could accept a numeric distance for the dist = argument in st_buffer(). Changing truncate = to a numeric would prompt the truncated loop above.

I'm not the best programmer, so this is just a rough idea. I'd like to hear your thoughts on this.

[josephlewis]

Hi @coconn41

Thanks for those. Alternatively the euclidean distance can be calculated from the origin to all destinations via _stdistance. Just trying to work out so the checks later on still return the correct values, e.g. telling you about duplicate points etc.

I should be able to work on this later in the month.

[coconn41]

@josephlewis Ah yes, I knew I was missing an obvious function to get distance. Thanks for your time - I'll keep an eye out for the updates!

[josephlewis]

Hi @coconn41,

I haven't forgotten about this! I've been thinking about this and I think I'll just recreate the _create_lcpnetwork function I had in the previous versions of leastcostpath rather than try to create another argument within create_FETE_lcp.

_create_lcpnetwork will allow you to specify which location connections will be calculated by supplying a matrix of indexes. That way, those within x distances can be specified as well as other configurations, e.g. top 3 nearest locations for each location.

I'll get working on that ASAP