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

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

Quadtrees - это хорошо, но деревья 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

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

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

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

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

Answer 7

Я знаю, что это было сказано как не самый быстрый, если вы хотите ДЕЙСТВИТЕЛЬНО ДЕЙСТВИТЕЛЬНО быстрые результаты, увидев, что я нашел это сообщение от 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, как я