Search code examples
algorithmgraphicscomputational-geometrygraph-algorithmnp

Filling rectilinear polygon (with holes) with rectangles

I read that it is NP problem.

But I don't need the smallest number of rectangles. Just "more or less" good algorithm.

So, the problem.

I have a binary pixel matrix, similar to this: http://en.wikipedia.org/wiki/Connected-component_labeling#mediaviewer/File%3aScreenshot-Pixel_Region_%28Figure_1%29.png

I need to fill 1's. I can't draw pixel by pixel. What I planned to do is to cover region with rectangles and fill rectangles.

Can somebody help me?

Solution

  • Problem is polynomial in 2D case, but NP-complete in 3D. It is shown in this paper.

    Idea of algorithm, for 2D case, is to reduce problem to maximum matching of bipartite graph (vertices are possible cuts.) Take a look on this page or this presentation.