algorithm - 保存矩形列表的数据结构？

Question

我想知道是否有一个好的数据结构来保存轴对齐的非重叠离散空间矩形列表。因此，每个矩形都可以存储为整数 x、y、宽度和高度。只存储这样一个列表很容易，但我也希望能够查询给定的 x,y 坐标是否在任何其他矩形内。

一个简单的解决方案是创建一个散列并用每个矩形开始的散列左下坐标填充它。这不允许我测试给定的 x,y 坐标，因为它会碰到中间的空白空间。另一个答案是在散列表中创建一堆边，用单位正方形覆盖整个矩形。这会为 100 x 100 的矩形创建太多不必要的条目。

Answer 1

R-Tree 是可以用的。R-树是用于空间访问方法的树数据结构，即用于索引多维信息，例如地理坐标、矩形或多边形。所有矩形的信息都可以以树的形式存储，因此搜索会很容易

维基百科页面、简短的 ppt和研究论文将帮助您理解这个概念。