如何處理R樹和四叉樹的重複點？

我正在尋找實現四叉樹和r-tree數據結構以測試處理二維點分佈的一些想法。我的問題是，這些算法如何處理重複點？或者有什麼處理重複點的技巧？如何處理R樹和四叉樹的重複點？

2015-09-15 Stefan Orr

很可能你可以忽略/刪除重複的點。

2015-09-15 23:32:14 Bytemain

我無法忽略或刪除點。我想找到有關所有點的分佈的信息，所以知道有重複是很重要的。不過，我不確定在這種情況下如何處理分區。我想我只需要創建一個班級點，如果創建了一個重複點，並且忽略分區部分，那麼該點的點數也會增加。 –

QuadTrees需要注意。天真的實現將嘗試繼續分割，直到元素的最大數量少於m個（默認m = 1）。如果你有m + 1個副本，它將會進入無限循環。因此，你需要檢測並處理重複的點。

R-樹更好。重疊頁面是完全有效的。因此，即使僅包含重複項的頁面溢出，您也可以將其分割。 R樹分割總是必須將數據分割成兩個同等大小的頁面。

2015-09-16 06:30:22

是的，R-tree應該可以用於重複點（例如Boost.Geometry R-tree允許重複）。「經典」平衡KD樹（將節點點存儲在堆狀數組中，並使用點的座標作爲劃分平面），也應該爲重複點提供開箱即用的功能。 –

回答