從位於距離範圍內的集合中移除位置的算法

Question

我正在尋找一個解決方案，我擁有一組具有一定優先級的位置。

我想刪除較低優先級的位置，使得沒有剩餘位置位於特定距離（比如100米）內的任何位置。

Answer 1

A k-d tree聽起來很適合這個問題。

• 如果你刪除了絕大多數的點，它可能使最有意義，從具有最高優先級的點開始，併爲每個點，做類似的近鄰搜索的東西（停止一旦我們得到由給定距離限定的點），以檢查是否插入點。

  您可能需要嘗試查找自動平衡變體或在此過程中偶爾重新平衡樹，因爲不平衡樹會導致操作速度變慢。

• 如果有很大一部分點將保留下來，最好將所有點插入樹中，以便從最低點開始修改最近鄰點搜索（忽略點本身，以距離爲界）在我們走的時候優先考慮並刪除相關的要點

  使用適當的施工技術，您可以從一開始就構建平衡樹。

插入和刪除需要O均衡樹（log n）的（一個簡單的方法來刪除是剛剛設置的節點的「刪除」標誌，但這並不永遠做樹更小）和O（n）在不平衡的樹中。最近鄰居搜索是相似的，儘管即使對於平衡樹也可能會花費O（n），但這是最差的情況 - 平均而言，它應該更接近於O（log n）。

k-d樹是一個二叉樹，其中每個節點都是一個k維點。每個非葉節點都可以被認爲是隱式地生成一個分裂超平面，該空間將空間分成兩部分，稱爲半空間。該超平面左側的點由該節點的左側子樹表示，超平面的點右側由右側子樹表示。超平面方向的選擇方式如下：樹中的每個節點都與其中一個k維關聯，超平面與該維的軸垂直。因此，例如，如果對於特定分割選擇「x」軸，具有比該節點更小的「x」值的子樹中的所有點將出現在左子樹中，並且具有更大「x」值的所有點將是在正確的子樹中。在這種情況下，超平面將由該點的x值設置，其法線將爲單位x軸。

搜索在kd樹收益的近鄰如下：

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

Answer 2

我假設你打算刪除位置，從最低優先級的位置開始，距離另一個位置有一定的距離。

您可以使用quad tree來表示相對位置。這個想法是，你構造一棵樹，每個節點有四個孩子。每個孩子代表一個象限，當你添加每個位置時，你遍歷樹。如果您擊中無孩子的節點，那麼您將創建新的子節點，再次表示劃分爲四個區域的同一區域，直到每個位置都在其自己的區域中。

創建此樹後，您可以將每個位置之間的距離檢查的樣本大小減少到僅限於特定深度內的距離，並且僅限附近象限內的位置。

這種方法是但近似和不保證您檢查跨越整個主象限的位置，但它確實有效地讓你距離檢查大部分地區被附近有效地降低了運行時間。爲了解決這個問題，您可以使用相同的數據創建多個具有輕微偏移的四叉樹，但是當然，每個四叉樹將在運行時成爲倍增因子，因爲您將逐個構建並檢查每個樹。

這是回答您的問題嗎？