16

在 kd 树的wikipedia 条目中，提出了一种算法，用于在 kd 树上进行最近邻搜索。我不明白的是步骤3.2的解释。仅仅因为搜索点的分裂坐标与当前节点的差值大于搜索点的分裂坐标与当前最佳点的差值，你怎么知道没有更近的点呢？

最近邻搜索 使用二维 KD 树进行 NN 搜索的动画

最近邻（NN）算法旨在找到树中最接近给定输入点的点。这种搜索可以通过使用树属性快速消除大部分搜索空间来有效地完成。在 kd-tree 中搜索最近邻的过程如下：

  1. 从根节点开始，算法递归地向下移动树，与插入搜索点的方式相同（即它向右或向左移动取决于该点是否大于或小于当前节点。分割维度）。
  2. 一旦算法到达叶节点，它将该节点点保存为“当前最佳”
  3. 该算法展开树的递归，在每个节点执行以下步骤： 1. 如果当前节点比当前最佳节点更接近，则它成为当前最佳节点。2. 算法检查分割平面的另一侧是否有任何点比当前最佳点更靠近搜索点。从概念上讲，这是通过将分割超平面与搜索点周围的超球面相交来完成的，该超球面的半径等于当前最近的距离。由于超平面都是轴对齐的，因此这是一个简单的比较，以查看搜索点和当前节点的分割坐标之间的差异是否小于搜索点到当前最佳点的距离（整体坐标）。1. 如果超球面穿过平面，则平面的另一侧可能有更近的点，因此算法必须从当前节点向下移动树的另一个分支以寻找更近的点，遵循与整个搜索相同的递归过程. 2. 如果超球面不与分裂平面相交，则算法继续向上走，并且该节点另一侧的整个分支被消除。
  4. 当算法完成对根节点的这个过程时，搜索就完成了。

通常，该算法使用平方距离进行比较以避免计算平方根。此外，它可以通过将平方当前最佳距离保存在变量中进行比较来节省计算量。

4

2 回答 2

15

仔细看那页动画的第 6 帧。

当算法返回递归时，它所在的超平面的另一侧可能有一个更接近的点。我们已经检查了一半，但另一半可能更接近一点。

好吧，事实证明我们有时可以进行简化。如果另一半上不可能有一个点比我们当前的最佳（最近）点更近，那么我们可以完全跳过该超平面的一半。这种简化是在第 6 帧中显示的。

通过比较从超平面到我们的搜索位置的距离来确定这种简化是否可行。因为超平面与轴对齐，所以从它到任何其他点的最短线将是一条沿一个维度的线，因此我们可以只比较超平面分割的维度的坐标。

如果从搜索点到超平面的距离比从搜索点到当前最近点的距离更远，那么就没有理由越过那个分割坐标进行搜索。

即使我的解释没有帮助，图形也会。祝你的项目好运！

于 2010-01-10T08:12:05.517 回答
9

是的，维基百科上对 KD 树中 NN（最近邻）搜索的描述有点难以理解。NN KD Tree 搜索中的许多热门 Google 搜索结果都完全错误，这无济于事！

下面是一些 C++ 代码，向您展示如何正确使用它：

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

用于在 KD 树上进行 NN 搜索的 API：

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

默认距离函数：

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

编辑：有些人也在寻求数据结构的帮助（不仅仅是 NN 算法），所以这就是我使用的。根据您的目的，您可能希望稍微修改数据结构。（注意：但您几乎可以肯定不想修改 NN 算法。）

KDPoint 类：

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

KDNode 类：

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

KDTree 类：（注意：您需要添加一个成员函数来构建/填充您的树。）

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};
于 2016-05-09T02:33:29.977 回答