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

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.