c++ - 我的KD-Tree怎么了？ (K = 2)

更具体地说，我最近的邻居搜索出现问题。我已经确认树是正确构建的，并且所有辅助函数均按预期工作。

请注意，这与标准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对象上调用了distance函数，则它们返回std::numberic_limits::max()
-这是在KD树的根上调用的，深度为0，并且* first = * second = * third = NULL
-axis = 0对应于X，axis = 1对应于Y

问题在于访问了每个节点，而不是看到通过利用树属性而预期的减少。无论有什么缺陷，它都会使它成为O(n)搜索。

最佳答案

这行是错误的:

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

您需要轴，而不是当前->轴。

关于c++ - 我的KD-Tree怎么了？ (K = 2)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/789656/