algorithm - 查找包含点的矩形 - 高效算法

Question

下午好。

我的情况:

• 在二维空间。
• 输入:一组矩形(重叠矩形)。
  • 矩形坐标是整数类型。
  • 对矩形大小和矩形位置没有任何限制(仅限整数范围)。
  • 没有矩形的 width=0 或 height=0。
• 我需要找到:包含输入的点(具有整数坐标)的所有矩形。

问题:

• 保留矩形的有效结构是什么？
• 在这种情况下哪种算法最有效？
  • 什么算法只对添加矩形而不删除矩形有效？

谢谢 :-).

Answer 1

R-Tree 是适合此用例的最佳数据结构。R-tree 是用于空间访问方法的树数据结构，即用于索引多维信息，例如地理坐标、矩形或多边形。所有矩形的信息都可以树形存储，方便查找

Wikipedia页，short ppt和 research paper将帮助您理解这个概念。