我應該如何索引一個簡單的矩形世界？

Question

世界由許多（1k-10k）大小相似的矩形組成，我需要能夠在嘗試添加新的矩形時快速確定潛在的重疊。矩形將被動態添加和刪除。 R-Trees在這裏適合嗎？如果是這樣，我應該考慮哪些好的圖書館？ （我接受任何語言的建議）。

Answer 1

R-Trees應該是合適的，是的。

quad trees也是一個很好的數據結構，用於快速查找2D空間區域中的對象。它們實際上是一種更加統一的r-樹版本。使用這些結構，即使使用海量數據集，您也可以在很小的空間區域內進行快速歸零，只需很少的測試。

有一個c＃實現here，雖然我沒有看過它。

這種數據結構（和它的3D版本叫Octrees）通常用於遊戲來管理對象的大型數據集，這些數據集需要知道它們是否靠近任何其他碰撞測試對象以及其他類型的其他對象有趣的原因。

你應該能夠找到大量的文章和這些類型的遊戲行業站點的數據結構的例子像gamasutra和opengl.org

Answer 2

您還可以仰望kd-trees。

我不知道任何實現，但在3D中，至少他們通常被認爲比八叉樹更高性能。例如，這裏是經驗的迴歸I just googled it。

如果您遇到性能問題，您可能需要考慮替代四叉樹。

但是應該注意的是kd-tree很難重新平衡......