For a 2D game I am working on, I am using y axis sorting in a simple rectangle-based collision detection. This is working fine, and now I want to find the nearest empty rectangle at a given location with a given size, efficiently. How can I do this? Is there an algorithm?
I could think of a simple brute force grid test (with each grid the size of the empty space we're looking for) but obviously this is slow and not even a complete test.
Consider using quad-trees to store your rectangles. See http://en.wikipedia.org/wiki/Quadtree for more information.
If you're already using axis sorting, then presumably you've computed a list of your rectangles sorted by their positions.
Perhaps I am misunderstanding, but could you not 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, then you could simply walk through the list until you find the first rectangle with a greater position than your arbitrary point, and use that rectangle and the one before it as the two to compare.