filling a rectilinear polygon with rectangles [dup

Question

This question already has an answer here:

• Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping 2 answers

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 );
}

Answer 1

Sounds a lot like a NP problem to me. That means, there are certainly a couple of algorithms that can quickly fill your shape with rectangles, if the number of rectangles doesn't really matter to you, but if you insist on the smallest number, then you better forget about the word "quick". Actually you should even forget about the word "smallest" and instead use "small", since determining if the set is smallest could already be a huge problem for the algorithm.

Answer 2

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)

Answer 3

Interesting discussion & solution here: http://www.gamedev.net/topic/460561-decomposing-a-rectilinear-polygon/