如何实现同一Shapefile中所有美国州样本多边形的完整连线？

我想参照Stack Overflow上的菊花链连接思路，将美国州样本中提取的所有多边形用细线连接起来。目前已实现部分多边形间的连线，但无法让所有多边形最终连通，请问如何让已连接的多边形与未连接的多边形建立连接？

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) 

你的问题根源在于：当前逻辑是让每个多边形单独连接自己的最近邻，这会形成多个独立的小连通块，而非单一整体连通的结构。要实现所有多边形连通的菊花链效果，需要维护一个动态扩展的已连通集合，每次从未连通的多边形中找到距离这个集合最近的个体，再将它与集合内最近的多边形连接，逐步把所有多边形纳入连通体系。

改进后的代码如下：

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)

# 初始化已连通多边形的索引和连线对象
connected_idx <- 1
all_connexion <- st_sf()

# 循环直到所有多边形都被连通
while(length(connected_idx) < nrow(nc_sample)) {
  # 拆分已连通和未连通的多边形子集
  connected_polys <- nc_sample[connected_idx, ]
  unconnected_polys <- nc_sample[-connected_idx, ]
  
  # 计算未连通多边形到已连通集合的距离矩阵
  dist_matrix <- st_distance(unconnected_polys, connected_polys) %>%
    units::drop_units()
  
  # 找到距离已连通集合最近的未连通多边形，以及对应的已连通多边形
  min_dist_per_unconnected <- apply(dist_matrix, 1, min)
  target_unconnected_idx <- which.min(min_dist_per_unconnected)
  target_connected_idx <- which.min(dist_matrix[target_unconnected_idx, ])
  
  # 获取要连接的两个多边形
  poly_to_add <- unconnected_polys[target_unconnected_idx, ]
  poly_in_set <- connected_polys[target_connected_idx, ]
  
  # 创建连线并合并到总连线中
  new_connection <- st_connect(poly_to_add, poly_in_set)
  all_connexion <- rbind(all_connexion, st_sf(new_connection))
  
  # 更新已连通集合的索引
  original_unconnected_pos <- which(!(1:nrow(nc_sample) %in% connected_idx))[target_unconnected_idx]
  connected_idx <- c(connected_idx, original_unconnected_pos)
}

# 绘制最终连通效果
ggplot() + 
  geom_sf(data = all_connexion, color = "red") +
  geom_sf(data = nc_sample)

• 核心逻辑是逐步扩展连通域：每次只纳入距离当前连通集合最近的未连通多边形，确保新加入的多边形必然与已有连通体系相连，最终形成单一连通链。
• 避免了原代码中“各连各的”导致的孤立块问题，确保所有多边形最终连通。

内容的提问来源于stack exchange，提问作者Camillionnaire