r - 大量点中任意点的最近对

Question

我们在 2D 平面上得到了大量的点。我们需要为每个点找到集合中最近的点。例如假设初始集合如下：

 foo <- data.frame(x=c(1,2,4,4,10),y=c(1,2,4,4,10))

输出应该是这样的：

 ClosesPair(foo)
 2
 1
 4
 3
 3 # (could be 4 also)

任何想法？

Answer 1

传统的做法是对数据进行预处理，并将其放入数据结构中，通常是Kd 树，“最近点”查询速度非常快。

包中有一个实现nnclust。

library(nnclust)
foo <- cbind(x=c(1,2,4,4,10),y=c(1,2,4,4,10))
i <- nnfind(foo)$neighbour
plot(foo)
arrows( foo[,1], foo[,2], foo[i,1], foo[i,2] )

Answer 2

这是一个例子；全部包装成一个函数。您可能希望将其拆分一下以进行优化。

ClosesPair <- function(foo) {
  dist <- function(i, j) {
    sqrt((foo[i,1]-foo[j,1])**2 + (foo[i,2]-foo[j,2])**2)
  }

  foo <- as.matrix(foo)

  ClosestPoint <- function(i) {  
    indices <- 1:nrow(foo)
    indices <- indices[-i]

    distances <- sapply(indices, dist, i=i, USE.NAMES=TRUE)

    closest <- indices[which.min(distances)]
  }

  sapply(1:nrow(foo), ClosestPoint)
}
ClosesPair(foo)
# [1] 2 1 4 3 3

当然，它不能很好地处理关系。

Answer 3

使用包spatstat。它有内置函数来做这类事情。