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

I'll bet you could use some kind of derivation of a quadtree to do this. Take a look at this example.

Answer 2

Personally, I would solve this with a KD-Tree or a BIH-Tree. They are both adaptive spatial data structures that have a log(n) search time. I have an implementation of both for my Ray Tracer, and they scream.

-- UPDATE --

Store all of your fixed rectangles in the KD-Tree. When you are testing intersections, iterate through the KD-Tree as follows:

function FindRects(KDNode node, Rect searchRect, List<Rect> intersectionRects)

// searchRect is the rectangle you want to test intersections with
// node is the current node. This is a recursive function, so the first call
//    is the root node
// intersectionRects contains the list of rectangles intersected

int axis = node.Axis;

// Only child nodes actually have rects in them
if (node is child)
{
    // Test for intersections with each rectangle the node owns
    for each (Rect nRect in node.Rects)
    {
        if (nRect.Intersects(searchRect))
              intersectionRects.Add(nRect);
    }
}
else
{
    // If the searchRect's boundary extends into the left bi-section of the node
    // we need to search the left sub-tree for intersections
    if (searchRect[axis].Min  // Min would be the Rect.Left if axis == 0, 
                              // Rect.Top if axis == 1
                < node.Plane) // The absolute coordinate of the split plane
    {
        FindRects(node.LeftChild, searchRect, intersectionRects);
    }

    // If the searchRect's boundary extends into the right bi-section of the node
    // we need to search the right sub-tree for intersections
    if (searchRect[axis].Max  // Max would be the Rect.Right if axis == 0
                              // Rect.Bottom if axis == 1
                > node.Plane) // The absolute coordinate of the split plane
    {
        FindRects(node.RightChild, searchRect, intersectionRects);
    }
}

This function should work once converted from pseudo-code, but the algorithm is correct. This is a log(n) search algorithm, and possibly the slowest implementation of it (convert from recursive to stack based).

-- UPDATE -- Added a simple KD-Tree building algorithm

The simplest form of a KD tree that contains area/volume shapes is the following:

Rect bounds = ...; // Calculate the bounding area of all shapes you want to 
              // store in the tree
int plane = 0; // Start by splitting on the x axis

BuildTree(_root, plane, bounds, insertRects);

function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)

if (insertRects.size() < THRESHOLD /* Stop splitting when there are less than some
                                      number of rects. Experiment with this, but 3
                                      is usually a decent number */)
{
     AddRectsToNode(node, insertRects);
     node.IsLeaf = true;
     return;
}

float splitPos = nodeBds[plane].Min + (nodeBds[plane].Max - nodeBds[plane].Min) / 2;

// Once you have a split plane calculated, you want to split the insertRects list
// into a list of rectangles that have area left of the split plane, and a list of
// rects that have area to the right of the split plane.
// If a rect overlaps the split plane, add it to both lists
List<Rect> leftRects, rightRects;
FillLists(insertRects, splitPos, plane, leftRects, rightRects); 

Rect leftBds, rightBds; // Split the nodeBds rect into 2 rects along the split plane

KDNode leftChild, rightChild; // Initialize these
// Build out the left sub-tree
BuildTree(leftChild, (plane + 1) % NUM_DIMS, // 2 for a 2d tree
          leftBds, leftRects);
// Build out the right sub-tree
BuildTree(rightChild, (plane + 1) % NUM_DIMS,
          rightBds, rightRects);

node.LeftChild = leftChild;
node.RightChild = rightChild;

There a bunch of obvious optimizations here, but build time is usually not as important as search time. That being said, a well build tree is what makes searching fast. Look up SAH-KD-Tree if you want to learn how to build a fast kd-tree.