找到 R 中非重叠多边形的所有排列（sp 或 sf 对象）

Question

我有一个空间对象（比如 sf 中的 Multipolygon 或 sp 中的 SpatialPolygons），我想找到非空间对象的所有可能排列重叠的特征。这里有一些图表说明了我所追求的。假设我有以下多边形。

library(sf)

# points
a <- st_as_sf(data.frame(lon = c(1,2,3.5,3,6), lat = c(0,1,0,1.5,-3)), coords = c('lon', 'lat'))

# circles
b <- st_buffer(a, 1)

# colors
cols = c('grey', 'red', 'green', 'yellow', 'blue')
cols = adjustcolor(cols, alpha.f = .5)

# plot
plot(b, col = cols)

我正在执行一个例程，该例程将创建以下 3 个对象，其绘图如下所示：

一个。

b。

c。

理想情况下，例程还允许在多边形的交点上设置阈值。

我认为即使是中等大小的对象（例如，150 个多边形，产生许多可能的组合），我自己编写的任何例程都会花费太长的时间。我希望有人已经解决了这个问题。

Answer 1

M <- st_overlaps(b, sparse = FALSE) * 1
(M <- 1 - M)
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    1    0    1    1    1
# [2,]    0    1    0    0    1
# [3,]    1    0    1    0    1
# [4,]    1    0    0    1    1
# [5,]    1    1    1    1    1
colnames(M) <- c('grey', 'red', 'green', 'yellow', 'blue')

library(igraph)
A <- graph_from_adjacency_matrix(M)
max_cliques(A)
# [[1]]
# + 2/5 vertices, named, from dae1f9f:
# [1] red  blue
#
# [[2]]
# + 3/5 vertices, named, from dae1f9f:
# [1] grey   blue   yellow
#
# [[3]]
# + 3/5 vertices, named, from dae1f9f:
# [1] grey  blue  green
cliques(A)
# ... 
# Omitted, 13 cliques in total

首先，我们使用 st_overlaps 来获得一种邻接矩阵，M，其中如果两个多边形在您的数据中重叠，则它们在此图中是相邻的。但实际上我们将需要 1 - M，其中两个多边形在这个新图中是相邻的，如果它们不重叠的话。这很有用，因为您正在寻找的内容对应于此图中的（最大）集团：

cliques find all complete subgraphs in the input graph, obeying the size limitations given in the min and max arguments.

max_cliques finds all maximal cliques in the input graph. A clique in maximal if it cannot be extended to a larger clique. The largest cliques are always maximal, but a maximal clique is not neccessarily the largest.

在这种情况下，团是多边形的集合，其中 none 的多边形与其余任何多边形重叠。

另外，对于sp个对象，只需要计算出对应的M即可。我相信 over 对此有所帮助。

奖金

至于增加阈值的可能性，我们只需要重新计算M。

aux <- function(x) if (length(x) == 1) x else 0
M <- matrix(1, nrow(a), nrow(a))
for(i in 1:nrow(a))
  for(j in 1:nrow(a))
    M[i, j] <- aux(st_area(st_intersection(b[i, 1], b[j, 1])))
diag(M) <- 0

然后，例如，如果我们仅在相交面积大于 0.2 时才将两个多边形计算为相交，我们运行

M <- 1 * (M > 0.2) # Getting threshold-overlaps
M <- 1 - M # The needed adjacency matrix

找到 R 中非重叠多边形的所有排列（sp 或 sf 对象）

find all permutations of non-overlapping polygons in R (sp or sf objects)

r

sp

sf