空間數據的數據結構

我正在尋找一個良好的功能數據結構來存儲空間（點）數據。數據結構應該允許對已經存在的點進行簡單的epsilon查詢。另外我需要經常修改數據。這意味着點可以移動並且應該能夠在數據結構中更新。這可能可以使用正常的刪除/添加來處理，但真正的移動可能會更快。空間數據的數據結構

現在我正在考慮使用quad/oct-trees（或更高版本），因爲移動部分應該很容易做到。然而，就平衡而言，四叉樹已知更糟糕。 KD-Trees可能是另一種選擇，但更新似乎相當惡劣。另外，我能找到的大多數空間數據結構實現都只是程序性的，而我正在使用一種功能性語言。

2011-06-15 LiKao

只是爲了澄清：是一個查詢查詢找到在給定點的指定距離內的點？ – aneccodeal 2011-06-15 15:40:16

KD樹或四核/月樹是合理的選擇。在Haskell

實例：

兩者都是很簡單的編碼爲純功能的數據結構。

2011-06-15 21:05:44

根據你如何使用它並快速移動點，你可能也會考慮sweep and prune。基本上，你保持點在一個維度排序（如x）。如果點很少改變位置，爲每個模擬步驟運行插入排序實際上會很快。

（我想你的兩個建議都已經相當不錯了，順便說一句）

2011-06-15 11:51:46

R-Trees和R * -Trees也是另一種解決方案，易於實現。

我在避難仿真中使用它們，更新步驟並沒有那麼慢。

2011-06-21 15:14:04 cynddl

看起來相當不錯，雖然我不得不修理一些東西才能在這裏工作。謝謝您的幫助... – LiKao 2011-07-03 13:17:03

This old paper作者：Overmars和van Leeuwen描述了僞四叉樹 - 一種四叉樹，它也可以平衡自己的插入和刪除進度。插入和刪除的攤銷成本類似於O(log^d(n))，甚至可以與平衡完成量進行交易（您可以在論文中閱讀更多關於此的內容）。

2011-06-21 20:04:45 axel22

回答