Как работает алгоритм разбиения пространства для поиска ближайших соседей?

StackOverflow https://stackoverflow.com/questions/1713736

Вопрос

Для поиска ближайшего соседа, Разделение пространства это один из алгоритмов.Как это работает?

Предположим, у меня есть 2D-набор точек (координаты x и y), и мне дана точка (a, b).Как бы этот алгоритм определил ближайшего соседа?

Это было полезно?

Решение

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

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

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

В некоторой литературе они называют это дерево kd

Другие советы

Эти два видео должны помочь:

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top