Как реализовать поиск ближайших соседей с помощью KDTrees?

Question

Итак, я реализую KD-Tree , чтобы выполнить поиск ближайшего соседа.У меня работает дерево, но не думаю, что я полностью понимаю поисковую часть.

Об обходе дерева для поиска соседа в статье в Википедии говорится следующее:

Starting with the root node, the algorithm moves down the tree recursively, in the same  
way that it would if the search point were being inserted (i.e. it goes right or left 
depending on whether the point is greater or less than the current node in the split 
dimension).

Что означает «больше или меньше текущего узла в измерении косы?сравнивать точки на основе расстояния от запроса, или мы сравниваем точки по разделенному измерению?

Кроме того, кто-то может объяснить часть о гиперпространстве и гиперплоскости?не уверен, что мне нужно больше объяснений.

Спасибо!

Answer 1

Каждый узел разбивает пространство на 2 полупространства вдоль одной оси.Вы смотрите, где рассматриваемая точка относительно этой плоскости разбиения, чтобы решить, с какой стороны дерева спуститься.Например, если ваша точка (4,7,12), и у вас есть плоскость расщепления, которая обрезает ось у в 9, вы сравниваете 7 с 9 и решаете спуститься с левой (меньше) стороныкд дерево первым.Найдя ближайшего соседа с левой стороны, вы проверяете, ближе ли он, чем 2 (расстояние до плоскости разбиения: 9-7).Если он ближе, чем плоскость расщепления, вам вообще не нужно проходить другую половину дерева.Вот почему это работает так хорошо, что в большинстве случаев вам придется обходить только одно поддерево.

Надеюсь, что это поможет.