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