如何用R计算多边形内所有点100米范围内的最短步行路线？

问题背景 #

你需要自动生成一条最短步行路线，确保目标多边形内所有点都处于路线的100米覆盖范围内，替代手动绘制的方式，针对给定的poly对象实现该需求。

可行性与实现方案 #

核心问题本质 #

这个需求属于**覆盖路径规划（Coverage Path Planning, CPP）**的变体，目标是找到满足覆盖约束的最短路径，在R中可以通过空间分析工具结合优化算法实现。

针对poly对象的具体步骤 #

首先需要注意：原始poly使用的是WGS84（EPSG:4326）经纬度坐标系，无法直接计算米制距离，必须先转换为投影坐标系（比如该区域对应的UTM 30N，EPSG:32630）。

步骤1：坐标系转换

# 转换为米制UTM投影
poly_utm <- st_transform(poly, crs = 32630)

步骤2：两种主流实现思路

思路1：栅格化+旅行商问题（TSP）求解

• 将多边形栅格化为200米分辨率的网格（确保路线经过栅格中心时，栅格内所有点都在100米覆盖范围内）
• 提取栅格中心，计算这些点的最短遍历路径（TSP问题），得到符合要求的最短路线

library(TSP)
library(stars)

# 栅格化多边形
grid <- st_rasterize(poly_utm, dx = 200, dy = 200)
# 提取多边形内的栅格中心
grid_centers <- st_as_sf(st_dimensions(grid)[[1]]$values, coords = c("x", "y"), crs = 32630) %>%
  filter(st_intersects(., poly_utm, sparse = FALSE))

# 构建距离矩阵并求解TSP
dist_matrix <- st_distance(grid_centers) %>% as.matrix()
tsp <- TSP(dist_matrix)
# 用concorde求解最优路径（需额外安装concorde求解器，启发式方法可选"nearest_insertion"）
tsp_solution <- solve_TSP(tsp, method = "concorde")
# 生成最终路线
route <- grid_centers[tsp_solution, ] %>% st_combine() %>% st_cast("LINESTRING")

思路2：中轴线提取+简化

• 计算多边形的中轴线（Medial Axis）：中轴线是多边形内到边界距离相等的点的集合，天然接近最短覆盖路径
• 对中轴线进行简化，确保所有区域在100米覆盖范围内

library(alphahull)

# 提取多边形边界坐标
poly_boundary <- st_cast(poly_utm, "LINESTRING") %>% st_coordinates()
# 计算中轴线
ma <- medialaxis(poly_boundary[,1:2])
# 转换为sf格式的线对象
ma_sf <- st_linestring(ma$medialaxis) %>% st_sfc(crs = 32630)
# 简化中轴线，调整容差控制简化程度（确保覆盖范围）
simplified_ma <- st_simplify(ma_sf, dTolerance = 50)

你的算法思路评估 #

你提出的「生成多条路线→筛选最短且覆盖性最好的路线」思路是可行的，但需要优化细节：

• 生成路线阶段：不能随机生成，应基于栅格中心、中轴线节点等有针对性的点集生成候选路径，否则效率极低
• 筛选标准：必须先确保路线满足「所有点都在100米范围内」的硬约束，再筛选最短路线；不能优先追求最短再考虑覆盖，否则可能出现不符合要求的结果

关键注意事项 #

• 必须使用米制投影坐标系，否则距离计算会出现误差
• TSP求解器的选择：concorde能给出最优解，但需要额外安装；若追求快速，可选用启发式方法
• 栅格分辨率需与100米覆盖范围匹配，避免出现覆盖盲区

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