Всем привет 

Постановка задачи: Существует картинка - прямоугольник со сторонами N и M, изначально составленная из элементарных квадратов (1x1). Каждый квадрат имеет свойство:цвет. Квадраты в прямоугольнике расположены как ячейки в таблице (другая аналогия: картинка и её пиксели). Я пытаюсь написать/найти алгоритм, который уменьшает общее кол-во (а лучше - находит минимум) квадратов, "склеивая" их в прямоугольники (конструкции вида Г или Т создавать нельзя). Условие склеивания: одинаковый цвет. Т.е. чем из меньшего числа прямоугольников и квадратов будет в конце состоять наша "картинка", тем лучше. Понятно что найдутся неоптимизирующиеся прямоугольники: 

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

Вопрос: Может кто знает название подобного алгоритма (или ссылку на аналогичное)? Заранее спасибо 

Это сообщение отредактировал(а) Michael.de - 22.10.2009, 19:09

ваша задача сводится к нахождению минимального разбиения прямоугольного многоугольника на прямоугольники

Lipetsk, а что это за задача и где можно найти информацию о алгоритме её решения?

P.S. "прямоугольный многоугольник"... хм, а разве не проще называть эту конструкцию прямоугольником? Или прямыми считаются также внешние углы и крест тоже к ним относится? (правда это уже не мой вопрос)

Michael.de
Вам примерно так надо?
http://narod.ru/disk/14429643000/Compare_color_rect.rar.html
Прога ищет прямоугольники, больише чем 1х1
 см. личку.

Sanaff, эээ... а где она их ищет? И это... я - параноик (*.exe из интернета не открываю). Может просто на словах принцип работы скажешь? А кодировать я уж сам 

Прога ищет однотонные прямоуглольники на изображении, состоящем из поля разноцветных точек и нескольких прямоугольников разных цветов. Во всяком случае, подходит к твоему заданию.
Алгоритм: пробег по столбцу (по y), поиск "линий" (смежных точек) с одинаковым цветом. Для каждой такой линии смотрим весь список найденных прямоугольников. если есть прямоугольник с началом, равным началу линии и с высотой, равной длине линии и он по х заканчивается как раз на предыдущем столбце, то добавляем линию к этому прямоугольнику. Иначе - это начало нового прямоугольника (высотой = длине линии, шириной=1)
Какой-то жуткий текст получился 0_0. Скачай прогу и посмотри. Проверяй антивирусниками, а специально вирусы никто слать не станет. Я просто доверяю всему, что присылают форумчане.

Sanaff, твой алгоритм найдёт 2 синих прямоугольника до красной линии и 2 после неё? И то же, если его повернуть на 90° или зеркально "отсимметрить"? Просто я считаю, что от перемены расположения прямоугольника в пространстве не должно меняться конечное решение (нахождение минимума одноцветных прямоугольников)
••••••••
••••••••
••••••••
••••••••
••••••••
••••••••

P.S. И это ещё очень простой пример 

Это сообщение отредактировал(а) Michael.de - 26.10.2009, 23:54

Michael.de
Нет, мой алгоритм найдёт 2 вверху и 3 внизу.если повернуть - то по-другому. Я и не говорил, что это оптимальный алгоритм. И вообще, поиск минимального числа чего-то - это раздел интеллектуальных задач, где алгритмы не такие простые.
Может помочь поиск и выделение прямоугольников сначала в одном направлении, потом в другом (на 90°)
Пример:

000000000                      
0000*****
00*****00
000000000

можно представить:

000000000                      
000022233
001122200
000000000   - так 3 прямоугольника (направление по Y)
  или:
000000000                      
000011111
002222200
000000000   - так  2 прямоугольника (направление по Х)

Как организовать выбор направления поиска, чтобы было минимальное число прямоугольников - пока не знаю. всю картинку поворачивать - смысла нет. надо вести 2 (или 4) направления анализа для каждой точки. Приоритетное направление - где линия от этой точки продолжается дольше. ИМХО.

Эээ... я вообще хотел бы уйти от этого примера с графическим файлом (*.png, *.jpg или *.gif). Мне нужен алгоритм (или направление для его поиска) без привязки к какой-либо практической задаче. Хотя использовать картинку (но только в качестве примера!) очень удобно и наглядно 

Можно начать отсюда: http://www.cise.ufl.edu/~sahni/papers/part.pdf

для решения возможно подойдет квадродерево(quadtree)