Алгоритм поиска близлежащих точек?

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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 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. Через некоторые пробные прогоны вы должны иметь возможность придумать стандартное отклонение и другое статистические числа, которые помогут вам определить размер прямоугольника для начала. Ваша программа также может настраивать свое "я" для этого на основе полученных результатов.

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

Ответ 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, как я