Каков самый быстрый способ найти ближайшую точку к данной точке массива данных?
Например, у меня есть 3D-пространство, массив точек (координаты - (x, y, z)) и точка (xp, yp, zp). Мне нужно найти ближайшую точку к (xp, yp, zp).
Насколько я знаю, самый медленный способ сделать это - использовать линейный поиск. Есть ли лучшие решения?
Возможно добавление любых вспомогательных данных.
Вы можете организовать свои очки в октябре. Тогда вам нужно только выполнить поиск небольшого подмножества.
Смотрите: en.wikipedia.org/wiki/Octree
Это довольно простая структура данных, которую вы можете реализовать самостоятельно (что было бы ценным опытом обучения), или вы можете найти полезные библиотеки, чтобы вы начали.
Примечание. Первоначально я сказал Quadtree (что для 2D) случайно. Спасибо @marcog за исправление.
Если вы делаете запрос на ближайший соседний запрос, то линейный поиск действительно лучший, который вы можете получить. Это, конечно, предполагает, что данные не предварительно структурированы.
Однако, если вы собираетесь делать много запросов, есть несколько пространственно-разделяющих структур данных. Они берут некоторую предварительную обработку формируют структуру, но затем могут очень быстро отвечать на запросы ближайших соседей.
Поскольку вы имеете дело с пространством 3D, я рекомендую посмотреть octrees или KD-деревья. Kd-деревья более общие (они работают для произвольных размеров) и могут быть сделаны более эффективными, чем octrees, если вы реализуете подходящий алгоритм балансировки (например, медиана хорошо работает), но осцилляторы легче реализовать.
ANN - отличная библиотека, использующая эти структуры данных, но также позволяющая приблизительные запросы ближайших соседей, которые значительно быстрее, но имеют небольшой потому что они просто приближаются. Если вы не можете принять какую-либо ошибку, установите для параметра error значение 0.
Я предлагаю KD-Tree работать отлично. Также полезно для поиска ближайшего соседа.
Его мое понимание quadtree для 2d, но вы могли бы вычислить что-то для 3d thats очень похоже. Это ускорит ваш поиск, но для вычисления индекса потребуется гораздо больше времени, если он будет выполнен "на лету". Я бы предложил подсчитать индекс, а затем сохранить его. При каждом поиске вы выясняете все внешние квадроциклы, а затем прокладываете себе путь в поисках хитов... это будет напоминать апельсин. Скорость будет значительно возрастать по мере уменьшения размеров квадроцикла. Все имеет компромисс.
Если они не организованы в правильной структуре данных, единственным способом будет линейный поиск.
Я бы использовал KD-дерево для этого в O (log (n)) времени, предполагая, что точки распределены случайным образом или у вас есть способ сохранить сбалансированное дерево.
http://en.wikipedia.org/wiki/Kd-tree
Деревья KD отлично подходят для такого рода пространственных запросов и даже позволяют вам найти ближайших k-соседей в точке запроса.
Мне нужно было сделать это довольно тяжело для поиска ближайших соседей в среде реального времени и использовать лучший алгоритм как с точки зрения простоты, так и скорости.
Возьмите все свои очки и поместите копию в d-списки, где d - размерность пространства. В вашем случае 3. Сортируйте эти три списка в соответствии с их размером. Это требует времени d (nlog (n)). И это для структуры данных.
Мы сохраняем эти правильно отсортированные списки в каждом измерении для всех рассматриваемых пунктов. Фокус в том, что по определению расстояние в одном направлении должно быть меньше или равно эвклидовому расстоянию. Поэтому, если расстояние в одном направлении больше нашего текущего ближайшего расстояния ближайшей известной точки, тогда эта точка не может быть ближе, и, что более важно, все точки в этом направлении не могут быть больше. Как только это верно для направлений 2 * d, мы по определению имеем ближайшую точку.
Для каждого конкретного элемента мы можем использовать binarysearch в отсортированных списках, чтобы найти ближайшую позицию, где требуемая точка может быть в двух разных измерениях. Математически мы знаем, что если расстояние в + x -x + y -y (другие размеры легко добавить), направления превышают наименьшее известное евклидово расстояние до точки, эта точка должна превышать расстояние, а так как это отсортированный массив, по определению, когда мы превосходим это расстояние в этом направлении, мы знаем, что мы можем прервать это направление, потому что в этом направлении не может быть лучшего ответа. Но, расширяясь в этих четырех направлениях, мы можем уменьшить наше значение m, так как оно равно евклидову расстоянию ближайшей точки, которую мы нашли.
Поэтому нам нужны только отсортированные списки для каждой оси, отсортированной по этой оси. Это довольно просто.
Затем, чтобы запросить список:
У нас есть отсортированные списки и нужно найти точку, которую мы ищем в каждом направлении в списке. Мы выполняем двоичный поиск, чтобы сохранить лог времени (n). Тогда у нас есть лучшая текущая дистанция (возможно бесконечность), а затем мы движемся в каждом направлении, которое нам доступно. Когда мы находим новые точки, мы обновляем ближайшую точку до сих пор. Хитрость заключается в том, что мы уходим, как только расстояние в этом направлении больше, чем наша текущая известная ближайшая точка.
Итак, если у нас есть точка с известным ближайшим расстоянием 13, то мы можем прервать проверку в направлениях + x, -x, + y, -y, как только расстояние в этом направлении превышает наше самое близкое известное расстояние, Поскольку, если он далее + x, чем наш текущий m, все остальные значения + x могут быть математически доказаны как более далеко. По мере того как мы становимся лучше и лучше ближайшими, количество пространства, которое нам нужно искать, становится все меньше и меньше.
Если у вас заканчиваются точки в направлении, это направление закончено. Если расстояние до точки вдоль только одного измерения линии само больше, чем m, это направление завершено.
Решение m, когда все направления доказали, что имеют только точки, которые должны быть дальше, чем наш лучший момент.
- Поскольку мы постепенно уменьшаем m, расстояние в каждом измерении, необходимое как целое, быстро падает, хотя, как и все алгоритмы, он уменьшается быстрее в более высоких измерениях. Но если расстояние в одном измерении больше, чем лучшее, что у нас есть до сих пор, обязательно должно быть так, что все остальные точки в этом направлении не могут быть лучше.
Сложность времени кажется наравне с лучшими. Но в простоте структур данных этот алгоритм явно выигрывает. Там много других свойств, которые делают этот алгоритм серьезным соперником. Когда вы обновляете материал, вы можете прибегать к спискам с действительно хорошей производительностью, потому что вы очень часто сортируете уже отсортированные списки или почти отсортированные списки. Вы повторяете массивы. В реальных условиях реальной производительности большинство хранилищ сосают. Вообще из-за кэширования и того, как выкладывается память, мы должны быть агностиками в отношении таких вещей, но это имеет большое значение. Данные, находящиеся рядом с вашими текущими актуальными данными, намного быстрее для доступа. Если мы уже знаем, где точка, которую мы будем искать в списках, мы можем решить ее еще быстрее (поскольку нам не нужно было бы искать ее с бинарным поиском). И другие разрешенные трюки, повторно использующие информацию из предыдущей итерации здесь и там. И дополнительные размеры в основном бесплатны (за исключением того, что тогда значение не сходится быстрее, а потому, что в области есть более случайные распределенные точки, чем круг того же радиуса).
public class EuclideanNeighborSearch2D {
public static final int INVALID = -1;
static final Comparator<Point> xsort = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return Double.compare(o1.x, o2.x);
}
};
static final Comparator<Point> ysort = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return Double.compare(o1.y, o2.y);
}
};
ArrayList<Point> xaxis = new ArrayList<>();
ArrayList<Point> yaxis = new ArrayList<>();
boolean dirtySortX = false;
boolean dirtySortY = false;
public Point findNearest(float x, float y, float minDistance, float maxDistance) {
Point find = new Point(x,y);
sortXAxisList();
sortYAxisList();
double findingDistanceMaxSq = maxDistance * maxDistance;
double findingDistanceMinSq = minDistance * minDistance;
Point findingIndex = null;
int posx = Collections.binarySearch(xaxis, find, xsort);
int posy = Collections.binarySearch(yaxis, find, ysort);
if (posx < 0) posx = ~posx;
if (posy < 0) posy = ~posy;
int mask = 0b1111;
Point v;
double vx, vy;
int o;
int itr = 0;
while (mask != 0) {
if ((mask & (1 << (itr & 3))) == 0) {
itr++;
continue; //if that direction is no longer used.
}
switch (itr & 3) {
default:
case 0: //+x
o = posx + (itr++ >> 2);
if (o >= xaxis.size()) {
mask &= 0b1110;
continue;
}
v = xaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vx > findingDistanceMaxSq) {
mask &= 0b1110;
continue;
}
break;
case 1: //+y
o = posy + (itr++ >> 2);
if (o >= yaxis.size()) {
mask &= 0b1101;
continue;
}
v = yaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vy > findingDistanceMaxSq) {
mask &= 0b1101;
continue;
}
break;
case 2: //-x
o = posx + ~(itr++ >> 2);
if (o < 0) {
mask &= 0b1011;
continue;
}
v = xaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vx > findingDistanceMaxSq) {
mask &= 0b1011;
continue;
}
break;
case 3: //-y
o = posy + ~(itr++ >> 2);
if (o < 0) {
mask = mask & 0b0111;
continue;
}
v = yaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vy > findingDistanceMaxSq) {
mask = mask & 0b0111;
continue;
}
break;
}
double d = vx + vy;
if (d <= findingDistanceMinSq) continue;
if (d < findingDistanceMaxSq) {
findingDistanceMaxSq = d;
findingIndex = v;
}
}
return findingIndex;
}
private void sortXAxisList() {
if (!dirtySortX) return;
Collections.sort(xaxis, xsort);
dirtySortX = false;
}
private void sortYAxisList() {
if (!dirtySortY) return;
Collections.sort(yaxis,ysort);
dirtySortY = false;
}
/**
* Called if something should have invalidated the points for some reason.
* Such as being moved outside of this class or otherwise updated.
*/
public void update() {
dirtySortX = true;
dirtySortY = true;
}
/**
* Called to add a point to the sorted list without needing to resort the list.
* @param p Point to add.
*/
public final void add(Point p) {
sortXAxisList();
sortYAxisList();
int posx = Collections.binarySearch(xaxis, p, xsort);
int posy = Collections.binarySearch(yaxis, p, ysort);
if (posx < 0) posx = ~posx;
if (posy < 0) posy = ~posy;
xaxis.add(posx, p);
yaxis.add(posy, p);
}
/**
* Called to remove a point to the sorted list without needing to resort the list.
* @param p Point to add.
*/
public final void remove(Point p) {
sortXAxisList();
sortYAxisList();
int posx = Collections.binarySearch(xaxis, p, xsort);
int posy = Collections.binarySearch(yaxis, p, ysort);
if (posx < 0) posx = ~posx;
if (posy < 0) posy = ~posy;
xaxis.remove(posx);
yaxis.remove(posy);
}
}
Обновление: Что касается комментариев, то проблема k-точек. Вы заметите, что очень мало изменилось. Единственное, что имело место, заключалось в том, что точка v была бы меньше текущего m (findDistanceMaxSq), затем эта точка добавляется в кучу, а значение для m устанавливается равным эвклидовому расстоянию между позицией поиска и k-й элемент. Регулярную версию алгоритма можно рассматривать как случай, когда k = 1. Мы ищем один элемент, который нам нужен, и обновляем m до единственного (k = 1) элемента, когда v оказывается ближе.
Имейте в виду, что я только когда-либо делаю дистанционные сравнения в форме квадрата расстояния, так как мне только нужно знать, если оно дальше, и я не трачу часы на функции квадратного корня.
И я знаю, что существует идеальная структура данных для хранения k-элементов в кучке с ограниченным размером. Очевидно, что вставка массива для этого не является оптимальной. Но, кроме слишком большого java-зависимого apis, просто не было одного для этого конкретного класса, хотя, по-видимому, Google Guava делает его. Но вы вообще не заметите, что шансы на то, что ваши шансы скорее всего не так велики. Но это делает сложность времени для вставки в точки, хранящиеся в k-time. Есть также такие вещи, как кеширование расстояния от точки поиска для элементов.
Наконец, и, вероятно, наиболее настойчиво, проект, который я буду использовать для тестирования кода, находится в процессе перехода, поэтому мне не удалось проверить это. Но это, безусловно, показывает, как вы это делаете: вы сохраняете k лучших результатов до сих пор и делаете m равным расстоянию до ближайшей точки k. - Все остальное остается прежним.
Пример источника.
public static double distanceSq(double x0, double y0, double x1, double y1) {
double dx = x1 - x0;
double dy = y1 - y0;
dx *= dx;
dy *= dy;
return dx + dy;
}
public Collection<Point> findNearest(int k, final float x, final float y, float minDistance, float maxDistance) {
sortXAxisList();
sortYAxisList();
double findingDistanceMaxSq = maxDistance * maxDistance;
double findingDistanceMinSq = minDistance * minDistance;
ArrayList<Point> kpointsShouldBeHeap = new ArrayList<>(k);
Comparator<Point> euclideanCompare = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return Double.compare(distanceSq(x, y, o1.x, o1.y), distanceSq(x, y, o2.x, o2.y));
}
};
Point find = new Point(x, y);
int posx = Collections.binarySearch(xaxis, find, xsort);
int posy = Collections.binarySearch(yaxis, find, ysort);
if (posx < 0) posx = ~posx;
if (posy < 0) posy = ~posy;
int mask = 0b1111;
Point v;
double vx, vy;
int o;
int itr = 0;
while (mask != 0) {
if ((mask & (1 << (itr & 3))) == 0) {
itr++;
continue; //if that direction is no longer used.
}
switch (itr & 3) {
default:
case 0: //+x
o = posx + (itr++ >> 2);
if (o >= xaxis.size()) {
mask &= 0b1110;
continue;
}
v = xaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vx > findingDistanceMaxSq) {
mask &= 0b1110;
continue;
}
break;
case 1: //+y
o = posy + (itr++ >> 2);
if (o >= yaxis.size()) {
mask &= 0b1101;
continue;
}
v = yaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vy > findingDistanceMaxSq) {
mask &= 0b1101;
continue;
}
break;
case 2: //-x
o = posx + ~(itr++ >> 2);
if (o < 0) {
mask &= 0b1011;
continue;
}
v = xaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vx > findingDistanceMaxSq) {
mask &= 0b1011;
continue;
}
break;
case 3: //-y
o = posy + ~(itr++ >> 2);
if (o < 0) {
mask = mask & 0b0111;
continue;
}
v = yaxis.get(o);
vx = x - v.x;
vy = y - v.y;
vx *= vx;
vy *= vy;
if (vy > findingDistanceMaxSq) {
mask = mask & 0b0111;
continue;
}
break;
}
double d = vx + vy;
if (d <= findingDistanceMinSq) continue;
if (d < findingDistanceMaxSq) {
int insert = Collections.binarySearch(kpointsShouldBeHeap, v, euclideanCompare);
if (insert < 0) insert = ~insert;
kpointsShouldBeHeap.add(insert, v);
if (k < kpointsShouldBeHeap.size()) {
Point kthPoint = kpointsShouldBeHeap.get(k);
findingDistanceMaxSq = distanceSq(x, y, kthPoint.x, kthPoint.y);
}
}
}
//if (kpointsShouldBeHeap.size() > k) {
// kpointsShouldBeHeap.subList(0,k);
//}
return kpointsShouldBeHeap;
}
Самый быстрый способ сделать это, учитывая ТОЛЬКО поиск, - использовать voxels. При использовании карты точечного вокселя 1:1 время доступа является постоянным и очень быстрым, просто сдвиньте координаты, чтобы центрировать начало вашей точки в начале вокселя (если необходимо), а затем просто округлите позицию и получите доступ к массиву вокселей с помощью это значение. В некоторых случаях это хороший выбор. Как объяснялось передо мной, октемы лучше, когда карта 1:1 трудно получить (слишком много очков, слишком мало воксельных разрешений, слишком много свободного места).
проверьте это. Вы также можете проконсультироваться с главой CLRS. http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf