What is an effective way to find a non-colliding rectangle closest to a location

Question

For the 2D game I'm working on, I use y-axis sorting in simple rectangle-based collision detection. This works fine, and now I want to find the effective empty nearest empty rectangle in the given location with the given size. How can i do this? Is there an algorithm?

I could come up with a simple brute force grid test (with each grid the size of the empty space we are looking for), but obviously this is a slow and not even a complete test.

Answer 1

Consider using quad trees to store your rectangles. See http://en.wikipedia.org/wiki/Quadtree for more details.

Answer 2

If you already use sorting by axes, then presumably you have calculated a list of your rectangles sorted by their positions.

Perhaps I misunderstand, but could you just look at the two rectangles before and after the rectangle in question and decide which one is closer? If you're talking about finding the closest rectangle to an arbitrary point, you can just go through the list until you find the first rectangle with a larger position than your arbitrary point, and use this rectangle and the one in front of it as two for comparison.