给定一个空间（六边形）网格，我怎样才能获得高阶邻居的样本？

Question

我想“细化”用 sf::st_make_grid 制作的网格并获得高阶邻居的子集。

一阶邻居至少共享一侧，二阶邻居与一阶邻居共享一侧，依此类推

这是一个例子：

require(sf)
require(ggplot2)

x = st_sfc(st_polygon(list(rbind(c(0,0), c(1,0), c(1,1), c(0,0)))))
g = st_make_grid(x, cellsize = .3, square = FALSE )
g = st_as_sf(g)
g$id = 1:nrow(g)

ggplot(g) + geom_sf() + geom_sf_text(aes(label = id))

二阶邻居的可能子集将是：

gs = g[g$id %in% c(3:5, 11:12, 18:20),]
ggplot(gs) + geom_sf() + geom_sf_text(aes(label = id))

但其他样本也是可能的，例如c(1,2,9,8,10,16,17)

我如何子集到任何更高阶的邻居？

Answer 1

我会尝试按以下方式解决您的问题。只有一个“免责声明”：我不确定以下方法是否 100% 正确并且在所有情况下都适用。此外，正如前面评论中所讨论的，以下解决方案不是唯一的，您可以根据起点和算法背后的选择得到不同的“细化”。

加载包

# packages
library(sf)
library(igraph)
library(ggplot2)

生成数据并绘制所有多边形

x = st_sfc(st_polygon(list(rbind(c(0,0), c(1,0), c(1,1), c(0, 1), c(0,0)))))
g = st_make_grid(x, cellsize = .3, square = FALSE)
g = st_as_sf(g)
g$id = 1:nrow(g)

# plot all polygons
ggplot(g) + 
  geom_sf() + 
  geom_sf_text(aes(label = id))

提取单元格背后的图形结构，并绘制出来

my_graph <- graph_from_adj_list(st_touches(g))
plot(my_graph)

你可以注意到它和以前差不多，没有任何地理结构。如果您将相同的代码应用于“现实世界的问题”，您可能需要使用不同的空间谓词并调整 sf 对象的精度，因为坐标中可能存在舍入误差。

现在，从第一个单元格开始计算一阶邻居列表（应排除）

id_to_be_ignored <- ego(my_graph, order = 1, nodes = 1)[[1]]

以及一阶和二阶邻居列表

all_second_order_neighbours <- ego(my_graph, order = 2, nodes = 1)[[1]]

最终样本应该包括这两个id之间的差异

final_sample <- difference(all_second_order_neighbours, id_to_be_ignored)

现在我需要对二阶单元重复这个操作

i <- 1
while (TRUE) {
  # We need to end the loop sooner or later
  if (i > length(final_sample)) break
  
  # Extract the id of the node
  id <- final_sample[[i]]
  
  # Determine and exclude first order neighbours considering the id-th node
  ego1_id <- ego(my_graph, order = 1, nodes = id)[[1]]
  id_to_be_ignored <- union(id_to_be_ignored, difference(ego1_id, V(my_graph)[id]))
  
  # Determine and add second order neighbours considering the id-th node
  ego2_id <- difference(
    ego(my_graph, order = 2, nodes = id)[[1]], 
    ego1_id
  )
  final_sample <- difference(union(final_sample, ego2_id), id_to_be_ignored)
  
  # Increment i
  i <- i + 1
}

结果是这样

ggplot(g[c(1, as.integer(final_sample)), ]) + 
  geom_sf() + 
  geom_sf_text(aes(label = id))

现在我重复 3 阶邻居

id_to_be_ignored <- ego(my_graph, order = 2, nodes = 1)[[1]]
all_third_order_neighbours <- ego(my_graph, order = 3, nodes = 1)[[1]]
final_sample <- difference(all_third_order_neighbours, id_to_be_ignored)
i <- 1
while (TRUE) {
  if (i > length(final_sample)) break
  
  id <- final_sample[[i]]
  
  ego2_id <- ego(my_graph, order = 2, nodes = id)[[1]]
  id_to_be_ignored <- union(id_to_be_ignored, difference(ego2_id, V(my_graph)[id]))
  
  ego3_id <- difference(
    ego(my_graph, order = 3, nodes = id)[[1]], 
    ego2_id
  )
  final_sample <- difference(union(final_sample, ego3_id), id_to_be_ignored)
  
  # Increment i
  i <- i + 1
}

同样，这是结果

ggplot(g[c(1, as.integer(final_sample)), ]) + 
  geom_sf() + 
  geom_sf_text(aes(label = id))

^{由 reprex package (v0.3.0)}

于 2021-01-28 创建

同样的代码也应该适用于不同的空间结构和街区顺序。

给定一个空间（六边形）网格，我怎样才能获得高阶邻居的样本？

Given a spatial (hexagonal) grid how can I obtain a sample of higher order neighbors?

r

geospatial

igraph

sf

spdep