Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 3 [4] 5   Вниз
  Печать  
Автор Тема: алгоритм закрашивания произвольной области  (Прочитано 95423 раз)
0 Пользователей и 1 Гость смотрят эту тему.
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #90 : 07-06-2010 12:40 » 

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
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #91 : 07-06-2010 12:59 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #92 : 07-06-2010 13:28 » 

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

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

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

* BG240128A.pdf (200.86 Кб - загружено 1337 раз.)
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #93 : 07-06-2010 13:43 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #94 : 07-06-2010 13:51 » 

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

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

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #95 : 07-06-2010 14:07 » 

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

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

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

* r.jpg (12.13 Кб - загружено 1652 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #96 : 07-06-2010 14:15 » 

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #97 : 07-06-2010 14:17 » new

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

а почему нельзя только по вертикали или только по горизонтали?
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #98 : 07-06-2010 14:20 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #99 : 07-06-2010 14:20 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #100 : 07-06-2010 14:22 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #101 : 07-06-2010 14:29 » 

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

Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #102 : 07-06-2010 14:36 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #103 : 07-06-2010 14:46 » 

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

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


Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #104 : 07-06-2010 14:51 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #105 : 07-06-2010 14:54 » 

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

Основная проблема с которой сталкиваемся - это касание в точке "сканирования", которая и сбивает четность.
то-есть в точке изгиба?
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #106 : 07-06-2010 14:58 » 

ну да, конечно.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
goodking
Постоялец

ua
Offline Offline
Пол: Мужской

« Ответ #107 : 07-06-2010 15:05 » 

ну да, конечно.
а если задать условие, заливать только если количество пересеченных точек-четное?
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #108 : 07-06-2010 15:13 » 

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



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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #109 : 07-06-2010 17:48 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #110 : 08-06-2010 02:52 » 

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

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #111 : 08-06-2010 03:31 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #112 : 08-06-2010 03:34 » 

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

Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #113 : 08-06-2010 05:27 » 

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

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #114 : 08-06-2010 05:35 » 

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

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #115 : 08-06-2010 05:52 » 

а в закрашенных местах сделал повышение рельефа
я не совсем  то имел в виду. Надо не "наливать в тарелку сверху" (ведь это , по сути, будет  A* ), а "вливать в форму сбоку" , тогда и вот это
программная реализация такой модели, скорее всего, будет весьма ресурсоемкой.
будет не так: надо сначала "течь вниз до упора" , а потом разливаться по низине, поднимая уровень заливки оттуда. Переливаться через края. И так до победного. Моделировать молекулы не нужно - мы лишь мысленно тянем курсор закраски вниз, а потом он всплывает, закрашивая всё как уровень прибывающей жидкости
« Последнее редактирование: 08-06-2010 05:54 от Алексей1153++ » Записан

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #116 : 08-06-2010 06:07 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #117 : 08-06-2010 06:08 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #118 : 08-06-2010 06:27 » 

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

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

* flow1.PNG (2.91 Кб - загружено 1413 раз.)
Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #119 : 08-06-2010 06:56 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: 1 2 3 [4] 5   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines