find overlapping rectangles algorithm

Question

let's say I have a huge set of non-overlapping rectangle with integer coordinates, who are fixed once and for all

I have another rectangle A with integer coordinates whose coordinates are moving (but you can assume that its size is constant)

What is the most efficient way to find which rectangles are intersecting (or inside) A? I cannot simply loop through my set as it is too big. Thanks

edit : the rectangles are all parallel to the axis

Answer 1

Create a matrix containing "quadrant" elements, where each quadrant represents an N*M space within your system, with N and M being the width and height of the widest and tallest rectangles, respectively. Each rectangle will be placed in a quadrant element based on its upper left corner (thus, every rectangle will be in exactly one quadrant). Given a rectangle A, check for collisions between rectangles in the A's own quadrant and the 8 adjacent quadrants.

This is an algorithm I recall seeing recommended as a simple optimization to brute force hit-tests in collision detection for game design. It works best when you're mostly dealing with small objects, though if you have a couple large objects you can avoid wrecking its efficiency by performing collision detection on them separately and not placing them in a quadrant, thus reducing quadrant size.

Answer 2

Let your set of rectangle be (Xi1,Yi1,Xi2,Yi2) where i varies from 0 to N.

Rectangle A and B can NOT be intersecting if Ax1 > Bx2 || Ay1 < By2 || Bx1 > Ax2 || By1 < Ay2.

Create tree which is optimized for range/interval (For exa: segment tree or interval tree) See http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l5cs4235.pdf

Use this tree to find set of triangle while your triangle is changing coordinates.

Answer 3

Use an R+ tree, which is most likely precisely the specific tree structure you are looking for. R+ trees explicitly do not allow overlapping in the internal (non-leaf) structure in exchange for speed. As long as no object exists in multiple leaves at once, there is no overlap. In your implementation, rather than support overlap, whenever an object needs to be added to multiple leaves, just return true instead.

Here is a detailed description of the data structure, including how to manage rectangles: The R+-tree: A dynamic index for multi-dimensional objects

Answer 4

Interval Trees: Are BSTs designed with taking 'lo' value as key in an interval. So, for example if we want to insert (23, 46) in the tree, we'd insert it using '23' in the BST.

Also, with interval trees at each node, we keep the maximum endpoint (hi value) of the sub-tree rooted at that node.

This order of insertion allows us to search all 'R' intersections in R(logN) time. [We search for first intersection in logN time and all R in RlogN time] Please refer to interval trees documentation for how insert, search is done and details of complexity.

Now for this problem, we use an algorithm known as sweep-line algorithm. Imagine we have a vertical line (parallel to y-axis) which is sweeping the 2D space and in this process intersects with the rectangles.

1) Arrange rectangles in increasing order of x-cordinates (left-edge wise) either via priority queue or via sorting . Complexity NlogN if N rectangles.

2) As this line sweeps from left to right, following are the intersection cases:

• If line intersects the left side of a rectangle never seen, add the y co-ords of the rectangle's side to the interval tree. [say (x1,y1) and (x1,y2) are left edge co-ordinates of the rectangle add interval (y1, y2) to the interval tree] ---> (NlogN)

• Do a range search on the interval tree. [say (x1,y1) and (x1,y2) are left edge co-ordinates of the rectangle, take the interval (y1,y2) and do an interval intersection query on the tree to find all intersections] ---> RlogN (in practice)

• If line intersects the right side of a rectangle, remove it's y-coords from the interval tree as the rectangle is now processed completely. ----> NlogN

Total complexity : NlogN + RlogN

Answer 5

You can do a random "walking" algorithm ... basically create a list of neighbors for all your fixed position rectangles. Then randomly pick one of the fixed-position rectangles, and check to see where the target rectangle is in comparison to the current fixed-position rectangle. If it's not inside the rectangle you randomly picked as the starting point, then it will be in one of the eight directions which correspond to a given neighbor of your current fixed position rectangle (i.e., for any given rectangle there will be a rectangle in the N, NE, E, SE, S, SW, W, NW directions). Pick the neighboring rectangle in the closest given direction to your target rectangle, and re-test. This is essentially a randomized incremental construction algorithm, and it's performance tends to be very good for geometric problems (typically logarithmic for an individual iteration, and O(n log n) for repeated iterations).

Answer 6

Topcoder provides a way to determine if a point lies within a rectangle. It says that say we have a point x1,y1 and a rectangle. We should choose a random point very far away from current locality of reference in the rectangular co-ordinate system say x2,y2.

Now we should make a line segment with the points x1,y1 and x2,y2. If this line segment intersects odd number of sides of the given rectangle (it'll be 1 in our case, this method can be extended to general polygons as well) then the point x1,y1 lies inside the rectangle and if it intersects even number of sides it lies outside the rectangle.

Given two rectangles, we need to repeat this process for every vertex of 1 triangle to possibly lie in the second triangle. This way we'd be able to determine if two rectangles overlap even if they are not aligned to the x or y axis.