Algorithm for hit test in non-overlapping rectangles

Question

I have a collection of non-overlapping rectangles that cover an enclosing rectangle. What is the best way to find the containing rectangle for a mouse click?

The obvious answer is to have an array of rectangles and to search them in sequence, making the search O(n). Is there some way to order them by position so that the algorithm is less than O(n), say, O(log n) or O(sqrt(n))?

Answer 1

You can organize your rectangles in a quad or kd-tree. That gives you O(log n). That's the mainstream method.

Another interesting data-structure for this problem are R-trees. These can be very efficient if you have to deal with lots of rectangles.

http://en.wikipedia.org/wiki/R-tree

And then there is the O(1) method of simply generating a bitmap at the same size as your screen, fill it with a place-holder for "no rectangle" and draw the hit-rectangle indices into that bitmap. A lookup becomes as simple as:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

Obviously that method only works well if your rectangles don't change that often and if you can spare the memory for the bitmap.

Answer 2

Create an Interval Tree. Query the Interval Tree. Consult 'Algorithms' from MIT press.

An Interval Tree is best implemented as a Red-Black Tree.

Keep in mind that it is only advisable to sort your rectangles if you are going to be clicking at them more then you are changing their positions, usually.

You'll have to keep in mind, that you have build build your indices for different axis separately. E.g., you have to see if you overlap an interval on X and on Y. One obvious optimization is to only check for overlap on either X interval, then immediately check for overlap on Y.

Also, most stock or 'classbook' Interval Trees only check for a single interval, and only return a single Interval (but you said "non-overlapping" didn't you?)

Answer 3

Shove them in a quadtree.

Answer 4

Use a BSP tree to store the rectangles.