Request a collection of rectangles to overlap the input rectangle

Question

In multidimensional space, I have a set of rectangles, all of which are aligned with the grid. (I use the word "rectangles" freely - in three-dimensional space they will be rectangular prisms.)

I want to request this collection for all rectangles that overlap the input rectangle.

What is the best data structure for storing a collection of rectangles? I will add rectangles and delete rectangles from the collection from time to time, but these operations will be infrequent. The operation I want to be fast is a request.

One solution is to save the corners of the rectangles in the list and perform a linear scan over the list, determine which rectangles overlap the query rectangle and skip those that do not.

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

I looked at the data structure of the R tree , but it contains a collection of points, not a set of rectangles, and I don’t see an obvious way to generalize it.

The coordinates of my rectangles are discrete if you find it useful.

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

Answer 1

Perhaps you can use KD-Trees , which can be used for rectangles according to the wiki page:

Options

Instead of dots

Instead of points, a kd tree may also contain rectangles or hyperrectangles [5]. A two-dimensional rectangle is considered a 4D object (xlow, xhigh, ylow, yhigh). Thus, finding a range becomes the problem of returning all the rectangles crossing the search rectangle. A tree is built the usual way with all the rectangles in the leaves. In the orthogonal search range, the opposite coordinate is used when comparing with the median. For example, if the current level is divided along xhigh, we check the minimum search coordinate of the rectangle. If the median is less than the minimum search coordinate of the rectangle, then in the rectangle the left branch can always intersect with the search rectangle and, therefore, there can be cropping. Otherwise, both branches must go through. See also the interval tree, which is a one-dimensional special case.

Answer 2

Let me call the original problem PN - where N is the number of measurements.

Suppose we know a solution for P1, a one-dimensional problem: find if the new interval overlaps with the given set of intervals.

Once we find out, we can check if the new rectangle overlaps with the collection of rectangles in each of the x / y / z projections.

So, the solution P3 is equivalent to P1_x AND P1_y AND P1_z.

For an effective solution to P1, we can use a sorted list. Each node in the list will include the coordinates and the number of opened-intetrvals-up-to-this-coord.

Suppose we have the following intervals: [1.5] [2.9] [3.7] [0.2]

then the list will look like this:

{0,1}, {1,2}, {2,2}, {3,3}, {5,2}, {7,1}, {9,0}

if we get a new interval, say [6,7], we will find the largest element in the list that is less than 6: {5,2} and smllest, which is more than 7: {9,0}.

So it’s easy to say that the new interval overlaps with the existing ones.

And a search in a sorted list is faster than a linear one :)

Answer 3

You must use some sort of separation method. However, since your problem is limited (you only use rectangles), the data structure may be slightly simplified. I did not think about it in detail, but something like this should work;)

Using a discrete value constraint - you can create a secondary tabular data structure in which you store discrete values ​​of the second dimension (87 possible values). Assume that these values ​​are planes perpendicular to this dimension. For each of these planes, you can save the rectangles that intersect these planes in this secondary table.

Similarly, for the third dimension, you can use another table with the same number of equally distributed values ​​as you need (1.8 million is too much, so you probably want to make it at least a couple of smaller values) and create a map of rectangles, which are between two selected values.

Given the query rectangle, you can query the first table in constant time to determine the set of tables that may intersect this query. Then you can execute another query in the second table and intersect the results from the first and second query results. This should narrow down the number of actual intersection tests that you should perform.