插入/更新/刪除和搜索2d點的最佳數據結構

Question

我有一個用於GIS地圖上海量實體的基礎結構 - 使用圖形卡進行繪製（WebGL）。

今天，我使用四叉樹索引數據和查詢 - 用於選擇/繪圖的目的。

最近我找到了一種方法來讓我的用戶能夠更新實體的位置並且非常快速地繪製出變化。例如更新15000個位置，重繪時間少於0.05毫秒。

現在的問題是更新我的數據結構。這是非常非常緩慢的。

我已經運行了許多數據結構，例如R樹，B樹等等，但還沒有找到滿意的結果。

我的問題是

什麼是2D點的最優數據結構但從性能點，用於插入/更新和查詢（從點由距離，矩形）？

也許有一個網絡gl解決方案呢？

Answer 1

什麼是2D點的最優數據結構從性能 的觀點來看，用於插入/更新和查詢（從 點由距離，矩形）？

很難找到滿足所有這些要求的數據結構。通常情況下，搜索速度最快，插入速度要慢一些，插入速度更快，搜索速度要慢一些，所以這是一種平衡的行爲。

但是，根據您的需要，一個簡單的NxM網格實際上可能是理想的。我最初來自遊戲背景，每個單幀都可以移動精靈。四叉樹通常對於想要在每一幀更新結構的動態內容來說太昂貴。因此，對於這些情況，簡單的NxM網格通常效果更好。

NxM網格可以做一個矩形查詢甚至可能比四叉樹更快，因爲它只需確定哪些網格單元與矩形重疊，然後只需檢查單元內的元素以查看重疊/是否在內部矩形。在徑向參數（圓圈）內進行搜索也一樣。

因爲我們只需要更新元素重疊的單元格，所以插入和刪除很便宜。如果你正在處理積分，一個點只屬於一個單元格，並且它變成一個非常簡單的常量操作。實際上，如果每個點爲下一個元素存儲一個列表指針，將它從一個單元格移動到另一個單元格（以及將它從單元格中移出並將其插入單元格）只需要更改指針周圍 - 不需要分配內存。然後網格成爲一個單鏈表頭指針的網格。

另一種方法是，我想你目前正在爲整個世界使用一個巨大的四叉樹。您可以通過使用四叉樹表示一個小區域來使用這些技術的混合，例如，將四叉樹拼接在一起形成四叉樹網格。這可以顯着降低爲特定區域更新四叉樹的成本，因爲每個四叉樹只存儲該區域的數據。