我應該使用什麼空間索引算法？

Question

我想爲我的MKAnnotations實現一些空間索引數據結構之王。 目前，當我嘗試根據距離標準（位置3-4k，目前極其緩慢，使用簡單雙for ...）對其進行過濾時，速度非常慢。

我想創建MKAnnotations的集羣，以確定它是否接近另一個集羣。此外，這些位置處於某種程度上（創建）的順序，並且需要「前」/「後」功能來「跳躍」（這不是必須的）。 我讀過kd-tree和r-tree結構，它們都似乎滿足過濾/聚類的快速距離/鄰居獲取選項，但我不確定哪個對我最好，或者是否還有其他選項。 我應該使用什麼算法/數據結構？

更新：我將這些位置存儲在覈心數據數據庫中，它們表示路徑。當地圖打開時，它們被提取到一個數組中，然後我使用該數組進行距離計算和註記創建。 當用戶移動/縮放地圖時，我會遍歷它們並決定在地圖上需要更改哪些內容，因此整個內容都是靜態的。據我瞭解，如果我使用樹，我可以在那裏存儲位置，當發生縮放/移動時，我只需搜索它並獲取新區域中的位置。這是真的 ？

即使在動態的情況下，當我可以添加新的位置到這個數組時，它將是一個插入，它很少發生。

Answer 1

這很大程度上取決於您的模式的使用情況（我的寫入方式，例如內存或磁盤）以及數據的外觀（分配方式）。

R-樹是好的，因爲它們是平衡，並允許更新。根據我的經驗，R * -tree顯然比其他變體更好，因爲它具有分割策略。好處是它比其他策略生成更多的方形頁面，因此對於許多查詢，您將需要掃描更少的頁面。

如果你是在內存中並且是靜態的，kd-tree是很好的。更新它們非常糟糕，你需要經常重建索引。

如果您的數據不會經常更改，則R-tree的批量加載工作得非常好。你可以做Sort-Tile-Recursive批量加載，它基本上需要（部分）在X和Y上對你的數據進行交替排序，所以用O(n log n)來構建樹;非常類似於批量加載kd-tree，除了你是多分裂而不是二分裂。這非常受歡迎。

此外，您可以跟蹤每個頁面中的對象數量。在地圖上顯示內容時，如果頁面在屏幕上顯示得太小（即小於標記），則可能需要提前停止。此時，您將不掃描該頁面，但只取對象的數量並將其顯示爲聚簇標記，直到用戶放大爲止。

對於具有有限值域的2D數據，請不要忽略簡單的東西。 Quadtrees也可以很好地工作！簡單化可以使事情優化變得更容易。或者一個經典的網格方法。如果您的用戶傾向於將其註釋分散到一個區域中（而不是將它們全部放到一個位置），則可以計算整數x，y網格座標，然後對它們進行散列併爲每個網格單元格創建一個列表。

Answer 2

我不是iOS開發者，但我看着的文檔，發現這個：

MKMapView.annotationsInMapRect：

返回位於指定地圖矩形的註釋對象。

(NSSet *)annotationsInMapRect:(MKMapRect)mapRect

參數

• mapRect：你要搜索的註釋地圖的一部分。

返回值 的一套位於mapRect註釋對象。

討論 該方法提供了一種快速方法來檢索地圖特定部分中的註記對象。此方法比自己在註釋屬性中進行線性搜索要快得多。

這表明NKMapView已經在空間索引結構中組織了註釋。這種方法會滿足您的需求嗎？

如果沒有，我會尋找任何2D空間索引結構的現有開源實現，並選擇最佳文檔，最乾淨的接口等，而不是擔心效率。如果你需要從頭開始編寫代碼，我認爲四叉樹是最容易實現的。另一方面，the Wikipedia article on R-tree似乎更專門針對映射比K-D樹或四叉樹。