Что не так с моим KD-Tree? (К = 2)

Question

Точнее, что-то не так с поиском ближайшего соседа. Я подтвердил, что дерево построено правильно, и что все вспомогательные функции работают должным образом.

Обратите внимание, что это немного отличается от стандартных KD-деревьев тем, что я ищу ближайшие 3 пункта.

struct Node
{
unsigned int axis;
Point* obj;

struct Node* left;
struct Node* right;
};


void _findClosest(struct Node* current, Point* to, Point** first, Point** second, Point** third, unsigned int depth)
{
if(current == NULL) return;

if(current->left == NULL && current->right == NULL)
{
            //_setOrder updates first, second, and third so that they point to
            //objects that are closest to "to", given an object and the current
            //current first, second, and third.
    _setOrder(to, current->obj, first, second, third);
    return;
}

unsigned int axis = depth % 2;
struct Node* other = NULL;

if(to->getValue(axis) < current->obj->getValue(axis))
{
    other = current->right;
    _findClosest(current->left, to, first, second, third, depth+1);
}
else
{
    other = current->left;
    _findClosest(current->right, to, first, second, third, depth+1);
}

_setOrder(to, current->obj, first, second, third);

if(other == NULL) return;

double searchToBest = _largestDistance(to, *first, *second, *third);
double searchToSplit = _distance(to, current->obj, current->axis);

    //This branch is ALWAYS taken, so this devolves into an O(n) search
if(searchToBest >= searchToSplit)
{
    _findClosest(other, to, first, second, third, depth+1);
}
}

Полагаю, я просто неправильно понимаю структуру данных / алгоритм.

Незначительные детали:
-Если функции расстояния вызываются для объектов NULL, они возвращают std :: numberic_limits :: max ()
-это вызывается в корне дерева KD с глубиной 0 и * first = * second = * third = NULL
ось = 0 соответствует X, ось = 1 соответствует Y

Проблема в том, что каждый узел посещается, а не видит ожидаемые сокращения от использования свойств дерева. Каким бы ни был недостаток, это делает поиск O (n).

Answer 1

Эта строка неверна:

double searchToSplit = _distance (to, current-> obj, current-> axis);

Вы хотите ось, а не текущая-> ось.