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

Question

У нас есть список пар x,y.Каждая пара представляет собой точку в двумерном пространстве.Я хочу найти ближайшую точку из этого списка к определенной точке xq, yq.Каков наилучший алгоритм, критичный к производительности, для решения этой проблемы?Лисп точек не изменится;это означает, что мне не нужно выполнять вставку и удаление.Я хочу просто найти ближайшего соседа целевой точки xq, yq в этом наборе.

Правка 1:Спасибо всем!Как правильно догадался Stephan202, я хочу делать это неоднократно;как функция.Список не обязательно отсортирован (на самом деле я не понимаю, как его можно отсортировать?Как таблица с первичным ключом из 2 столбцов a и y?Если это поможет, я разберусь с этим).

Я создам структуру данных на основе списка один раз, а затем буду использовать эту сгенерированную структуру данных в функции (если этот процесс сам по себе релевантен).

Спасибо тебе, Джейкоб;Похоже, что структура данных KD-Tree является хорошим кандидатом на роль ответа (И я чувствую, что это так.Я обновлю, когда получу некоторые релевантные результаты).

Правка 2:Я обнаружил, что эта проблема называется "ближайший сосед"!

Правка 3:Первое название было "В поисках алгоритма (для пространственных запросов и пространственной индексации) (Ближайший сосед)".;Я выбрал новое название:"Наилучший алгоритм, критичный к производительности, для решения задач ближайшего соседа".Поскольку я не хочу выполнять операцию вставки и удаления моих исходных данных, и мне нужен только ближайший из них к новой точке (которая не будет вставлена), я решил (в настоящее время) работать с KD-деревьями.Спасибо всем!

Answer 1

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

Я бы порекомендовал KD-tree, реализацию которого можно легко найти в нескольких пакетах, таких как OpenCV 2.0.Или вы могли бы реализовать его самостоятельно!

Редактировать: Я задал вопрос о реализациях kd-дерева здесь - это может быть полезно.

Редактировать: KD-деревья широко и успешно используются для поиска по NN :) - Кроме того, если вы готовы принять приблизительные совпадения, вы можете использовать Быстрая библиотека для поиска примерной ближайшей соседки (ФЛАНН).Реализация FLANN присутствует в OpenCV 2.0.

Если вам не нужны приблизительные ответы, вы можете настроить параметры ФЛАННА для поиска по всему дереву.

Answer 2

Если точка запроса (xq, yq) меняется, а список - нет, вам необходимо рассчитать Диаграмма Вороного списка точек. Это даст вам набор полигонов или «ячеек». (некоторые из которых бесконечны); каждый многоугольник соответствует точке из исходного списка, называемой «сайт» этой клетки. Любая точка, которая полностью лежит внутри одного многоугольника, ближе к сайту этого многоугольника, чем к другим сайтам в исходном списке. Любая точка на границе между двумя полигонами находится на одинаковом расстоянии от каждого участка.

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

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

Если вы не хотите писать код самостоятельно, и вам не следует этого делать, попробуйте получить библиотеку, например, CGAL , который сделает большую часть работы за вас. Это, вероятно, относится и к ответу KD-дерева, но я точно не знаю.

Answer 3

Вам нужен пространственный индекс .

Если вы катите свой собственный, вы можете сделать намного хуже, чем выбрать R-Tree или алгоритмы Quad-Tree .

Answer 4

Я бы пошел с квадри. Это самая простая пространственная структура. В двух измерениях я бы вообще рекомендовал quadtree вместо kd-tree, потому что это проще, быстрее. Его недостатком является большее потребление памяти, если число измерений велико, но в случае двух измерений разница не значительна.

Есть хороший прием оптимизации, если ваши координаты имеют тип с плавающей точкой: В запросе сначала нужно найти лист-узел, содержащий точку, к которой запрашивается наиболее близкая точка. Для этого вам придется идти по дереву от корня к листу - в каждой итерации решать, на какой дочерний узел перейти. Сохраните идентификаторы / адреса дочерних узлов в массиве 4-х размеров в структуре Node. Оцифруйте координаты точки в алгоритме запроса. Тогда вы сможете найти подходящий подузел, просто проиндексировав массив двумя правильными битами оцифрованных координат точек. Оцифровка выполняется быстро: реализуйте ее с помощью простого static_cast.

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

Answer 5

Выполните итерацию по каждой другой точке, используя формулу расстояния, чтобы найти минимальное расстояние от Q (xq, yq).

Однако вы не предоставили достаточно информации для критического ответа.

Например, если Q - ОЧЕНЬ общая точка, вы можете рассчитать расстояние до Q и сохранить его для каждой точки.

Во втором примере, если у вас огромное количество точек, вы можете организовать точки по разделам и начать с точек только в том же разделе и смежных разделах с разделом, содержащим Q.