Здравствуйте! Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: IT. Если вы считаете, что система ошиблась - напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее. Фрэнк, команда ЖЖ.
Навскидку в голову приходит 2 варианта: 1) Брать закрашенные области и пытаться заполнить их за минимальное число прямоугольников. Начиная от простого перебора до какого-нибудь аналога задачи о рюкзаке на плоскости. Если вас интересуют практические реализации, то можно попробовать погуглить. 2) Чередуя прямоугольники с краской и фоном. Скажем, простую рамку можно нарисовать четырьмя прямоугольниками с краской или одним прямоугольником с краской и одним с фоном. Но чо-то даже не представляю как это реализовать, может тоже что-то можно нагуглить.
1) Задача о рюкзаке это как запихать в заданный объем максимальное количество предметов. Я не знаю, как правильно называется обсуждаемое, поэтому предложил "аналог задачи о рюкзаке на плоскости", только предметов надо не максимум, а минимум.
Алгоритмами графики занимался в юности и по учебе. Но из того, что приходит на ум: 1. Представление данных в виде двухмерного массива X/Y с бинарным содержимым. 2. Преобразование массива в вид набора длинны цепочек цвета пикселя (т.е. удаление из массива ячеек с содержимым 0 и замена бинарного содержимого ячейки на длинну линии. Получаем каждое нечетное значение - длина линии, каждое четное - длина пропуска. Принимаем инициирущее значение (первоначальный пропуск). Пример: исходный массив (ромб, лучше смотреть моношрифтом): 00000000000 00000100000 00001110000 00011111000 00111111100 00011111000 00001110000 00000100000 00000000000
Ну да: предлагаемое -- фактически run-length encoding, Как в древних алгоритмах сжатия графики, вроде BMP и PCX. Только здесь -- не сжатие, а оптимизация отрисовки.
Но -- предлагаемое решение, по сути, одномерное. То есть, анализируя изображение по строкам -- игнорирует повторяемость по столбцам. А если, например, проходить по столбцам -- то игнорируются повторы по строкам.... В общем, интересно, есть ли двухмерный алгоритм.
Тогда так. 0. Находим фоновый цвет и рисуем им прямоугольник растра. Это даст существеную экономию для картинок типа "черный пиксель в белом поле". 1. Сканируем растр, выбирая из него нефоновые подстроки (прямоугольники единичной высоты и длины<длины строки растра). 2. Проходим получившийся список подстрок, выявляя в нем подстроки одинаковой длины, расположенные друг над другом, и сливая их в прямоугольники. 3. Выводим по списку
В принципе, этот подход тоже приходил в голову: выявление прямоугольников.
Однако, опять-таки: как быть с ситуациями, которые 'almost perfect'? Ну, например -- найден практически идеальный прямоугольник, к которому с одной стороны прилеплен один пиксель? Или, наоборот -- идеальный прямоугольник, из которого ровно один пиксель изъят?? )))
(Кстати, поиск таких прямоугольников -- тоже не очень тривиальная задача. Я помню, на какой-то из олимпиад по программированию -- очень похожее было.)
Comments 21
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: IT.
Если вы считаете, что система ошиблась - напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.
Reply
1) Брать закрашенные области и пытаться заполнить их за минимальное число прямоугольников. Начиная от простого перебора до какого-нибудь аналога задачи о рюкзаке на плоскости. Если вас интересуют практические реализации, то можно попробовать погуглить.
2) Чередуя прямоугольники с краской и фоном. Скажем, простую рамку можно нарисовать четырьмя прямоугольниками с краской или одним прямоугольником с краской и одним с фоном. Но чо-то даже не представляю как это реализовать, может тоже что-то можно нагуглить.
Reply
2) Ну, как раз в этом затык (как реализовать)))
Reply
2) Так у вас fun или нужна практическая реализация? Если первое, то это развлечение для ума и мы тут просто накидываем идеи. Если второе, то я бы не думал, а гуглил готовое. Вот что-то гуглится, например
http://dspace.nbuv.gov.ua/bitstream/handle/123456789/8123/45-Voronov.pdf?sequence=1
update: ссылка в пункте 2 негодная, у нас же прямогольники строго ориентированные по горизонтали.
Reply
2. Интересен, прежде всего, теоретический подход. Хотя, к этому подтолкнула вполне практическая задача.
Reply
1. Представление данных в виде двухмерного массива X/Y с бинарным содержимым.
2. Преобразование массива в вид набора длинны цепочек цвета пикселя (т.е. удаление из массива ячеек с содержимым 0 и замена бинарного содержимого ячейки на длинну линии. Получаем каждое нечетное значение - длина линии, каждое четное - длина пропуска. Принимаем инициирущее значение (первоначальный пропуск).
Пример: исходный массив (ромб, лучше смотреть моношрифтом):
00000000000
00000100000
00001110000
00011111000
00111111100
00011111000
00001110000
00000100000
00000000000
Имеем по результату:
инициирующее значение = 16,
массив = 1, 9, 3, 7, 5, 5, 7, 5, 5, 7, 3, 9, 1
Далее простым циклом рисуем линии, если пропуск + длина линии превышают ширину картинки - обрезаем и следующей командой дорисовываем.
Reply
Но -- предлагаемое решение, по сути, одномерное. То есть, анализируя изображение по строкам -- игнорирует повторяемость по столбцам. А если, например, проходить по столбцам -- то игнорируются повторы по строкам.... В общем, интересно, есть ли двухмерный алгоритм.
Reply
Reply
Reply
Двухмерный битовый массив (с разверткой по строкам).
Reply
Reply
Reply
0. Находим фоновый цвет и рисуем им прямоугольник растра. Это даст существеную экономию для картинок типа "черный пиксель в белом поле".
1. Сканируем растр, выбирая из него нефоновые подстроки (прямоугольники единичной высоты и длины<длины строки растра).
2. Проходим получившийся список подстрок, выявляя в нем подстроки одинаковой длины, расположенные друг над другом, и сливая их в прямоугольники.
3. Выводим по списку
Reply
Однако, опять-таки: как быть с ситуациями, которые 'almost perfect'? Ну, например -- найден практически идеальный прямоугольник, к которому с одной стороны прилеплен один пиксель? Или, наоборот -- идеальный прямоугольник, из которого ровно один пиксель изъят?? )))
(Кстати, поиск таких прямоугольников -- тоже не очень тривиальная задача. Я помню, на какой-то из олимпиад по программированию -- очень похожее было.)
Reply
Leave a comment