性能 – 在2d空间中查找矩形

我在2D空间中设置了各种大小的矩形.矩形的数量可以动态地从10变化到100 000,它们的位置以及它们的大小经常被更新.

您会建议在给定点(x,y)找到矩形的空间结构？假设搜索操作也经常执行(例如在鼠标移动时).如果您可以参考各种空间索引算法比较或比较它们的搜索/构建/更新性能 – 这将是可爱的.

我建议 R-Tree.它主要设计用于矩形(或N维轴对齐立方体).