查询矩形的集合为一个输入矩形的重叠 [英] Querying a collection of rectangles for the overlap of an input rectangle

问题描述

在一个多维空间中，我有矩形的集合，所有这些都与网格对齐。 （我用的是矩形宽松 - 在一个三维空间中，他们将直角棱镜）

In a multi-dimensional space, I have a collection of rectangles, all of which are aligned to the grid. (I am using the word "rectangles" loosely - in a three dimensional space, they would be rectangular prisms.)

我要查询该集合重叠的输入矩形所有的矩形。

I want to query this collection for all rectangles that overlap an input rectangle.

什么是最好的数据结构保持矩形的集合？我会增加矩形，并从集合删除矩形不时，但这些操作将是罕见的。我想快的操作是查询。

What is the best data structure for holding the collection of rectangles? I will be adding rectangles to and removing rectangles from the collection from time to time, but these operations will be infrequent. The operation I want to be fast is the query.

的一个解决方案是要保持在一个列表中的矩形的角落，并做了线性扫描在列表中，发现其中的矩形重叠查询矩形和跳过的那些没有

One solution is to keep the corners of the rectangles in a list, and do a linear scan over the list, finding which rectangles overlap the query rectangle and skipping over the ones that don't.

不过，我想查询操作会比直线速度快。

However, I want the query operation to be faster than linear.

我看了看 R树的数据结构，但它持有收集点，矩形不是集合，而且我也看不到任何明显的方法来概括它。

I've looked at the R-tree data structure, but it holds a collection of points, not a collection of rectangles, and I don't see any obvious way to generalize it.

我的矩形的坐标是不连续的，如果你发现有帮助的。

The coordinates of my rectangles are discrete, in case you find that helpful.

我感兴趣的是通用的解决方案，但我还会告诉你我的具体问题的性质：我的问题空间是三维的，而他们的疯狂多样性变化。第一维度有两个可能的值，所述第二维具有87的值，以及第三维具有180万的值。

I am interested in the general solution, but I will also tell you the properties of my specific problem: my problem space has three dimensions, and their multiplicity varies wildly. The first dimension has two possible values, the second dimension has 87 values, and the third dimension has 1.8 million values.

推荐答案

您也许可以使用 KD- 的可以根据wiki页面用于矩形树木：

You can probably use KD-Trees which can be used for rectangles according to the wiki page:

变体形式

而不是点

相反的点，一个kd树也可以   包含矩形或   hyperrectangles [5]。二维矩形   考虑四维对象（超低，xhigh，   ylow，yhigh）。因此范围搜索   就返回所有的问题   矩形交叉搜索   矩形。树的建造   与所有的矩形在通常的方式   叶子。在正交范围   搜索，相反的坐标是   对比较时使用   中位数。例如，如果当前   级别沿xhigh分裂，我们检查   搜索的xlow坐标   矩形。如果中值小于   搜索的xlow坐标   矩形，那么没有在矩形   左支都不能相交   搜索矩形，这样可以   修剪。另外两个分支应   遍历。另请参阅区间树，   它是一个一维的特例。

Instead of points, a kd-tree can also contain rectangles or hyperrectangles[5]. A 2D rectangle is considered a 4D object (xlow, xhigh, ylow, yhigh). Thus range search becomes the problem of returning all rectangles intersecting the search rectangle. The tree is constructed the usual way with all the rectangles at the leaves. In an orthogonal range search, the opposite coordinate is used when comparing against the median. For example, if the current level is split along xhigh, we check the xlow coordinate of the search rectangle. If the median is less than the xlow coordinate of the search rectangle, then no rectangle in the left branch can ever intersect with the search rectangle and so can be pruned. Otherwise both branches should be traversed. See also interval tree, which is a 1-dimensional special case.

这篇关于查询矩形的集合为一个输入矩形的重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！