Efficient point inside rectangle boundaries search

Question

I'm working on a vector map editor and I have a set of elements, each of which specifies its bounding box within the view. As the mouse moves I want to highlight the first element whose bounding box contains the current mouse location. Right now I use a simple list and go through it, but as the number of elements is likely to increase, the O(n) complexity of the current search algorithm will be problematic for an interactive application.

What would be a better algorithm/data structure for this?

Some additional constraints/requirements:

• The filling of the bounding boxes data structure would have to be relatively quick (since I need to do that each time the map moves or the zoom or projection changes).
• The algorithm would have to be able to find all of the matching elements (not just the first one). The reason is that some map elements can have irregular shape, so the simple bounding box match is not strict enough. I would then go through the list of matches and do some precise matching.
• The order in which the boxes were added to the set needs to be maintained somehow - a map element which is drawn above another element should have a priority when matching their bounding boxes.

Answer 1

After browsing through books, I've found one answer in Computational Geometry book (p. 237 in 3^rd edition; 2008). This type of search is often referred to as stabbing query and is usually implemented using segment trees.

Complexities:

• The query: O(log2n + k), where k is the number of reported bounding boxes
• The data structure uses O(n*log n) storage
• The structure can be built in O(n*log n) time

Answer 2

If you sort your elements by lower x-location, you can skip all elements before a certain point. If you have a second list with upper x-location, you know when you're done.

Another idea: Create a grid maybe splitting the whole area into 100x100 parts. Now find once out, in which parts of your grid a figure is overlapping:

5
4
3    xx 
2  xxxx
1  xx
0
 0 1 2 3 4 5 

For this figure it would be (1,1),(1,2)(2,2)(2,3) A map of x*y Lists would now contain this shape s for the 4 locations (1,1)->s, (1,2)->s, ...

If you have seldom insertions/deletions, but often comparisions, this would speed your searches up. You would only visit the shapes, associated to a certain cell, and investigate the exact coordinates for these.