KD樹 - 最近鄰算法

我不完全理解wikipedia的O（log n）最近鄰算法。KD樹 - 最近鄰算法

...

...

算法解開樹的遞歸，在每個節點執行下列步驟：

...

算法檢查是否有可能是分裂平面另一側比當前最接近搜索點的任何點。在概念上，這是通過將分裂超平面與具有半徑等於當前最近距離的搜索點周圍的超球體相交來完成的。由於超平面都是軸對齊的，因此將其作爲簡單比較來實現，以查看搜索點與當前節點的分割座標之間的差異是否小於從搜索點到當前最佳點的距離（總體座標）。

如果超球面穿過平面，平面另一側可能會有更近的點，所以算法必須從當前節點向下移動樹的另一個分支，尋找更近的點，遵循相同的遞歸處理爲整個搜索。

如果超球面不與分裂平面相交，則算法繼續向上走樹，並且該節點另一側的整個分支被消除。

這3.2是困惑我，我已經看到了this問題。我正在用Java實現算法，不確定是否正確。

//Search children branches, if axis aligned distance is less than current distance 
if (node.lesser!=null) { 
    KdNode lesser = node.lesser; 
    int axis = lesser.depth % lesser.k; 
    double axisAlignedDistance = Double.MAX_VALUE; 
    if (axis==X_AXIS) axisAlignedDistance = Math.abs(lastNode.id.x-lesser.id.x); 
    if (axis==Y_AXIS) axisAlignedDistance = Math.abs(lastNode.id.y-lesser.id.y); 
    else if (axis==Z_AXIS) axisAlignedDistance = Math.abs(lastNode.id.z-lesser.id.z); 

    //Continue down lesser branch 
    if (axisAlignedDistance<=lastDistance && !set.contains(lesser)) { 
     searchNode(value,lesser,set,K); 
    } 
} 
if (node.greater!=null) { 
    KdNode greater = node.greater; 
    int axis = greater.depth % greater.k; 
    double axisAlignedDistance = Double.MAX_VALUE; 
    if (axis==X_AXIS) axisAlignedDistance = Math.abs(lastNode.id.x-greater.id.x); 
    if (axis==Y_AXIS) axisAlignedDistance = Math.abs(lastNode.id.y-greater.id.y); 
    else if (axis==Z_AXIS)axisAlignedDistance = Math.abs(lastNode.id.z-greater.id.z); 

    //Continue down greater branch 
    if (axisAlignedDistance<=lastDistance && !set.contains(greater)) { 
     searchNode(value,greater,set,K); 
    } 
}

上面的代碼是否完成算法的3.2方面？特別是在填充「axisAlignedDistance」變量的位置。

你可以找到KDTree here的完整源代碼。

感謝您的任何幫助/指針。

「的算法解開樹的遞歸，在每個節點執行以下步驟：」

你實現

來源

2012-06-26 Justin

你測試過了嗎？爲什麼要問一個關於代碼的問題，你認爲它會做它應該做的事情？如果沒有自己測試代碼，我會說它看起來應該完成這項工作。而且，如果可能的話，我會避免while（true）循環。特別是因爲你的情況，在循環之後它始終是current = node。 – kutschkem

更好地測試代碼，然後提出有關理解算法的問題。如果它不起作用，那麼你可以發佈輸出，我們可以從那裏去。 –

@kutschkem我測試了代碼，它返回了正確的結果，但這並不意味着它正確地實現了算法。我的意思是O（n）算法會返回正確的結果，但不會是正確的。我會更新問題以幫助縮小問題的範圍。 – Justin

我加了這個，希望能幫助別人找到同樣的問題。我用下面的代碼結束了對3.2的處理。雖然，我不確定它是否100％正確。它已經通過了我提出的所有測試。上面的原始代碼在許多相同的測試用例上失敗了。利用點，線，矩形和多維數據集對象

更明確的解決方案：

int axis = node.depth % node.k; 
KdNode lesser = node.lesser; 
KdNode greater = node.greater; 

//Search children branches, if axis aligned distance is less than current distance 
if (lesser!=null && !examined.contains(lesser)) { 
    examined.add(lesser); 

    boolean lineIntersectsRect = false; 
    Line line = null; 
    Cube cube = null; 
    if (axis==X_AXIS) { 
     line = new Line(new Point(value.x-lastDistance,value.y,value.z), new Point(value.x+lastDistance,value.y,value.z)); 
     Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tur = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tlr = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bur = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point blr = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } else if (axis==Y_AXIS) { 
     line = new Line(new Point(value.x,value.y-lastDistance,value.z), new Point(value.x,value.y+lastDistance,value.z)); 
     Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tlr = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY); 
     Point tll = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point blr = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY); 
     Point bll = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } else { 
     line = new Line(new Point(value.x,value.y,value.z-lastDistance), new Point(value.x,value.y,value.z+lastDistance)); 
     Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z); 
     Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z); 
     Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z); 
     Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } 

    //Continue down lesser branch 
    if (lineIntersectsRect) { 
     searchNode(value,lesser,K,results,examined); 
    } 
} 
if (greater!=null && !examined.contains(greater)) { 
    examined.add(greater); 

    boolean lineIntersectsRect = false; 
    Line line = null; 
    Cube cube = null; 
    if (axis==X_AXIS) { 
     line = new Line(new Point(value.x-lastDistance,value.y,value.z), new Point(value.x+lastDistance,value.y,value.z)); 
     Point tul = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tll = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bll = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } else if (axis==Y_AXIS) { 
     line = new Line(new Point(value.x,value.y-lastDistance,value.z), new Point(value.x,value.y+lastDistance,value.z)); 
     Point tul = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY); 
     Point tur = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY); 
     Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY); 
     Point bur = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY); 
     Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } else { 
     line = new Line(new Point(value.x,value.y,value.z-lastDistance), new Point(value.x,value.y,value.z+lastDistance)); 
     Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z); 
     Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z); 
     Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z); 
     Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z); 
     Rectangle trect = new Rectangle(tul,tur,tlr,tll); 
     Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY); 
     Rectangle brect = new Rectangle(bul,bur,blr,bll); 
     cube = new Cube(trect,brect); 
     lineIntersectsRect = cube.inserects(line); 
    } 

    //Continue down greater branch 
    if (lineIntersectsRect) { 
     searchNode(value,greater,K,results,examined); 
    } 
}

我覺得this簡單的代碼也應該工作，已通過所有相同的測試上面的代碼。

int axis = node.depth % node.k; 
KdNode lesser = node.lesser; 
KdNode greater = node.greater; 

//Search children branches, if axis aligned distance is less than current distance 
if (lesser!=null && !examined.contains(lesser)) { 
    examined.add(lesser); 

    double p1 = Double.MIN_VALUE; 
    double p2 = Double.MIN_VALUE; 
    if (axis==X_AXIS) { 
     p1 = node.id.x; 
     p2 = value.x-lastDistance; 
    } else if (axis==Y_AXIS) { 
     p1 = node.id.y; 
     p2 = value.y-lastDistance; 
    } else { 
     p1 = node.id.z; 
     p2 = value.z-lastDistance; 
    } 
    boolean lineIntersectsCube = ((p2<=p1)?true:false); 

    //Continue down lesser branch 
    if (lineIntersectsCube) { 
     searchNode(value,lesser,K,results,examined); 
    } 
} 
if (greater!=null && !examined.contains(greater)) { 
    examined.add(greater); 

    double p1 = Double.MIN_VALUE; 
    double p2 = Double.MIN_VALUE; 
    if (axis==X_AXIS) { 
     p1 = node.id.x; 
     p2 = value.x+lastDistance; 
    } else if (axis==Y_AXIS) { 
     p1 = node.id.y; 
     p2 = value.y+lastDistance; 
    } else { 
     p1 = node.id.z; 
     p2 = value.z+lastDistance; 
    } 
    boolean lineIntersectsCube = ((p2>=p1)?true:false); 

    //Continue down greater branch 
    if (lineIntersectsCube) { 
     searchNode(value,greater,K,results,examined); 
    } 
}

來源

2012-06-27 17:48:02 Justin

重要的是要注意，從3以下是很重要的似乎只是進行遞歸調用，而不是遞歸遞歸的任何事情。

儘管看起來您正在檢測交集，但您並未執行遞歸的退出（展開）步驟。遞歸調用完成後，會執行0個步驟（包括3.2）。

3。2個狀態：「如果超球不相交的分割平面，那麼算法繼續走了樹，並在該節點的對方整支消除」

這是什麼意思？在到達基本案例（算法到達葉節點）後，遞歸開始放鬆。在每一級遞歸解除之後，該算法檢查以查看子樹是否可能包含更近的鄰居。如果可以，則在該子樹上進行另一次遞歸調用，如果不是，則該算法繼續展開（走向樹）。

你應該這樣開始：

「根節點開始，算法樹它將如果搜索點進行插入下移遞歸，以同樣的方式」

然後開始思考在遞歸解開期間要採取什麼步驟以及何時採取的步驟。

這是一個具有挑戰性的算法。如果您已完成此數據結構的insert（）方法，則可以將其用作此算法的開始框架。

編輯：

//Used to not re-examine nodes 
Set<KdNode> examined = new HashSet<KdNode>();

它可能會更容易，更快，將使用較少的內存來簡單地將一個標誌，你可以標記爲「走訪」的每個節點。理想情況下，HashSet有一個恆定的時間查詢，但真的沒有辦法保證這一點。這樣，每次訪問時都不必搜索一組節點。在搜索樹之前，您可以在O(N)時間將所有這些值初始化爲false。

來源

2012-06-26 17:56:59

展開應該發生在最初的葉節點上調用「searchNode（）」的「nearestNeighbourSearch（）」方法調用中。在「searchNode（）」在葉節點上完成之後，它返回到「nearestNeighbourSearch（）」方法，該方法移動到葉的父節點並在其上調用「searchNode（）」。 – Justin

@Justin：我現在明白了。但是你有兩個獨立的方法遍歷樹。您需要在每個遞歸級別展開後執行這些檢查，以確保'O（log（N））'的運行時間。關於檢查的Set的 –

。當計算機正常工作時，我打算這麼做。 – Justin

是的，在維基百科上的KD樹中搜索NN（最近鄰居）的描述有點難以遵循。在NN KD Tree搜索中，很多谷歌搜索結果都是錯誤的！

請參閱https://stackoverflow.com/a/37107030/591720瞭解正確的說明/算法。

來源

2016-05-09 02:39:01

KD樹 - 最近鄰算法

回答

相關問題