Ваше дерево kd правильное.
Алгоритм ближайшего соседа
Поиск ближайшего соседа дерева kd пересекает дерево, чередуя две фазы:
-
Go фаза-вниз:
Обратите внимание на расстояние между вашей входной точкой и текущим узлом в дереве (фактическое расстояние, а не расстояние по оси).
Чередуя ось x и ось y, сравните координату оси вашей входной точки с координатой оси текущего узла в дереве, чтобы определить, какое поддерево go вниз до.
Повторяйте фазу Go вниз до тех пор, пока не достигнете нижней части дерева, затем введите Go фазу резервирования.
Go - резервная фаза:
Go до одного уровня. Если вы не можете go up, все готово.
Если вы уже выполнили фазу Go -распада на обоих поддеревьях текущего узла, повторите Go -back-up.
Если фактическое расстояние до лучшего соседа, которого вы нашли до сих пор, ближе, чем расстояние по оси между вашим входным узлом и текущим узлом в дереве, повторить Go -бэк-ап.
В противном случае введите Go -фаза спада на поддереве, противоположном тому, с которого вы пришли.
Ваш пример
Вот эскиз вашего дерева kd, чтобы прояснить его:
Применение этих шагов на вашем примере дерева и узла ввода (2,4):
- Начните с фазы Go -down в узле root (8,1). Расстояние между (8,1) и входным узлом (2,4) равно 6,708, поэтому (8,1) является нашим известным на данный момент ближайшим соседом. Текущей осью является x, поэтому мы сравниваем 8 и 2 и видим, что нам нужно go к левому поддереву.
- Текущий узел - (7,3). Расстояние между (7,3) и входным узлом (2,4) составляет 5,099, что лучше, чем предыдущее известное расстояние, поэтому (7,3) становится нашим новым ближайшим соседом. Текущей осью является y, поэтому мы сравниваем 3 и 4, и мы видим, что go нужно указать правое поддерево.
- Текущий узел (5,8). Расстояние между (5,8) и входным узлом (2,4) равно 5.000, что меньше, чем предыдущее известное расстояние, поэтому (5,8) становится нашим новым ближайшим соседом. Текущая ось равна x, но мы не можем дальше go вниз, поэтому мы входим в фазу Go -back-up.
- We go обратно в (7,3). Текущая ось y. Y-расстояние между (7,3) и входным узлом (2,4) составляет | 3-4 | = 1, что меньше 5, расстояние до известного на данный момент ближайшего соседа. Поэтому мы должны войти в фазу Go -back-down на другом поддереве. Вы можете видеть это на рисунке: расстояние между входной точкой (S) и (5,8) больше, чем расстояние между (S) и разделительной линией, проходящей через (7,3). Это означает, что на другой стороне разделительной линии может быть ближайший сосед.
- Текущий узел - (3,2). Расстояние между (3,2) и входным узлом (2,4) составляет 2,236, что лучше, чем ранее известное наилучшее расстояние, поэтому (3,2) становится нашим известным на данный момент ближайшим соседом. Текущей осью является x, но мы не можем go дальше, поэтому мы входим в фазу Go -back-up.
- Мы go возвращаемся к (7,3). Текущая ось y. Мы посетили оба поддерева этого узла, поэтому мы повторяем фазу Go -back-up.
- Мы go возвращаемся к (8,1). Текущая ось х. Х-расстояние между (8,1) и входным узлом (2,4) составляет | 8-2 | = 6, что больше расстояния до известного в настоящее время ближайшего соседа, поэтому мы повторяем фазу Go -back-up. Вы снова можете увидеть это на рисунке: расстояние между входной точкой (S) и текущим ближайшим соседом (3,2) меньше, чем расстояние между (S) и разделительной линией, проходящей через (8,1). Это означает, что не может быть ближайшего соседа по другую сторону от разделительной линии.
- Мы не можем go подняться дальше, поэтому мы закончили.
Узлы, которые мы посетили, были: (8,1), (7,3), (5,8), (7,3), (3,2), (7,3), (8,1) , Ближайший сосед, которого мы нашли, был (3,2) на расстоянии 2,236.