# Filling a rectilinear polygon with rectangles

algorithmgeometry

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:

``````function makeRects(Rect r, Polygon p)

if p is empty
if r is inside your original polygon

else
choose good splitter s

makeRects(left part of r relative to s, left part of p relative to s)
makeRects(right part of r relative to s, right part of p relative to s)
``````