如何在KD-Tree中实现范围搜索

Question

我建立了一个d维度 KD 树。我想在这棵树上进行范围搜索。维基百科提到了 KD 树中的范围搜索，但没有以任何方式谈论实现/算法。有人可以帮我解决这个问题吗？如果不是任意的d，至少对d = 2和的任何帮助d = 3都会很棒。谢谢！

Answer 1

kd-tree 有多种变体。我使用的具有以下规格：

1. 每个内部节点最多有两个节点。
2. 每个叶节点可以有最大maxCapacity点。
3. 没有内部节点存储任何点。

旁注：还有一些版本，其中每个节点（无论其内部节点还是叶子节点）只存储一个点。下面的算法也可以针对这些进行调整。主要是buildTree关键区别所在。

大约两年前，我为此编写了一个算法，感谢 @9mat 指出的资源。

假设任务是找到位于给定超矩形（“d”维度）中的点的数量。此任务也可以是列出所有点或位于给定范围内并满足某些其他条件等的所有点，但这可以是对我的代码的直接更改。

将基节点类定义为：

template <typename T> class kdNode{
    public: kdNode(){}
    virtual long rangeQuery(const T* q_min, const T* q_max) const{ return 0; }
};

然后，内部节点（非叶节点）可以如下所示：

class internalNode:public kdNode<T>{
    const kdNode<T> *left = nullptr, *right = nullptr; // left and right sub trees
    int axis; // the axis on which split of points is being done
    T value; // the value based on which points are being split

    public: internalNode(){}

    void buildTree(...){
        // builds the tree recursively
    }

    // returns the number of points in this sub tree that lie inside the hyper rectangle formed by q_min and q_max
    int rangeQuery(const T* q_min, const T* q_max) const{
        // num of points that satisfy range query conditions
        int rangeCount = 0;

        // check for left node
        if(q_min[axis] <= value) {
            rangeCount += left->rangeQuery(q_min, q_max);
        }
        // check for right node
        if(q_max[axis] >= value) {
            rangeCount += right->rangeQuery(q_min, q_max);
        }

        return rangeCount;
    }
};

最后，叶节点如下所示：

class leaf:public kdNode<T>{
    // maxCapacity is a hyper - param, the max num of points you allow a node to hold
    array<T, d> points[maxCapacity];
    int keyCount = 0; // this is the actual num of points in this leaf (keyCount <= maxCapacity)

    public: leaf(){}

    public: void addPoint(const T* p){
        // add a point p to the leaf node
    }

    // check if points[index] lies inside the hyper rectangle formed by q_min and q_max
    inline bool containsPoint(const int index, const T* q_min, const T* q_max) const{
        for (int i=0; i<d; i++) {
            if (points[index][i] > q_max[i] || points[index][i] < q_min[i]) {
                return false;
            }
        }
        return true;
    }

    // returns number of points in this leaf node that lie inside the hyper rectangle formed by q_min and q_max
    int rangeQuery(const T* q_min, const T* q_max) const{
        // num of points that satisfy range query conditions
        int rangeCount = 0;
        for(int i=0; i < this->keyCount; i++) {
            if(containsPoint(i, q_min, q_max)) {
                rangeCount++;
            }
        }
        return rangeCount;
    }
};

在叶子节点内部范围查询的代码中，还可以在“线性搜索”内部进行“二分搜索”。由于点将沿 axis 排序，因此您可以使用andaxis进行二分搜索查找l和r值，然后从to而不是to进行线性搜索（当然在最坏的情况下它不会有帮助，但实际上，并且特别是如果您的容量相当高，这可能会有所帮助）。q_minq_maxlr0keyCount-1