Given GIS data of polygons and two points, is there a way to find the minimum number of polygons you need to traverse to walk between the two points? Even an approximate approach would be fine for my purposes if the problem cannot always be solved exactly.
The actual application I am using this for uses tax parcels and pipelines, with the goal of finding minimum number of parcels I need to traverse to lay a pipeline between two points -- so thousands of polygons and thousands of pairs of points. But to provide an example here is some code in R using the sf package. I load North Carolina counties and put two points on it. The straight line path between the two points goes through 5 counties. But if you look at the map you can see there's a path that goes through only 4 counties. I want an approach to calculate that 4 in this case, and more generally.
# install.packages(c('sf','dplyr')) # if needed library(sf) library(dplyr) # use NC counties polygons polys <- read_sf(system.file("shape/nc.shp", package = "sf")) # make two points, goal is to find the minimum # of counties to get between them points <- data.frame(name=c('start','end'),LAT=c(34.623858,35.257017),LONG=c(-78.851954,-78.237195)) points <- st_as_sf(points, coords = c("LONG", "LAT"), crs = 4326) plot(polys$geometry) plot(points$geometry, add=TRUE,col='blue') plot(st_cast(summarize(points,name=first(name)),'LINESTRING'),add=TRUE,col='blue')