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

Question

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

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

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

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

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

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

Answer 1

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

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

EDIT: Я задал вопрос о реализации kd-tree here - был бы вам полезна.

EDIT: KD-деревья широко успешно используется для NN поисков :) - Кроме того, если вы готовы принять приблизительные матчи, вы можете использовать Fast Library for Approximate Nearest Neigbor (FLANN). Реализация FLANN присутствует в OpenCV 2.0.

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Вам нужен spatial index.

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

Answer 5

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

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

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