存储矩形列表的数据结构？

Question

8

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

一个简单的解决方案是创建一个哈希表，并用每个矩形开始的哈希后的左下坐标填充它。这将无法让我测试给定的x、y坐标，因为它会碰到中间的空白区域。另一个答案是创建一堆边缘进入哈希表，用单位正方形覆盖整个矩形。这会为一个例子为100乘100的矩形创建太多不必要的条目。

- Michael

我不确定当插入一个新的矩形与树的分割线重叠时会如何运作。我想我可以将该矩形分割，但在退化情况下，我们会得到像哈希表一样糟糕的结果，并且插入时间为log(n)。或者我有什么误解吗？ - Michael

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tejas Patil · Accepted Answer

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