从同一个shapefile连接多个多边形

Question

我想要连接从美国州的样本中绘制出来的所有州之间的线，就像在这个帖子中所做的那样。 我成功地在一些多边形之间画了一些线，但是我没有成功地画出所有多边形最后都连接在一起的线。我该如何强制一个已经连接的多边形去寻找与自己尚未连接的多边形建立连接？

这是我的代码：

library(dplyr)
library(sf)
library(ggplot2)
library(nngeo)

nc <- st_read(system.file("shape/nc.shp", package="sf"))
set.seed(2806)
nc_sample=dplyr::sample_n(nc,10)
ggplot() + geom_sf(data = nc_sample)

co=st_connect(nc_sample[1,], nc_sample %>% slice(st_distance(nc_sample[1,],nc_sample) %>%
                                                   units::drop_units() %>% 
                                                   as.data.frame() %>%
                                                   mutate_if(is.numeric, ~na_if(., 0)) %>%
                                                   rowwise() %>% which.min()))
all_connexion=st_sf(co)

for(i in 2:length(nc_sample$AREA)){
  co=st_connect(nc_sample[i,], nc_sample %>% slice(st_distance(nc_sample[i,],nc_sample) %>%
                                       units::drop_units() %>% 
                                       as.data.frame() %>%
                                       mutate_if(is.numeric, ~na_if(., 0)) %>%
                                        rowwise() %>% which.min()))
  all_connexion = rbind(all_connexion,co)
}

ggplot() + 
  geom_sf(data = all_connexion) +
  geom_sf(data = nc_sample) 

我得到的连接是：

- Camillionnaire

Answer 1

使用nngeo，您可以遍历多边形，每次从尚未连接的集合中找到最近的邻居。这基本上是旅行推销员问题的最近邻算法。还要注意nc数据集包含多个多边形，要连接每个单独的多边形，您需要首先使用st_cast(nc_sample, "POLYGON")之类的方法。

library(dplyr)
library(sf)
library(ggplot2)
library(nngeo)

nc <- st_read(system.file("shape/nc.shp", package="sf"))
set.seed(2806)

nc_sample=dplyr::sample_n(nc,10) %>% 
  # add index and next_hop columns
  mutate(id = row_number(),
         next_hop = NA_integer_)

# iterate though list of ploygons, 
# find the closest neighbour from set of polygons
# that are not yet linked

# starting polygon index:
idx <- 1
# mask for unlinked polygons:
nn_mask <- rep_len(TRUE, nrow(nc_sample))
nn_mask[idx] <- FALSE
while (any(nn_mask)) {
  # index of the nearest neighbour in masked dataset
  masked_idx <- st_nn(nc_sample[idx,], 
                      nc_sample[nn_mask,], 
                      k = 1, 
                      progress = FALSE)[[1]]
  # get / store matching id value 
  idx <- nc_sample$next_hop[idx] <- nc_sample[nn_mask,]$id[masked_idx]
  # exclude latest match from the set of available polygons
  nn_mask[idx] <- FALSE
} 

# resulting connections:
st_drop_geometry(nc_sample)[,c("id", "next_hop")]
#>    id next_hop
#> 1   1        6
#> 2   2        5
#> 3   3       NA
#> 4   4        2
#> 5   5        3
#> 6   6       10
#> 7   7        9
#> 8   8        7
#> 9   9        4
#> 10 10        8
connections <- st_connect(nc_sample, nc_sample, ids = nc_sample$next_hop)

ggplot(nc_sample) + 
  geom_sf() + 
  geom_sf_label(aes(label = id)) +
  geom_sf(data = connections)

^{创建于2023-06-29，使用reprex v2.0.2。}

在大多数情况下，您可能希望通过图形和更高级的TSP方法来解决此问题，因此可以查看igraph和TSP包。

- margusl