Given a polygon, created entirely from rectangles, and defined by an array of points, where the edges are always aligned with the axis:

I am trying to determine a quick algorithm to find a small number of rectangles which can fill in this shape. This is something I did by hand to show the collection of rectangles I am describing:

**EDIT:**

Here is some simple processing code to create this shape (well, close to it).

```
float[] xpts = {0, 50, 50, 100, 100, 150, 150, 250, 250, 300, 300, 325, 325, 300, 300, 250, 250, 210, 210, 250, 250, 125, 125, 25, 25, 50, 50, 0 };
float[] ypts = {100, 100, 80, 80, 10, 10, 80, 80, 75, 75, 80, 80, 200, 200, 300, 300, 275, 275, 260, 260, 200, 200, 270, 270, 165, 165, 125, 125};
void setup( )
{
size( 350, 350 );
}
void draw( )
{
stroke( 0 );
strokeWeight( 1.5 );
float px = xpts[0];
float py = ypts[0];
for (int i=1; i < xpts.length; i++)
{
float nx = xpts[i];
float ny = ypts[i];
line( px, py, nx, ny );
px = xpts[i];
py = ypts[i];
}
float nx = xpts[0];
float ny = ypts[0];
line( px, py, nx, ny );
}
```

## Best Solution

Build a KD-Tree using existing edges as the splitter planes and ignore regions that are completely outside of the polygon during recursion. The leaf nodes will then make up a rectangular decomposition.

Getting a good decomposition is simply a matter of which splitter to choose in each step of the recursion. You might wanna use a simple heuristic that halves the remaining area each step. If you want, you can also just try a few different splitters!

Here's some pseudo code: