найти все перестановки непересекающихся многоугольников в R (объекты sp или sf) - PullRequest
Новая
       31

найти все перестановки непересекающихся многоугольников в R (объекты sp или sf)

0 голосов
/ 28 октября 2018

У меня есть пространственный объект (скажем, Multipolygon в sf или SpatialPolygons в sp), и я хочу найти все возможные варианты не перекрывающихся объектов.Вот некоторые диаграммы, которые иллюстрируют то, что я после.Допустим, у меня есть следующие многоугольники. 

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)

enter image description here

Я выполняю процедуру, которая создала бы следующие 3 объекта, графики которых выглядели бы так:

а.a

b.enter image description here

c.enter image description here

В идеале подпрограмма также учитывает порог пересечения многоугольников.

Я думаю, что любая рутина, которую я мог бы написать сам, заняла бы непомерно много времени даже для объектов среднего размера (скажем, 150 полигонов, дающих множество возможных комбинаций).Я надеялся, что кто-то уже решил эту проблему.

1 Ответ

0 голосов
/ 29 октября 2018 
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 найти все полные подграфы во входном графе, соблюдая ограничения по размеру, указанные в min и maxarguments.

max_cliques находит все максимальные клики во входном графе.Максимальная клика, если она не может быть расширена до большей клики.Самые большие клики всегда максимальны, но максимальная клика не обязательно самая большая.

В этом случае клики - это наборы многоугольников, в которых ни один из многоугольников не перекрывается ни с одним из остальных.

Кроме того, чтобы применить это к 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
...