Find out if point is inside one of N (possibly overlapping) rectangles in less than O(N)

Question

I have an image, and I want to show tooltips when mouse moves over certain rectangular areas. The rectangular areas can be up to 1000. However, just checking each rectangle if the point is in it, which is O(N), makes the interface unresponsive when moving the mouse.

Is there a way to do it in less than O(N)? I can sort the rectangles beforehand (I'm assuming it would be needed). The rectangles might be (very rarely) overlapping, but no more than 4-5 rectangles can overlap the same area. In that case I might need to get a list of all the rectangles, but even just any of them would still be good enough.

But I'm assuming that this problem has already been solved by window managers, etc.

Answer 1

It sounds like you want to be storing your rectangles within an R-Tree and then querying that. There are a few implementations available:

• JTS Topology Suite (Java)
• Net Topology Suite (.Net)
• GeoTools (.Net)

Check out their STRtree classes.

Answer 2

A faster and simpler (though less memory efficient) method than a tree for images (and web pages that can be rendered onto reasonably small images) is to use a stencil. i.e. if you have an image of x by y pixels, create a two dimensional array of size x by y and populate it with your tool tip IDs. This has a search speed from pixel position to ID of O(1) (my favourite O)