Clever Geek Handbook

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

+3


source to share


1 answer


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.

The algorithm finds seven rectangles in seven steps

For efficiently detecting the minimum in step 3, you can keep the list x jin the heap .

+3


source






More articles:


All Articles