алгоритм закрашивания произвольной области

[RXL]

Dale, ну да. Кстати, посмотри графический формат xpm - так можно и картинку реальную увидеть, и в тексте оставаться.
http://ru.wikipedia.org/wiki/X_Pixmap#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80_.D0.B8.D0.B7.D0.BE.D0.B1.D1.80.D0.B0.D0.B6.D0.B5.D0.BD.D0.B8.D1.8F

[Dale]

я подозреваю, что у "дисплея" есть встроенная функция рисования прямых.

Не факт. Я использовал в самоделках графические дисплеи DOGM132 и от Nokia 1200. И те, и другие напрочь лишены интеллекта, просто тупо засвечивают точки. Может, у старших моделей такая функция и имеется, не сталкивался. Но твердо рассчитывать на ее наличие не стоит.

[goodking]

я подозреваю, что у "дисплея" есть встроенная функция рисования прямых.

С другой стороны если, например гистограмма рисуется в реальном времени, и нет времени на прорисовку отрезков, то заполнение проводить уже "постфактум".

Подозреваю, что просмотр "спектра" происходит в ручном режиме, т.е. есть время на прорисовку.

неет, ничего такого нет, вот ЖКИ с которым я работаю

[Sla]

goodking, достаточно было бы ссылку на контроллер

Ну, нет так нет.
Все равно задача упрощается.
двигаясь по оси X заливать ось Y. Обыкновенный итерационный метод.

[goodking]

goodking, достаточно было бы ссылку на контроллер

Ну, нет так нет.
Все равно задача упрощается.
двигаясь по оси X заливать ось Y. Обыкновенный итерационный метод.

да я уже понял, сижу пишу... но насчет контура-все равно интересно просто для себя, возможно ли реализовать это на МК (кстати МК SiLabs c8051F120)

[Sla]

непроверенная идея

Если контур замкнутый то пересечение прямой дает четное количество точек.
Заливка происходит по вертикали, затем по горизонтали

вот как-то так

[Dale]

Я примерно эту идею и продвигаю в массы, только там касания могут испортить всю малину, нарушив четность.

[goodking]

Если контур замкнутый то пересечение прямой дает четное количество точек.
Заливка происходит по вертикали, затем по горизонтали

а почему нельзя только по вертикали или только по горизонтали?

[Sla]

...нарушить четность

Нестрашно. Надо идти до первого свободного.

[Sla]

Если контур замкнутый то пересечение прямой дает четное количество точек.
Заливка происходит по вертикали, затем по горизонтали

а почему нельзя только по вертикали или только по горизонтали?

Потому что... смотри рисунок.

[Sla]

...нарушить четность

Нестрашно. Надо идти до первого свободного.

кажется спорол глупость.
Я ж говорил - непровернная.

[goodking]

вот как описан этот (насколько я понимаю) алгоритм в книжке

Поэтому для решения задачи закраски области
предпочтительнее алгоритмы, способные обрабатывать сразу целые группы
пикселов, т. е. использовать их "связность" - если данный пиксел принадлежит области, то
скорее всего его ближайшие соседи также принадлежат данной области.
Ясно, что по заданной точке (х, у) отрезок [xl, хr] максимальной длины,  
проходящий через эту точку и целиком содержащийся в области, построить несложно.
После заполнения этого отрезка необходимо проверить точки, лежащие
непосредственно над и под ним. Если при этом мы найдем незаполненные пикселы,
принадлежащие данной области, то для их обработки рекурсивно вызывается функция.
Этот алгоритм намного эффективнее
предыдущего и способен работать с
областями самой сложной формы

[Sla]

goodking, учитывая ограниченный объем стека МК от рекурсии мы отказываемся.
Рекурсию можно использовать на малых областях.

Задача. Залить дисплей рекурсивным методом
размер NxM
при лучших условиях тебе понадобится стек размером n*m

[goodking]

немножко не то, я имел ввиду этот алгоритм

Существует и другой подход к заполнению области сложной формы,
заключающийся в определении ее границы и последовательном заполнении горизонтальных
участков между граничными пикселами.
Такой алгоритм имеет следующую структуру:
• построение упорядоченного списка граничных пикселов (отслеживается
верхняя граница);
• проверка внутренности (для обнаружения в ней дыр);
• заполнение области горизонтальными отрезками, соединяющими точки границы

[Sla]

goodking, пойми, это все алгоритмы ресурсоемкие (жрут много памяти)
Запомнить контур, построить список

Основная проблема с которой сталкиваемся - это касание в точке "сканирования", которая и сбивает четность.

[goodking]

goodking, пойми, это все алгоритмы ресурсоемкие (жрут много памяти)
Запомнить контур, построить список

Основная проблема с которой сталкиваемся - это касание в точке "сканирования", которая и сбивает четность.

то-есть в точке изгиба?

[Sla]

ну да, конечно.

[goodking]

ну да, конечно.

а если задать условие, заливать только если количество пересеченных точек-четное?

[RXL]

goodking, опять возвращаемся назад. См. рисунок.

Отрезок на рисунке испортит работу такого алгоритма. Необходима логика для проверки, что является контуром, а что - нет.

[Dimka]

Задача. Залить дисплей рекурсивным методом
размер NxM
при лучших условиях тебе понадобится стек размером n*m

С какой это стати n*m?

[Алексей++]

Ещё мысль по заливанию: заливать, представляя, что внизу у нас сила тяжести ))

[RXL]

Леш, расскажи подробнее. Лучше с примером.

[Алексей++]

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

[Dale]

Ещё мысль по заливанию: заливать, представляя, что внизу у нас сила тяжести ))

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

Очень удачная метафора. Только я бы плоскость расположил горизонтально, а в закрашенных местах сделал повышение рельефа. Тогда тяжелая жидкая краска будет растекаться по свободным областям, пока не упрется в дамбу. Заливка прекращается, когда повышается уровень краски, это означает, что ей больше некуда растекаться. Этакая аналоговая вычислительная машина.

[Dale]

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

[Алексей++]

а в закрашенных местах сделал повышение рельефа

я не совсем  то имел в виду. Надо не "наливать в тарелку сверху" (ведь это , по сути, будет  A* ), а "вливать в форму сбоку" , тогда и вот это

программная реализация такой модели, скорее всего, будет весьма ресурсоемкой.

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

[Sla]

Еще реализация

Найти точку на контуре и проходить ее по контуру во внутрь.
Недостаток - дырки в области.

[Sla]

Алексей1153++, то что ты предлагаешь, чем отличается от волнового метода?

[Алексей++]

принципом. А стек будет использоваться только в местах перегибов

вот как-то так

[Dimka]

Sla, он предлагает написать пиксельный тетрис

Производительность будет просто замечательная