Ближайшая пара по любому из огромного количества точек

Нам дан огромный набор точек в 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)

Есть идеи?


r points euclidean-distance
person Ali    schedule 21.05.2013    source источник
comment
Аналогичный вопрос: title="как рассчитать евклидово расстояние и сохранить только сводки для больших данных fra">stackoverflow.com/questions/16474179/   -  person flodel    schedule 21.05.2013

Ответы (3)


arrow_upward
4
arrow_downward

Традиционный подход заключается в предварительной обработке данных и помещении их в структуру данных, часто в виде дерева 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] )
person Vincent Zoonekynd    schedule 21.05.2013
comment
nnclust больше не доступен в библиотеке cran. Последняя доступная версия в архиве от 2010 года. - person Adrian Tompkins; 02.05.2018

arrow_upward
1
arrow_downward

Вот пример; все завернуто в одну функцию. Возможно, вы захотите немного разделить его для оптимизации.

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

Конечно, он не очень хорошо справляется с галстуками.

person MrGumble    schedule 21.05.2013
comment
Спасибо, а будет ли это работать на огромном наборе баллов, я имею в виду например 1М баллов? - person Ali; 21.05.2013
comment
Да, но эффективно? Не уверен. Он будет работать за O (n ^ 2), так как для каждой точки необходимо пересчитать все расстояния, поэтому, если вам нужно оптимальное решение, обойти это невозможно. С точки зрения пространства, что обычно является более насущной проблемой, он использует только O (n). Если вам нужно ускорить процесс, вы можете рассмотреть параллельную обработку, в которой эта функция легко может быть переписана, или эвристический алгоритм поиска, который сильно зависит от ваших данных. - person MrGumble; 21.05.2013
comment
Вы не используете тот факт, что ваша функция dist уже векторизована... Замените sapply(indices, dist, i=i, USE.NAMES=TRUE) на dist(i, indices), и вы увидите огромное улучшение. Вы также можете ускорить работу, используя более эффективные индексы, например, indices <- 1:nrow(foo) не следует вычислять внутри цикла. И замените sapply на vapply. - person flodel; 21.05.2013

arrow_upward
0
arrow_downward

Используйте пакет spatstat . У него есть встроенные функции для таких вещей.

person Carl Witthoft    schedule 21.05.2013