use*_*928 5 algorithm search geometry data-structures
在多维空间中，我有一组矩形，所有矩形都与网格对齐。（我宽松地使用“矩形”这个词 - 在三维空间中，它们将是矩形棱柱。）
我想查询此集合中与输入矩形重叠的所有矩形。
保存矩形集合的最佳数据结构是什么？我会不时地向集合中添加矩形或从集合中删除矩形，但这些操作并不频繁。我想要快速的操作是查询。
一种解决方案是将矩形的角保留在列表中，并对列表进行线性扫描，查找哪些矩形与查询矩形重叠，并跳过不重叠的矩形。
但是，我希望查询操作比线性更快。
我研究过R 树数据结构，但它保存的是点的集合，而不是矩形的集合，而且我没有看到任何明显的方法来概括它。
我的矩形的坐标是离散的，以防您发现有帮助。
我对通用解决方案感兴趣，但我也会告诉您我的具体问题的属性：我的问题空间具有三个维度，并且它们的多重性变化很大。第一个维度有两个可能的值，第二个维度有 87 个值，第三个维度有 180 万个值。
小智 4
您可能可以使用KD-Trees，根据 wiki 页面，它可用于矩形：
变化
而不是积分
除了点之外，kd 树还可以包含矩形或超矩形[5]。2D 矩形被视为 4D 对象（xlow、xhigh、ylow、yhigh）。因此范围搜索就变成了返回与搜索矩形相交的所有矩形的问题。这棵树是按照通常的方式构建的，所有矩形都位于叶子上。在正交范围搜索中，与中位数进行比较时使用相反的坐标。例如，如果当前级别沿 xhigh 分割，我们检查搜索矩形的 xlow 坐标。如果中值小于搜索矩形的 xlow 坐标，则左分支中的任何矩形都不能与搜索矩形相交，因此可以被修剪。否则，应遍历两个分支。另请参见区间树，它是一维特例。