.net - 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.