Find a rectangle in an array with [x,y] point

Question

I'll do my best to make my case scenario simple.

1-) Let's suppose we need to stores a lot of rectangles in some kind of array/data structure. Each rectangle are of different sizes and are positioned at various parts of the screen. Rectangles can't overlap together.

2-) Then we click on the screen with the mouse at point [x,y].

Now, we need to determine if we clicked on a part of one of the rectangles. Well, that would be insane to iterate through all the rectangles to make some kind of comparisons, especially if there is a huge number of them.

What would be the fastest technique/algorithm to do it with as little steps as possible? What would be the best data structure to use in such case?

Answer 1

One way would be to use a quadtree to store the rectangles: The root represents the whole area that contains all rectangles, and this area is then recursively subdivided as required.
If you want to test if a certain coordinate is within one of the rectangles, you start at the root, and walk down the tree until either you find a rectangle or not.
This can be done in O(log n) time.