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

Question

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

您会推荐哪种空间结构来在给定点 (x,y) 处找到矩形？假设搜索操作也经常执行(例如鼠标移动)。如果您可以在此处提供各种空间索引算法比较的引用或比较它们的搜索/构建/更新性能 - 那就太好了。

Answer 1

我会建议 R-Tree .它主要是为矩形(或 N 维轴对齐的立方体)设计的。