Leave a comment

Comments 21

lj_frank_bot November 22 2021, 12:06:02 UTC
Здравствуйте!
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: IT.
Если вы считаете, что система ошиблась - напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.

Reply


ziavra November 22 2021, 14:57:43 UTC
Навскидку в голову приходит 2 варианта:
1) Брать закрашенные области и пытаться заполнить их за минимальное число прямоугольников. Начиная от простого перебора до какого-нибудь аналога задачи о рюкзаке на плоскости. Если вас интересуют практические реализации, то можно попробовать погуглить.
2) Чередуя прямоугольники с краской и фоном. Скажем, простую рамку можно нарисовать четырьмя прямоугольниками с краской или одним прямоугольником с краской и одним с фоном. Но чо-то даже не представляю как это реализовать, может тоже что-то можно нагуглить.

Reply

trilirium November 23 2021, 06:24:34 UTC
1) а что это за задача -- о "рюкзаке на плоскости"?

2) Ну, как раз в этом затык (как реализовать)))

Reply

ziavra November 23 2021, 14:27:38 UTC
1) Задача о рюкзаке это как запихать в заданный объем максимальное количество предметов. Я не знаю, как правильно называется обсуждаемое, поэтому предложил "аналог задачи о рюкзаке на плоскости", только предметов надо не максимум, а минимум.

2) Так у вас fun или нужна практическая реализация? Если первое, то это развлечение для ума и мы тут просто накидываем идеи. Если второе, то я бы не думал, а гуглил готовое. Вот что-то гуглится, например
http://dspace.nbuv.gov.ua/bitstream/handle/123456789/8123/45-Voronov.pdf?sequence=1

update: ссылка в пункте 2 негодная, у нас же прямогольники строго ориентированные по горизонтали.

Reply

trilirium November 23 2021, 17:58:46 UTC
1. А, понятно. Эту задачу я знаю (правда, кажется, как "задачу о ящике") -- меня плоский рюкзак смутил. )))

2. Интересен, прежде всего, теоретический подход. Хотя, к этому подтолкнула вполне практическая задача.

Reply


terrious November 22 2021, 15:02:44 UTC
Алгоритмами графики занимался в юности и по учебе. Но из того, что приходит на ум:
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

trilirium November 23 2021, 06:30:44 UTC
Ну да: предлагаемое -- фактически run-length encoding, Как в древних алгоритмах сжатия графики, вроде BMP и PCX. Только здесь -- не сжатие, а оптимизация отрисовки.

Но -- предлагаемое решение, по сути, одномерное. То есть, анализируя изображение по строкам -- игнорирует повторяемость по столбцам. А если, например, проходить по столбцам -- то игнорируются повторы по строкам.... В общем, интересно, есть ли двухмерный алгоритм.

Reply


ony10 November 22 2021, 16:31:24 UTC
Исходные данные - растр (двумерный массив)?

Reply

karpion November 22 2021, 17:34:38 UTC
Вот-вот, надо начинать с типа исходных данных.

Reply

trilirium November 23 2021, 06:32:55 UTC
Да.
Двухмерный битовый массив (с разверткой по строкам).

Reply


ony10 November 22 2021, 21:55:12 UTC
Еще один вопрос: перекраска возможна? Можно нарисовать белый прямоугольничек поверх чОрного прямоугольника?

Reply

trilirium November 23 2021, 06:33:07 UTC
Возможна.

Reply

ony10 November 23 2021, 08:39:19 UTC
Тогда так.
0. Находим фоновый цвет и рисуем им прямоугольник растра. Это даст существеную экономию для картинок типа "черный пиксель в белом поле".
1. Сканируем растр, выбирая из него нефоновые подстроки (прямоугольники единичной высоты и длины<длины строки растра).
2. Проходим получившийся список подстрок, выявляя в нем подстроки одинаковой длины, расположенные друг над другом, и сливая их в прямоугольники.
3. Выводим по списку

Reply

trilirium November 23 2021, 08:48:15 UTC
В принципе, этот подход тоже приходил в голову: выявление прямоугольников.

Однако, опять-таки: как быть с ситуациями, которые 'almost perfect'? Ну, например -- найден практически идеальный прямоугольник, к которому с одной стороны прилеплен один пиксель? Или, наоборот -- идеальный прямоугольник, из которого ровно один пиксель изъят?? )))

(Кстати, поиск таких прямоугольников -- тоже не очень тривиальная задача. Я помню, на какой-то из олимпиад по программированию -- очень похожее было.)

Reply


Leave a comment

Up