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:

a polygon created entirely from intersecting rectangles

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:a polygon created entirely from intersecting rectangles filled with non-overlapping rectangles

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
      add r to results

  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)

Splitters for the OPs sample decomposition

Related Question