how to calculate many rectangles/boxes intersection

Question

I have many rectangles in 2D (or have many boxes in 3D).

The rectangle can be described by coordinate (xD,yD,xB,yB).

  A-----B
  |     |
  |     |
  D-----C

I want to obtain the intersection adjacency graph of these rectangles/boxes.

I am now using O(n^2) way to implement.

AdjacencyGraph graph(n);
for (int i=0;i<n;i++)
{
   for (int j=i+1;j<n;j++)
   {
       if (isItersection(boxes[i],box[j]))
       {
             graph.flagEdge(i,j);
             graph.flagEdge(j,i);
       }
   }
}

But this way is very slow. Is there any fast algorithm that can accelerate this process?

Answer 1

1) If box sizes are not equal:

• Sort boxes on X-axis
• Generate 1D adjacency list for each box, by comparing only within range (since it is 1D and sorted, you only compare the boxes within range) like [(1,2),(1,3),(1,5),....] for first box and [(2,1),(2,6),..] for second box, etc. (instead of starting from index=0, start from index=current and go both directions until it is out of box range)
• Iterate over 1D adjacency list and remove duplicates or just don't do the last step on backwards (only compare to greater indexed boxes to evade duplication)
• Group the adjacencies per box index like [(1,a),(1,b),..(2,c),(2,d)...]
• Sort the adjacencies within each group, on Y-axis of the second box per pair
• Within each group, create 2D adjacency list like [(1,f),(1,g),..]
• Remove duplicates
• Group by first box index again
• Sort (Z) of second box per pair in each group
• create 3D adjacency list
• remove duplicates
• group by first index in pairs
• result=current adjacency list (its a sparse matrix so not a full O(N*N) memory consumption unless all the boxes touch all others)

So in total, there are:

• 1 full sort (O(N*logN))
• 2 partial sorts with length depending on number of collisions
• 3 lumping pairs together (O(N) each)
• removing duplicates (or just not comparing against smaller index): O(N)

this should be faster than O(N^2).

---

2) If rectangles are equal sized, then you can do this:

• scatter: put box index values in virtual cells of a grid (i.e. divide the computational volume into imaginary static cells & put your boxes into a cell that contains the center of selected box. O(N)

• gather: Only once per box, using the grid cells around the selected box, check collisions using the index lists inside the cells. O(N) x average neighbor boxes within collision range

---

3) If rectangles are not equal sized, then you can still "build" them by multiple smaller square boxes and apply the second (2) method. This increases total computation time complexity by multiplication of k=number of square boxes per original box. This only requires an extra "parent" box pointer in each smaller square box to update original box condition.

This method and the (2) method are easily parallizable to get even more performance but I guess first(1) method should use less and less memory after each axis-scanning so you can go 4-dimension 5-dimension easily while the 2-3 methods need more data to scan due to increased number of cell-collisions. Both algorithms can become too slow if all boxes touch all boxes.

---

4) If there is "teapot in stadium" problem (all boxes in single cell of grid and still not touching or just few cells close to each other)

• build octree from box centers (or any nested structure)
• compute collisions on octree traversal, visiting only closest nodes by going up/down on the tree

---

1-revisited) If boxes are moving slowly (so you need to rebuild the adjacency list again in each new frame), then the method (1) gets a bit more tricky. With too small buffer zone, it needs re-computing on each frame, heavy computation. With too big buffer zone, it needs to maintain bigger collision lists with extra filtering to get real collisions.

---

2-revisited) If environment is infinitely periodic (like simulating Neo trapped in train station in the Matrix), then you can use grid of cells again, but this time using the wrapped-around borders as extra checking for collisions.

---

For all of methods (except first) above, you can accelerate the collision checking by first doing a spherical collision check (broad-collision-checking) to evade unnecessary box-collision-checks. (Spherical collision doesn't need square root since both sides have same computation, just squared sum of differences enough). This should give only linear speedup.

For method (2) with capped number of boxes per cell, you can use vectorization (SIMD) to further accelerate the checking. Again, this should give a linear speedup.

For all methods again, you can use multiple threads to accelerate some of their steps, for another a linear speedup.

Even without any methods above, the two for loops in the question could be modified to do tiled-computing, to stay in L1 cache for extra linear performance, then a second tiling but in registers (SSE/AVX) to have peak computing performance during the brute force time complexity. For low number of boxes, this can run faster than those acceleration structures and its simple:

select a group of boxes n=multiple of 8
    select another group of boxes n=multiple of 8
        iterate first group 8 by 8
            iterate second group 8 by 8
            Only rotate the vector to scan all 8 elements (64 collision checks for each 2 vectors)
        write results for 8 boxes in first group

Are coordinates only 16bit integers? Then you can cache each collision result using hash(distanceX,distanceY,distanceZ,sizeXYZ) as keys and true/false as values.

So, solution depends on your problem. What is N? Do the boxes overlap much? Do they lump together in a big environment or do they stay sparse? How many cores in system? How much memory? Are the boxes moving and how fast? What are your run-time expectations for how many boxes?

Edit: I tried to write an adaptive-grid (optimized the second method against "teapot in stadium" problem a bit) in less than 500 lines of codes: https://github.com/tugrul512bit/FastCollisionDetectionLib

It is not optimized to lower the buffer-allocation overhead, not multithreaded and not vectorized but it scales up linearly for uniformly distributed particles and close to linear when some of particles lumped together 100x far from center of mass. It is hundreds to thousands of times faster than the brute force method depending on number of particles between 20k and 100k. Also did not test it for unequal shaped boxes, only identical boxes.

Answer 2

For a first, simple solution, you can store the boxes as pairs of triples (Y, Xleft, Xright) with a flag to distnguish between top and bottom Y. [As the X are duplicated, you can reserve some special value to make the distinction.]

Then sort on Y and scan by increasing Y, while you maintain an "active list". When you meet a top triple, insert it to the active list, and for a bottom, remove. Now you have a 1D interval overlap problem.

Similarly as above, you can enter the intervals in the active list as two distinct entries, Xleft and Xright plus a flag. After sorting left-to-right, you scan the active list to get the overlapping intervals, by means of a secondary active list. You can sort explicitly, or maintain the lists sorted by using an ordered set.

---

The 3D case is similar, but with one more stage. You first sort on Z, and the active list will be made of 2D rectangles, and you use the above procedure on it.