Как работает алгоритм разделения пространства для поиска ближайших соседей?
Для нахождения ближайшего соседа Space Partitioning является одним из алгоритмов. Как это работает?
Предположим, у меня есть двумерный набор точек (координаты x и y), и мне дана точка (a,b). Как этот алгоритм узнает ближайшего соседа?
2 ответа
Пространственное разбиение - это на самом деле семейство тесно связанных алгоритмов, которые разделяют пространство, чтобы приложения могли легче обрабатывать точки или многоугольники.
Я считаю, что есть много способов решить вашу проблему. Я не знаю, насколько сложным вы готовы построить свое решение. Простой способ, вероятно, построить двоичное дерево, разделяющее пространство на 2. Все точки разделены между некоторой средней плоскостью. Постройте свое дерево путем рекурсивного деления, пока у вас не закончатся точки.
Поиск ближайшего соседа будет оптимизирован, поскольку каждый обход дерева сужает область поиска.
В некоторой литературе они называют это дерево кд
Эти два видео должны помочь:
- Объяснение того, как создается дерево KD: http://www.youtube.com/watch?v=T9h2KKJ_Pl8
- Объяснение того, как выполнять поиск ближайших соседей: http://www.youtube.com/watch?v=2SbVSxWGtpI