Алгоритм нахождения ближайших точек?

Question

Учитывая набор из нескольких миллионов точек с координатами x, y, какой алгоритм вы выберете для быстрого поиска 1000 лучших ближайших точек из местоположения? «Быстро» здесь означает около 100 мс на домашнем компьютере.

Грубая сила означала бы делать миллионы умножений, а затем сортировать их. Хотя даже простое приложение на Python может сделать это менее чем за минуту, оно все равно слишком длинное для интерактивного приложения.

Граничная рамка для точек будет известна, поэтому разделение пространства на простую сетку будет возможно. Однако точки распределены несколько неравномерно, поэтому я подозреваю, что большинство квадратов сетки будут пустыми, а затем некоторые из них внезапно будут содержать большую часть точек.

Редактировать: не должен быть точным, на самом деле может быть довольно неточным. Это не было бы огромной сделкой, если бы топ-1000 на самом деле были просто случайными точками из топ-2000, например.

Редактировать: набор точек редко меняется.

Answer 1

Как насчет использования quadtree ?

Вы делите область на прямоугольники, если область имеет низкую плотность точек, прямоугольники большие, а если область имеет высокую плотность точек, прямоугольники будут маленькими. Вы рекурсивно подразделяете каждый прямоугольник на четыре под прямоугольника, пока прямоугольники не станут достаточно маленькими или не содержат достаточно точек.

Затем вы можете начать смотреть на точки в прямоугольниках рядом с локацией и двигаться наружу, пока не найдете свои 1000 точек.

Код для этого может быть несколько сложным, поэтому, возможно, вам следует сначала попробовать с простой сеткой и посмотреть, достаточно ли она быстра.

Answer 2

Четыре дерева хороши, но деревья BSP гарантированно будут запущены за O (log n). Я думаю, что для четырех деревьев требуется конечный ограничивающий объем, и есть некоторые вырожденные случаи, когда квадро-деревья с треском проваливаются, например, когда большое количество точек занимает одно и то же относительно небольшое пространство.

При этом, Quadtree, возможно, легче реализовать и довольно эффективны в большинстве обычных ситуаций. Это то, что UPS использует в своих алгоритмах маршрутизации, потому что его недостатки не создают значительных проблем на практике, вероятно, потому, что города имеют тенденцию быть распределенными по интересующей области.

Answer 3

Вы хотите использовать структуру, подобную Quad Tree или RTree. Это многомерные индексные структуры.

Ключ использует хорошую "кривую заполнения пространства", которая помогает определить близость точек. Простая кривая заполнения пространства - это Zorder, но вы бы больше заинтересовались чем-то вроде кривой Гильберта.

http://en.wikipedia.org/wiki/Space_filling_curve

Я не знаю ни одной предварительно упакованной реализации этого материала. Недавно я реализовал свое собственное RTree в двух измерениях, которое поддерживает только массовую загрузку и поиск (через предоставленную ограничивающую рамку).

Один недостаток в том, что ваши очки должны содержаться в конечной области. Там знают, что есть кривые заполнения пространства, которые работают для пространств, которые не являются конечными, но я ничего о них не знаю.

Answer 4

В дополнение к предложениям дерева QuadTree и BSP вы должны поискать поиск ближайшего соседа . Выбор алгоритма зависит от того, как часто вы добавляете в базовый набор данных. Если вы часто добавляете и удаляете, древовидные решения лучше. Если данные более статичны, диаграммы поиска ближайших соседей и вороной могут быть намного быстрее и лучше масштабироваться.

Answer 5

Если набор точек редко меняется, вы также можете рассмотреть возможность использования диаграммы Вороного. Я не уверен, поможет ли это найти первую точку быстрее, но это должно упростить поиск следующих 999 точек.

Answer 6

я знаю, что это было сказано как не самый быстрый, если вы хотите ДЕЙСТВИТЕЛЬНО ДЕЙСТВИТЕЛЬНО быстрые результаты, увидев, что я нашел это сообщение от Google, я подумал, что добавлю свое решение SQL, которое я использовал некоторое время назад, в форме сохраненного процесса , Он ищет места рядом с координатами и возвращает их по расстоянию.

Надеюсь, это кому-нибудь поможет:)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

ПРИМЕЧАНИЕ: я уже говорил, что это не лучшее решение для этого вопроса просто, может быть, для того, кто нашел это в Google, как я

Answer 7

Я предполагаю, что точки находятся в базе данных или в каком-либо индексируемом месте с возможностью поиска? Если так, то должно быть довольно быстро. Из заданной точки вы можете иметь диапазон по осям x и y и получить все местоположения в этом диапазоне (т.е. указать самый верхний левый угол x (a) и y (b) и самый нижний правый угол x (c) и y). (г)).

Затем выполните запрос, где для точек, где y> = b AND y <= d AND x> = a AND x <= c. это будет быстро, если у вас есть индексы по координатам x и y отдельно. (при условии, что начало слева равно 0,0). </p>

Затем вы можете увеличить (или уменьшить, если результат огромен) этот диапазон на z, пока число точек в наборе результатов не станет> = 1000. В некоторых пробных прогонах вы сможете получить стандартное отклонение и другие. статистические числа, которые помогут вам определить размер прямоугольника для начала. Ваша программа также может настроить себя для этого на основе результатов, которые она получает.

Как только вы получите грубые данные, установите довольно простые математические расчеты для определения расстояния между каждой точкой и исходной точкой.