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

lookup table: users tend to go back to the same areas on the screen (so margins visit rate is usually low, and center visit rate is usually high). so we can use this knowledge to improve our performance.
after finding a point once (could be any other method of finding) you can cache the results as a list, and next time the user visits the same place, lookup would be O(1). of course you will need to dump the cache once a new shape was added.

another possibility is using Observer Pattern, each new shape will register itself in the needed points (this could be expensive, depending on how much shape insert is frequent...) and once the mouse is on this point, all it has to do is call whoever registered to this point.

third possibility is of course cutting down your search area like @user unknown suggested. this possibility can be combined with lookup table.

Answer 3

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.