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

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

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

Ответы [ 2 ]

4 голосов
/ 11 ноября 2009

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

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

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

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

2 голосов
/ 03 июня 2011

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

...