最近鄰居 - k-d樹 - 維基百科證明

Question

在wikipedia entry for k-d trees上，提出了一種用於在k-d樹上進行最近鄰居搜索的算法。我不明白的是對步驟3.2的解釋。如何知道搜索點的分割座標與當前節點之間的差值大於搜索點的分割座標與當前最佳值之間的差值時，是否沒有近點？

編輯：添加維基百科文章的問題，以防萬一它在維基百科後更改。

NN的

最近鄰搜索動畫在2D與KD樹搜索

最近鄰（NN）算法 旨在找到樹 的點，這是最接近給定輸入 點。通過使用樹 屬性可以有效地完成 的搜索空間的大部分搜索空間。 在 kd樹進行了近鄰搜索如下：

1. 根節點開始，算法向下移動的樹 遞歸，以同樣的方式，它 會，如果搜索點是插入 （即根據該點是否大於或小於分割維度中的當前節點 ，它會向右或向左移動 ），取決於該點是否爲 。
2. 一旦算法到達葉節點，它保存該節點點作爲 「當前最佳」
3. 該算法解開樹的遞歸，在每個節點處執行 以下步驟： 1.如果當前節點比當前最好的更接近，那麼它就成爲當前最好的。 2.該算法檢查在分割平面 的另一側上是否存在比當前最佳搜索點更接近搜索點 的任何點。在概念上，這是通過將 分裂超平面與圍繞搜索點 的 超球相交而得到的，其半徑等於當前的最近距離 。由於 超平面都軸線對準該 被實現爲簡單的比較 看是否 之間的差分割搜索 點的座標和當前節點是從搜索小於 的距離（總體座標） 指向當前最好的 。 1.如果超球越過平面，有可能是在 平面的另一側 接近點，所以算法必須樹的另一分支從 當前節點尋找更接近 點下移 ，以下與整個搜索相同的遞歸 進程。 2.如果超球面不與分割平面相交，則算法繼續向上行走，並且整個分支在 上，該節點的另一側被去掉 。
4. 當算法爲根節點完成此過程時，則搜索完成。

通常，該算法使用平方距離 的距離進行比較，以避免 計算平方根。此外，通過將 平方當前最佳距離保存在 變量中進行比較，可以節省計算量。

Answer 1

仔細看看animation on that page的第6幀。

由於該算法正在恢復遞歸，所以有可能在超平面的另一側存在更近的點。我們已經檢查了一半，但另一半可能會更接近一點。

嗯，事實證明，我們有時可以做一個簡化。如果它的不可能因爲在另一半上的點比我們當前的最佳（最近）點更近，那麼我們可以完全跳過該超平面的一半。這種簡化是在第6幀上顯示的。

找出這種簡化是否可行是通過比較超平面到我們搜索位置的距離來完成的。因爲超平面與軸線對齊，從它到其他點的最短線將沿着一個維度的一條線，所以我們可以比較超平面分割的維度的座標。

如果從搜索點到超平面比從搜索點到當前最近點距離更遠，那麼沒有理由搜索該分割座標。

即使我的解釋沒有幫助，圖形會。祝你的項目好運！

Answer 2

是的，在維基百科的KD樹中搜索NN（最近鄰居）的描述有點難以遵循。在NN KD樹搜索的頂部Google搜索結果中，lot無濟於事！

這裏的一些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); 
     } 
    } 
} 

API爲NN在KD樹搜索：

// 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; 
};