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

Question

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

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

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

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

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

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

Answer 1

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

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

РЕДАКТИРОВАТЬ: Я задал вопрос о реализации дерева kd здесь - может быть полезно.

РЕДАКТИРОВАТЬ: KD-деревья успешно использовались для поиска NN :) - Кроме того, если вы хотите принимать приблизительные совпадения, вы можете использовать Быстрая библиотека для приблизительной ближайшей соседки ( Flann) . Реализация FLANN присутствует в OpenCV 2.0 .

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

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.