# 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.

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

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 .

+3

source

All Articles