Алгоритм поиска пустых прямоугольников?
Вроде бы, всё просто. Никакой NP-полноты.Разбить, как вы и описали, по гайдам на мелкие. Это максимальное число полигонов.Взять любой, и начать присоединять к нему смежные, насколько возможно.Взять следующий пустой не затронутый.Процесс останавливается, когда больше ни к одному 4-угольнику нельзя присоединить еще один.
Поверхностно кажется, что так получится наименьшее возможное число. Хотя не гарантируется максимизация площадей. Хотя, пожалуй, такой подход может не найти оптимальный вариант, когда границы нескольких исходных блоков легли точно на одной линии. Тогда выиграет вариант, захватывающий обе пустоты. Представьте силуэт буквы «Т». Его можно замостить всего двумя прямоугольниками. Но алгоритм может прозевать такую возможность и предложить 3 блока.
Представьте себе Г-образный набор блоков. Как ни крути, там не менее 2 в итоге получится. Заметьте, что в обоих вариантах у вас получилось по 9 прямоугольников.
П.2 подробнее. Тут возможны разные стратегии. В частности:Можно от блока «пойти» в одну сторону, присоединяя соседей, пока не упрётся в непустую область. Затем попытаться расшириться во вторую сторону всеим набранными блоками, до упора. Затем в третью и четвертую.Можно идти спиралью. 1 шаг наверх, 1 шаг вправо, 1 шаг вниз, 1 шаг влево и т.д. пока подряд 4 шага ни один не даст прироста.
вообщем тут думаю такой ход действий. тест грани на сосесдство с пустотой--->в зависимости от стороны которая соседствует формируем массив видимых блокоы лежащих на ее пути и сортируем по наименьшей координате (в зав-ти от стороны, если правая сторона базового блока то сортируем то что справа по х1, слева по х2 и т.д.) ---> формируем блок и перезапускаем заново цикл, каждый новый найденный  блок помечаем ---> когда пустота закончится прогоняем циклом все помеченные найденные блоки на возможность слития. как то так наверное