如何在R中从网格坐标创建邻接矩阵？

Question

我是这个网站的新手。我想知道是否有人有将网格坐标列表（在下面的示例代码中显示为df）转换的经验。我编写了一个可以处理非常小数据集的函数，但随着数据集大小的增加，运行时间呈指数级增长（我认为800像素需要大约25小时）。这是由于嵌套的for循环造成的，但我不知道如何解决。

## Dummy Data
x <- c(1,1,2,2,2,3,3)
y <- c(3,4,2,3,4,1,2)
df <- as.data.frame(cbind(x,y))
df

## Here's what it looks like as an image
a <- c(NA,NA,1,1)
b <- c(NA,1,1,1)
c <- c(1,1,NA,NA)
image <- cbind(a,b,c)
f <- function(m) t(m)[,nrow(m):1]
image(f(image))

## Here's my adjacency matrix function that's slowwwwww
adjacency.coordinates <- function(x,y) {
  df <- as.data.frame(cbind(x,y))
  colnames(df) = c("V1","V2")
  df <- df[with(df,order(V1,V2)),]
  adj.mat <- diag(1,dim(df)[1])
  for (i in 1:dim(df)[1]) {
    for (j in 1:dim(df)[1]) {
      if((df[i,1]-df[j,1]==0)&(abs(df[i,2]-df[j,2])==1) | (df[i,2]-df[j,2]==0)&(abs(df[i,1]-df[j,1])==1)) {
        adj.mat[i,j] = 1
      }
    }
  }
  return(adj.mat)
}

## Here's the adjacency matrix
adjacency.coordinates(x,y)

有没有一种方法可以在几千像素的坐标系上很好地完成此操作？我已经尝试将其转换为SpatialGridDataFrame，但无法正确获取邻接矩阵。非常感谢您的时间。

- Logan

---

原帖作者显然想要图像中“开启”像素所构成的图的邻接矩阵（x和y是像素坐标；示例中有7个像素），如果两个像素相邻，则它们之间有一条边。这是二维网格的子图。（可以使用以下代码复制图像：im <- matrix(FALSE,5,5); im[cbind(x,y)] <- TRUE; image(im)。） - Vincent Zoonekynd

Answer 1

虽然我认为igraph可能是解决问题的方法，但我认为你可以更简单地做到这一点，如下所示：

result <- apply(df, 1, function(pt) 
  (pt["x"] == df$x &  abs(pt["y"] - df$y) == 1) |
  (abs(pt["x"] - df$x) == 1 &  pt["y"] == df$y)    
)
diag(result) <- 1

避免循环，获得相同的结果：

> identical(adjacency.coordinates(x,y),result)
[1] TRUE

- thelatemail

---

但是你得到的矩阵与从adjacency.coordinates(x,y)得到的期望输出不同... - Ben

@Ben - 我意识到了 - 它确实复制了op的“image”调用，并根据维基百科的定义生成了一个“邻接矩阵”。老实说，我对“adjacency.coordinates(x,y)”函数的结果代表什么感到困惑。 - thelatemail

大家好，非常感谢你们的回复。我的 adjacency.coordinates 是基于这样一个事实：当比较两组坐标时，如果 x 值之间的差为 0，y 值之间的差为 1 或反之，则这两组坐标是相邻的。可能这不是最好的解释。我真正想做的就是找出如何从一组坐标列表中获取邻接矩阵。现在遇到了困难... 再次感谢大家。 - Logan

非常棒，完全奏效了。将它与igraph的graph.adjacency()和clusters() 结合使用，让我可以将图像中的所有集群分开并单独进行分析。 - Logan

这个解决方案是检查网格中每个顶点的4个相邻顶点。有没有想过如何实现8-邻居的解决方案？ - Javier de la Rosa

顺便提一下，检查8邻域的条件应该是(abs(pt["x"] - df$x) <= 1 & abs(pt["y"] - df$y) <= 1)。 - Javier de la Rosa