K-d деревья: алгоритм поиска ближайшего соседа

Шаг 4 - это «else» на шаге 3, что вы делаете, если плоскость ближе, чем точка. Тот факт, что найденная вами точка будет находиться в том же прямоугольнике, что и точка, для которой вы ищете соседа, не означает, что она является ближайшей.

Представьте себе следующий сценарий: у вас есть две точки в вашем kD-дереве, A и B. A находится в середине его прямоугольника, а B находится чуть выше края, в разделенной области рядом с A. Если вы теперь выполните поиск для ближайшего соседа к точке C, которая находится рядом с B, но оказывается по другую сторону края и в области разделения A, ваша первая точка, которую вы выберете, будет A из-за начального поиска в глубину, который выбирает все будет в том же разделе, что и ваша точка поиска. Однако B на самом деле ближе, поэтому, даже если вы выбрали A, вам нужно проверить, ближе ли B, иначе ваше kD-Tree на самом деле не даст вам правильных результатов.

Хороший способ визуализировать это - нарисовать:

A-------------C--|--B

A - это первая точка, которую мы нашли в DFS, C - это наша точка, ближайший сосед которой мы хотим, B - фактический ближайший сосед, | это наш разделенный самолет.

Другой способ представить это - нарисовать круг с радиусом dist (A, C) вокруг точки C. ближе к C, чем A, поэтому их необходимо проверить. Если вы теперь найдете B, вы можете уменьшить радиус своего круга (потому что B ближе), чтобы меньше прямоугольников могло пересекаться, и как только вы проверите все прямоугольники, которые пересекаются с вашим кругом (уменьшив радиус вашего круга, как ваш найти более близких соседей) можно однозначно сказать, что более близких точек нет.

Я написал базовую реализацию C ++ на github. У него есть как итеративная, так и рекурсивная версии.