Efficient algorithm to return all rectangles to the surface
One critical piece of code in my application involves listing all rectangles on a 2D surface. The rectangles do not intersect with each other and I should be able to list all rectangles within a given rectangular border.
I already have a function to return a rectangle for a given coordinate if it exists
GetRectangle( int row, int col )
This is what I would call the resulting code.
foreach( var rect in GetRectangles( row, col, rowCount, colCount ) ) {
//.. my processing code here
}
Obviously, I could call a function GetRectangle()
for each of the points on the surface. I can also skip the width of the rectangle that was returned from a previous call, since I know they don't intersect. But this is not yet effective enough.
Do you know about this algorithm?
UPDATE: The surface is not necessarily covered with rectangles, but it might be for some special cases. Thus, the function GetRectangle( int row, int col )
can return null.
Think of a surface as a waste filled with random rectangles (that don't overlap). The challenge is to return all rectangles on this surface that fall within (i.e. intersect) the given frame. Hope this clears up the question.
thank
source to share
For best results, organize your collection of rectangles into a spatial search structure . In this case, it sounds like an R-tree would be a good bet. But if you can't do it, and GetRectangle
that's all you have, here's what I do:
The plan is to keep a list of integers x jfor 0 ≤ j < rowCount
, where x j is the leftmost point in line j for which I have not yet found a rectangle covering it.
-
Start by initializing x j: = 0 for all j.
-
If x j=
colCount
for all j, we're done. Stop. -
Let J = min (j | x j= min (x i)). Then x J is the top-left point at which I have not yet found the rectangle that covers it.
-
Call
GetRectangle
(x J, J). If this does not return a rectangle, then the point was not found. Install x J: = x J + 1 and go to step 2. -
Otherwise, we have a rectangle with the upper left corner at (x J, J). Call its width w and height h. For J ≤ j <J + h, set x j: = x j+ w. Go to step 2.
Here is an example of this algorithm. List x jshown in numbers on the left, with the top-most left in bold. The orange rectangle is the one that was found at this stage of the algorithm.
For efficiently detecting the minimum in step 3, you can keep the list x jin the heap .
source to share