Алгоритм поиска пустых прямоугольников?

Вроде бы, всё просто. Никакой NP-полноты.

1. Разбить, как вы и описали, по гайдам на мелкие. Это максимальное число полигонов.
   
2. Взять любой, и начать присоединять к нему смежные, насколько возможно.
   
3. Взять следующий пустой не затронутый.
   
4. Процесс останавливается, когда больше ни к одному 4-угольнику нельзя присоединить еще один.
   

Поверхностно кажется, что так получится наименьшее возможное число. Хотя не гарантируется максимизация площадей. Хотя, пожалуй, такой подход может не найти оптимальный вариант, когда границы нескольких исходных блоков легли точно на одной линии. Тогда выиграет вариант, захватывающий обе пустоты. Представьте силуэт буквы «Т». Его можно замостить всего двумя прямоугольниками. Но алгоритм может прозевать такую возможность и предложить 3 блока.

Представьте себе Г-образный набор блоков. Как ни крути, там не менее 2 в итоге получится. Заметьте, что в обоих вариантах у вас получилось по 9 прямоугольников.

П.2 подробнее. Тут возможны разные стратегии. В частности:

• Можно от блока «пойти» в одну сторону, присоединяя соседей, пока не упрётся в непустую область. Затем попытаться расшириться во вторую сторону всеим набранными блоками, до упора. Затем в третью и четвертую.
  
• Можно идти спиралью. 1 шаг наверх, 1 шаг вправо, 1 шаг вниз, 1 шаг влево и т.д. пока подряд 4 шага ни один не даст прироста.
  

https://en.wikipedia.org/wiki/Covering_problems
В частности: https://en.wikipedia.org/wiki/Polygon_covering#Cov...

Бегаешь по прямоугольникам, если грани формирующие угол соприкасаются с пустотой, то тяни одну из граней до упора. Так получишь еще один прямоугольник. Его надо запомнить. Аналогично проделать со всеми углами. Далее объединяешь два соседних получившихся прямоугольника в один, если их соприкасающиеся грани одинаковые. Так ты получишь наименьшее количество прямоугольников из пустой области. Конечный результат зависит от того, в какой последовательности ты все будешь делать, главное не плоди слишком много мелочи, и старайся из одного угла тянуть только одну грань.

вообщем тут думаю такой ход действий. тест грани на сосесдство с пустотой--->в зависимости от стороны которая соседствует формируем массив видимых блокоы лежащих на ее пути и сортируем по наименьшей координате (в зав-ти от стороны, если правая сторона базового блока то сортируем то что справа по х1, слева по х2 и т.д.) ---> формируем блок и перезапускаем заново цикл, каждый новый найденный блок помечаем ---> когда пустота закончится прогоняем циклом все помеченные найденные блоки на возможность слития. как то так наверное

все очень просто. с начало добавляем рект на все поле в некий лист nodes. потом бежим по всем ректам которые есть на поле, пусть он будет CurrentRect, и для каждого выполняем алгоритм:
бежим по всем nodes от i = 0 до nodes.Count - 1 (во время пробегания nodes.Count может меняться)
{
Берем nodes[i] и если он пересекается с CurrentRect (именно пересекается а не касается) выполняем следующее:
{
Обрезаем его по CurrentRect. как именно: с начало снизу, если есть что резать пихаем в nodes новый рект а текущий урезаем по CurrentRect, и так по всем сторонам
Первый в прогоне запоминаем как основной, который в итоге останется на месте CurrentRect, если он меньше CurrentRect, растягиваем его по CurrentRect.
Все остальные после разрезаний удаляем (куски которые будут лежать в CurrentRect, они лишние) и делаем i--
}
}
Далее можно сделать оптимизацию, найти ректы с одинаковыми гранями и объединить их. Еще можно что-то придумать. Но это уже задачка по легче