Мне нужно было сделать это довольно интенсивно для поиска многих ближайших соседей в режиме реального времени и найти лучший алгоритм с точки зрения простоты и скорости.
Возьмите все свои очки и поставьте копиюв d списках, где d размерность пространства.В вашем случае 3. Сортируйте эти три списка по их размеру.Это стоит d (nlog (n)) времени.И это все для структуры данных.
Мы поддерживаем эти правильно отсортированные списки в каждом измерении для всех рассматриваемых точек.Хитрость в том, что по определению расстояние в одном направлении должно быть меньше или равно евклидову расстоянию.Таким образом, если расстояние в одном направлении больше нашего текущего ближайшего расстояния ближайшей известной точки, то эта точка не может быть ближе, и, что более важно, все точки в этом направлении не могут быть больше.Как только это верно для 2 * d направлений, которые у нас есть, мы по определению имеем ближайшую точку.
Для каждого конкретного элемента мы можем выполнить двоичный поиск в отсортированных списках, чтобы найти ближайшую позицию, где требуемая точка может быть вдва разных измерения.Математически мы знаем, что если расстояние в направлениях + x -x + y -y (другие измерения легко добавить) превышает наименьшее известное евклидово расстояние до точки, то эта точка должна превышать расстояние, и, поскольку это отсортированный массив,по определению, когда мы превышаем это расстояние в этом направлении, мы знаем, что можем прервать это направление, потому что лучшего ответа в этом направлении не может быть.Но, расширяясь в этих четырех направлениях, мы можем уменьшить наше значение m, поскольку оно равно евклидову расстоянию от ближайшей найденной точки.
Таким образом, нам только нужны отсортированные спискидля каждой оси, отсортированной по этой оси.Что довольно просто.
Затем запросим список:
- Мы выполняем двоичный поиск в каждом из списков (dlog (n)).
- Мы находим наштекущее минимальное расстояние, м.(изначально это может быть бесконечность)
- Для каждого списка мы путешествуем в положительном и отрицательном направлениях.
- Для каждого из 2 * d направлений, которые у нас есть,
- Мыпересекайте списки, уменьшая m, когда мы находим более близкие точки.
- Когда направление оказывается математически бесплодным, мы прекращаем поиск таким образом.
- Когда направление не остаетсямы нашли нашу самую близкую точку.
Мы отсортировали списки, и нам нужно найти точку, которую мы ищем в каждом направлении списка.Мы выполняем двоичный поиск, чтобы сохранить журнал временной сложности (n).Тогда у нас будет наилучшее текущее расстояние (возможно, бесконечность), а затем мы будем двигаться в каждом доступном нам направлении.Когда мы находим новые точки, мы обновляем ближайшую точку, которая у нас есть.Хитрость в том, что мы покидаем, как только расстояние только в одном этом направлении становится больше, чем наша текущая известная ближайшая точка.
Так что если у нас есть точка на известном ближайшем расстоянии 13, то мы можем прервать проверку в+ x, -x, + y, -y, направления, как только расстояние только в этом направлении превышает наше ближайшее известное расстояние.Потому что, если он больше + x, чем наш текущий m, математически может быть доказано, что все остальные значения + x находятся дальше.По мере того, как мы получаем все лучшие и лучшие ближайшие точки, количество пространства, которое нам нужно искать, становится все меньше и меньше.
Если у нас заканчиваются точки в каком-либо направлении, это направление заканчивается.Если расстояние до точки вдоль только этого одного измерения линии больше, чем m, то это направление заканчивается.
Решение - это m, когда все направления, как доказано, имеют только точки, которые должны быть дальше наших лучшихпока что.
- Поскольку мы постепенно уменьшаем m, расстояние в каждом измерении, необходимое в целом, быстро уменьшается, хотя, как и во всех алгоритмах, оно уменьшается менее быстро в более высоких измерениях. Но если расстояние только в одном измерении больше, чем лучшее, что у нас есть, это обязательно должно быть так, что все остальные точки в этом направлении не могут быть лучше.
Со временем сложность кажется наравне с лучшими. Но в простоте структур данных этот алгоритм явно выигрывает. Есть много других свойств, которые делают этот алгоритм серьезным соперником. Когда вы обновляете материал, вы можете использовать списки с действительно хорошей производительностью, потому что вы очень часто сортируете уже отсортированные списки или почти отсортированные списки. Вы перебираете массивы. В реальном выражении большинство структур данных - отстой. Обычно из-за кеширования и того, как устроена память, мы должны быть агностиками в отношении таких вещей, но это имеет большое значение. Данные, расположенные рядом с текущими релевантными данными, на 1043 * намного быстрее, чем на самом деле. Если мы уже знаем, где точка, которую мы будем искать, в списках, мы можем решить ее еще быстрее (поскольку нам не нужно было бы находить ее с помощью бинарного поиска). И другие разрешенные трюки, использующие информацию из предыдущей итерации здесь и там. А дополнительные измерения в основном бесплатны (за исключением того, что тогда значение не сходится быстрее, но это потому, что в сфере больше случайно распределенных точек, чем в круге того же радиуса).
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-points. Вы заметите, что очень мало изменилось. Единственно релевантным было то, что если найденная точка v будет меньше текущей m (FindDistanceMaxSq), то эта точка добавляется в кучу, и значение для m устанавливается равным евклидову расстоянию между позицией поиска и k-й элемент. Обычную версию алгоритма можно рассматривать как случай, когда k = 1. Мы ищем 1 элемент, который хотим, и обновляем m, чтобы он стал равным единственному (k = 1) элементу, когда v оказывается ближе.
Имейте в виду, что я только когда-либо делаю сравнение расстояний в форме квадрата расстояния, так как мне только нужно знать, находится ли он дальше, и я не трачу циклы часов на функции квадратного корня.
И я знаю, что существует идеальная структура данных для хранения k-элементов в куче с ограниченным размером. Очевидно, что вставка массива не является оптимальной для этого. Но, кроме слишком большого количества Java-зависимых API-файлов, для этого конкретного класса просто не было ни одного, хотя, очевидно, Google Guava делает его. Но вы вообще не заметите, учитывая, что шансы хорошие, ваш k, вероятно, не так велик. Но это усложняет временную сложность вставки в точках, хранящихся в k-времени. Есть также такие вещи, как кэширование расстояния от точки нахождения для элементов.
Наконец, и, что наиболее важно, проект, который я бы использовал для тестирования кода, находится в стадии перехода, поэтому мне не удалось проверить это. Но это, безусловно, показывает, как вы это делаете: вы храните 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;
}