Пометка соседних точек в матрице

Question

У меня есть матрицу 8x8:

1 1 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 1 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 1 

код для его создания:

examplemat <- matrix(c(1, 1, rep(0, 6), 1, rep(0, 9), 1, 1, rep(0, 17), 1, rep(0, 7), 1, rep(0, 5), 1, rep(0, 11), 1), 8, 8, byrow=T) 

Те, которые были извлечены как координаты:

onecoords <- which(examplemat == 1, arr.ind=T) 

     row col 
[1,] 1 1 
[2,] 2 1 
[3,] 1 2 
[4,] 3 3 
[5,] 3 4 
[6,] 7 4 
[7,] 5 6 
[8,] 6 6 
[9,] 8 8 

I нужен простой, векторный подход к кластеризации этих групп в группы смежных координат. (Для целей этой задачи я хотел бы добавить 4-позиционное смещение вверх/вниз/влево/вправо, но вам также может понадобиться опция 8-позиционной смежности, включая диагонали.)

В этом примере мы бы в конечном итоге с 5 кластеров клеток:

 row col clus 
[1,] 1 1 A 
[2,] 2 1 A 
[3,] 1 2 A 
[4,] 3 3 B 
[5,] 3 4 B 
[6,] 7 4 C 
[7,] 5 6 D 
[8,] 6 6 D 
[9,] 8 8 E 

4-позиционная проверка смежности довольно проста: sum(abs(onecoords[1,] - onecoords[2,])) == 1 Но я изо всех сил, чтобы решить, как эффективно векторизации это.

Answer 1

С благодарностью alexis_laz и Carl Witthoft за очень полезные комментарии, которые позволяют мне самим ответить на это.

Четырехходовой смежности

Для того, чтобы получить кластеры на основе 4-пути смежности, используют иерархическую кластеризацию с одной связью на Manhattan расстояние:

cbind(onecoords, clus = cutree(hclust(dist(onecoords, "manhattan"), "single"), h = 1)) 
     row col clus 
[1,] 1 1 1 
[2,] 2 1 1 
[3,] 1 2 1 
[4,] 3 3 2 
[5,] 3 4 2 
[6,] 7 4 3 
[7,] 5 6 4 
[8,] 6 6 4 
[9,] 8 8 5 

Восемь способов смежности

Для получения кластеров на основе 8-позиционной смежности (включая диагонали) используйте иерархическую кластеризацию с одной связью возраст на максимальное расстояние:

cbind(onecoords, clus = cutree(hclust(dist(onecoords, "maximum"), "single"), h = 1)) 

Разница между Манхэттеном и максимальные расстояния

В случае примера, эти оба дают те же результаты, но если удалить первую строку, например, вы увидите, что расстояние Манхэттена составляет 6 кластеров, а максимальное расстояние составляет 5 кластеров.

cbind(onecoords[2:9,], clus = cutree(hclust(dist(onecoords[2:9,], "manhattan"), "single"), h = 1)) 
    row col clus 
[1,] 2 1 1 
[2,] 1 2 2 
[3,] 3 3 3 
[4,] 3 4 3 
[5,] 7 4 4 
[6,] 5 6 5 
[7,] 6 6 5 
[8,] 8 8 6 
cbind(onecoords[2:9,], clus = cutree(hclust(dist(onecoords[2:9,], "maximum"), "single"), h = 1)) 
    row col clus 
[1,] 2 1 1 
[2,] 1 2 1 
[3,] 3 3 2 
[4,] 3 4 2 
[5,] 7 4 3 
[6,] 5 6 4 
[7,] 6 6 4 
[8,] 8 8 5