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

以下に例を示します。すべてが単一の関数にラップされます。最適化のために少し分割することをお勧めします。

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 2

パッケージを使用しますspatstat。この種のことを行うための組み込み関数があります。