Заполнение прямолинейного многоугольника (с отверстиями) с прямоугольниками

Question

Я прочитал, что это проблема NP.

Но мне не нужно наименьшее количество прямоугольников. Просто «более или менее» хороший алгоритм.

Итак, проблема.

У меня есть бинарная матрица пикселей, похожее на это: http://en.wikipedia.org/wiki/Connected-component_labeling#mediaviewer/File%3aScreenshot-Pixel_Region_%28Figure_1%29.png

Мне нужно заполнить 1-х. Я не могу рисовать пиксель за пикселем. То, что я планировал сделать, - это охватить область прямоугольниками и заполнить прямоугольники.

Может кто-нибудь мне помочь?

Answer 1

Проблема полиномиальная в 2D-корпусе, но NP-полная в 3D. Это показано в этом paper.

Идея алгоритма для двумерного случая состоит в том, чтобы уменьшить проблему до максимального соответствия двухстороннего графа (вершины возможны разрезы.) Посмотрите на это page или на этот presentation.