Найти ближайшая точка в двумерном пространстве
Вчера я прочитал задачу, которая может быть преобразована в следующую задачу с небольшой модификацией:
Координата точки выражается (x, y) в 2D пространство.
Входные данные: массив точек ARRAY = (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)
и еще одна точка D = (xi, yi)
Найдите точку в ARRAY , которая является ближайшей к D . Я имею в виду евклидово расстояние .
Существует очевидное решение: пройти каждую точку в массиве и вычислить ее евклидово расстояние до D . Затем найдите кратчайшее расстояние. Это можно сделать за время O (N). Можем ли мы сделать это быстрее, скажем, за O (logN)? Я пытаюсь использовать подход «разделяй и властвуй», но пока не пришел к конкретной идее.
Обобщение проблемы: как найти ближайшую точку в K-мерном пространстве? Можем ли мы сделать это менее чем за O (N)?
3 ответа
Если массив не отсортирован каким-либо образом, то невозможно сделать что-либо быстрее, чем O (n), так как вы должны проверять каждую точку, чтобы убедиться, что она не ближе, чем все, что вы нашли до сих пор.
Вы МОЖЕТЕ выполнить некоторую предварительную обработку, чтобы отсортировать точки или упаковать их в какую-либо структуру, а затем выполнить поиск по этой структуре. В этом случае, хотя этап предварительной обработки может быть медленнее, чем O (n), отдельные поиски могут быть быстрее. Если у вас есть много точек для проверки по одному и тому же набору точек, это может быть выгодно.
Вы можете использовать Иерархию ограничивающих объемов . Однако это не улучшает сложность наихудшего случая и не ведет напрямую к точному решению.
Я предложил решение за O (logN), если точки отсортированы по координате x.
Он использует подход «разделяй и властвуй». Я делю массив точек на основе их координаты x в 2D-пространстве.
Рассмотрим двумерный случай.
Предположим, каждая точка выражена в следующей структуре данных:
class Point {
public float getX();
public float getY();
}
У нас есть два входа: массив точек ARRAY и еще одна точка D .
Изначально мы хотели бы разделить ARRAY на две части: те точки, которые находятся «слева» от D , и те точки, которые находятся «справа» от D .
int pivotIndex = partition(array, 0, array.length() - 1, d);
После разделения точки с индексом меньше pivotIndex имеют координату x меньше d.getX () ; точки с индексом, равным или большим, чем pivotIndex , имеют координату x, равную или большую, чем d.getX () .
Если все точки находятся слева от D , pivotIndex будет array.length () - 1 . Если все точки находятся справа от D , pivotIndex будет -1 . Если некоторые точки находятся слева от D , а некоторые - справа от D , то pivotIndex будет между 0 и array.length () - 1 . Для точек, имеющих ту же координату x, что и D , они считаются "правой" стороной.
Теперь следующим шагом будет поиск ближайшей точки на каждом разделе:
Point p1 = getNearestDot(array, 0, pivotIndex, d);
Point p2 = getNearestDot(array, pivotIndex + 1, array.length() - 1, d);
if (p1 == null) return p2;
if (p2 == null) return p1;
return nearer(p1, p2, d);
Возможно, все точки в ARRAY находятся слева от D , то в этом случае p2 будет нулевым. Точно так же, если все точки в ARRAY находятся справа от D , то p1 будет нулевым.
Алгоритм getNearestDot работает следующим образом:
// Find the nearest dot in array[low...high] inclusive which is closest to point d
Point getNearestDot(Point[] array, int low, int high, Point d) {
if (low > high)
return null;
if (low == high)
return array[low];
int middle = low + (high - low) >> 1;
Point p1 = getNearestDot(array, low, middle, d);
Point p2 = getNearestDot(array, middle + 1, high, d);
if (p1 == null) return p2;
if (p2 == null) return p1;
return nearer(p1, p2, d);
}
И, наконец, функция nearer (p1, p2, d) должна возвращать либо p1, либо p2, расстояние до которых меньше d.