Разбиение битовой карты

From

Max Alekseyev (2:5015/60)

To

Sergei Makarov

Date

2002-07-31T18:31:56Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Sergei !

Replying to a message of Sergei Makarov to All:

 SM> Посоветуйте алгоритм решения задачи:
 SM> Дана битовая карта (0|1) N x M.
 SM> Надо выделить из нее список прямоугольников единиц (структура RECT).
 SM> Критерии оптимальности:     минимум прямоугольников

Первое, что пришло в голову:

1) Находишь еще непокрытую "угловую" (см. ниже) единицу, определяешь прямоугольник 1x1 из нее состоящий. Если такой единицы нет - конец.

2) Раздуваешь прямоугольник, пока возможно: если снаружи вдоль какой-то стороны стоят одни единицы, добавляешь их к прямоугольнику.

3) Добавляешь прямоугольник в список. Помечаешь все единицы, которые он содержит, как покрытые.

4) goto 1

ЗЫ. "Угловая" единица - это единица не зажатая двумя другими непокрытыми единицами (по вертикали или горизонтали). Возможные варианты с точностью до поворотов:

    [*]            [*]         [*]
 [*](1)[*]      [*](1)[1]   [*](1)[1]
    [*]            [*]         [1]

здесь: (1) - угловая единица
       [1] - непокрытая единица
       [*] - ноль, покрытая единица или отсутствие клетки

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)