performance - 在二维空间中查找矩形

Question

我在二维空间中有一组不同大小的矩形。矩形的数量可以从 10 到 100 000 动态变化，它们的位置以及它们的大小经常更新。

你会推荐哪种空间结构在给定点 (x,y) 找到矩形？假设搜索操作也经常执行（例如鼠标移动）。如果您可以参考各种空间索引算法比较或在这里比较它们的搜索/构建/更新性能 - 那会很可爱。

Answer 1

我建议R-Tree。它主要设计用于矩形（或 N 维轴对齐的立方体）。

Answer 2

使用四叉树 ( http://en.wikipedia.org/wiki/Quadtree )。

确定矩形开始和结束的所有可能的 X 和 Y 值。然后在这些值上构建一个四叉树。在四叉树的每个叶子中，存储哪些矩形与叶子的坐标范围重叠。找到哪些矩形重叠只是找到包含坐标的叶子的问题。