Effective point inside the borders of the rectangle

Question

I am working on a vector map editor, and I have a set of elements, each of which defines its own bounding box in the view. When the mouse moves, I want to select the first element whose bounding box contains the current location of the mouse. Right now I am using a simple list and browsing 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 the best algorithm / data structure for this?

Some additional restrictions / requirements :

• populating the data structure of the bounding fields should be relatively quick (since I need to do this every time the map moves or the scale or projection changes).
• The algorithm would have to find all the matching elements (and not just the first). The reason is that some elements of the map may have an irregular shape, so just matching with the bounding box is not strict enough. Then I will look at the list of matches and make an exact match.
• , in which the boxes were added to the set , you need to support it somehow - the map element that is drawn over another element should take priority when comparing their bounding fields.

Answer 1

After watching the books I found one answer in the book " Computational Geometry" (page 237 3. ^Th edition, 2008). This type of search is often referred to as a piercing query and is usually implemented using segment trees .

Difficulties:

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

Answer 2

x, . x, , .

: , , 100x100 . , :

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

(1,1), (1,2) (2,2) (2,3) x * y s 4 (1,1) → s, (1,2) → s,...

/, , . , , .

Answer 3

: , , ( , ). . ( ) , , , O (1). , .

Pattern , each new form is registered at the necessary points (this can be expensive, depending on how many inserts the form often ...), and as soon as the mouse is at this stage, all you need to do is call the person who registered at this point .

The third possibility is, of course, reducing your search area, as @user is unknown. this feature can be combined with a lookup table.