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

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

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

WWW
« Ответ #60 : 07-06-2010 06:26 » 

Вот примерно так:



1. Секущая a не находит пересечений с контуром - не красим.
2. Секущая b сталкивается с контуром в точке 6. Точка имеет верхнего соседа (5) и не имеет нижнего, поэтому запоминаем "верхний" и идем дальше в поисках нижнего соседа.
3. Проходим точки 7-10, нижний сосед так и не найден. В следующей точке покидаем контур, так ничего и не покрасив (касание границы).
4. Секущая c сталкивается с контуром в точке 5, которая имеет верхнего соседа (4) и нижнего (6). Фиксируем факт пересечения контура снаружи внутрь, включаем триггер закраски.
5. Продолжая сканирование, красим точки внутренней области контура между точками 5 и 11.
6. Секущая сталкивается с контуром в точке 11, которая имеет верхнего соседа (12) и нижнего (10). Фиксируем факт пересечения контура изнутри наружу, выключаем триггер закраски.
7. Остальные секущие ничем принципиально не отличаются от c, за исключением последней, которая пройдет через макушку окружности. Последняя будет подобна секущей b с точностью до осевой симметрии и не будет иметь верхнего соседа.

* Sample.png (4.17 Кб - загружено 1459 раз.)
Записан

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

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

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

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

WWW
« Ответ #61 : 07-06-2010 06:32 » 

Dale, подвох в отрезке прямой.

Все, понял идею. Я этот отрезок принял за секущую, а не часть фигуры на экране.

Алгоритм слишком простой, чтобы справиться с такой ситуацией. Я раньше вскользь упоминал, что если помимо замкнутых контуров на битовой карте есть еще и ломаные, нужно сначала пройтись еще одним алгоритмом, который распознает замкнутые контуры и подготавливает их к закраске. Он тоже в моем представлении очень простой и, что самое главное для мизерного стека, не рекурсивный.
« Последнее редактирование: 07-06-2010 06:34 от Dale » Записан

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

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

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

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

WWW
« Ответ #62 : 07-06-2010 06:33 » 

Dale, по сути, если трассировать контуры, то алгоритм переходит в нечто, описанное мною выше (пост 42). Там линейная заливка, как у тебя, рекурсия (точнее - итераций по очереди заданий на заливку) не велика, а объем запоминаемых данных на итерацию - всего 4 величины (координаты начальной точки, направление и длина - можно упаковаться в 3-4 байта, в зависимости от размеров растрового буфера).

Кстати, граждане, а почему мы забываем об этом самом растровом буфере? История учит, что какая-то его часть не является существенной (например, строка состояния или панель инструментов - их можно перерисовать после) и эту память можно использовать как внешний буфер. Скажем, при распространенном формате для сотовых - экранчике 240х320, если забрать под буфер восемь строк, то получится аж 1920 пикселей - это, в зависимости от формата пикселя, 240-960-1920-3840 байт! Куда больше 128 стандартных для 8051!
Записан

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

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

WWW
« Ответ #63 : 07-06-2010 06:38 » 

Немного в сторону от алгоритма.
Offtopic:

SP в х51 - восьмибитный. Доступ только к внутренней памяти.
И растет он вверх.
Поэтому stackoverflow - стандартная ошибка.
Поставлю в угол.

Записан

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

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

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

Кстати, граждане, а почему мы забываем об этом самом растровом буфере?

Ни в коем случае не забываем. Я как раз и строю алгоритм с его максимальным использованием. Без него даже поле 100*100 точек с 256 градациями серого не поместится в ОЗУ старшей модели МК. Суть в том и состоит, чтобы сканировать буфер экрана.
Записан

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

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

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

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

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

Немного в сторону от алгоритма.
Offtopic:

SP в х51 - восьмибитный. Доступ только к внутренней памяти.
И растет он вверх.
Поэтому stackoverflow - стандартная ошибка.
Поставлю в угол.


Весьма ценное дополнение. Получается, даже наличие в лучшем случае 8К ОЗУ, что само по себе немного, погоды не сделает. Не говоря уже о подключении внешней памяти.
Записан

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

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

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

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

WWW
« Ответ #66 : 07-06-2010 06:45 » 

Слав, стек, в нашем случае - лишь структура, а не SP (особенно если перейти с рекурсии на итерации). Т.ч. его можно организовать и во внешней памяти, хотя доступ к ней не так удобен и на порядок медленнее из-за частых перезагрузок адресного регистра. В минимуме мы имеет порядка 80-100 байт для выполнения задачи. В более прогрессивном процессоре - килобайта полтора.
Записан

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

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


WWW
« Ответ #67 : 07-06-2010 06:46 » 

интересно, а можно ли контролировать заполнение стека таким образом, что вот как только он собрался переполнится, заменяем один из его элементов новой точкой, и продолжаем работать с извлечённой. Или так не всегда возможно ?
Записан

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

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

WWW
« Ответ #68 : 07-06-2010 06:48 » 

Кстати, граждане, а почему мы забываем об этом самом растровом буфере?

Ни в коем случае не забываем. Я как раз и строю алгоритм с его максимальным использованием. Без него даже поле 100*100 точек с 256 градациями серого не поместится в ОЗУ старшей модели МК. Суть в том и состоит, чтобы сканировать буфер экрана.

Нет-нет, я о другом говорю: часть экрана зачастую используется не для отображения картинок, а для всяких статусов, индикаторов, навигации и т.п. На время выполнения затратного по памяти алгоритма можно использовать эту область как бесплатный буфер приличных размеров, а после перерисовать ее заново.

Леш, возьми кольцевой буфер. Когда из него нечего удалить, но и добавить тоже некуда, то что делать?..
« Последнее редактирование: 07-06-2010 06:50 от RXL » Записан

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

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

WWW
« Ответ #69 : 07-06-2010 06:53 » 

Алексей1153++, заполнение стека можно контролировать.
Записан

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

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

WWW
« Ответ #70 : 07-06-2010 07:17 » 

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

1. При вызове подпрограммы, в том числе рекурсивном, программный счетчик откладывается в аппаратный стек. Это накладывает ограничение на глубину рекурсии не более 128 при условии, что на стек нет претензий со стороны других программных модулей и что аппаратные прерывания запрещены.

2. Компилятор С (полагаю, что программа будет писаться именно на нем) обучен передавать агрументы подпрограмм через стек и в стеке же создавать локальные автоматические переменные. Теоретически можно и то, и другое организовать в нашем самодельном стеке. Но мне сильно сдается, что выглядеть это будет, мягко говоря, не слишком эстетично.
Записан

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

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

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

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


WWW
« Ответ #71 : 07-06-2010 07:27 » 

Леш, возьми кольцевой буфер. Когда из него нечего удалить, но и добавить тоже некуда, то что делать?..
так фишка в том, что можно попробовать начать обработку другой точки из стека, а это, в свою очередь, может разгрузить заполненный стек. Только всегда ли это возможно - вот вопрос
Записан

goodking
Постоялец

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

« Ответ #72 : 07-06-2010 07:33 » 

немного о цели вопроса =) . Вообще-то в идеале мне нужно будет выводить на LCD (монохромный) спектры излучения, т.е их то и нужно заливать изнутри, причем форма контура буде постоянно меняться.  
Записан
Dale
Блюзмен
Команда клуба

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

WWW
« Ответ #73 : 07-06-2010 07:38 » 

goodking, а можно картинку, как они выглядят? Хотя бы схематично.
Записан

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

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

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

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

WWW
« Ответ #74 : 07-06-2010 07:48 » 

Offtopic:

Я думал, что топикстартер уже потерялся Улыбаюсь
Поставлю в угол.

goodking, а ты здесь был?
Записан

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

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

WWW
« Ответ #75 : 07-06-2010 09:40 » 

Ну, вот... Мы алгоритмы придумываем, а тут банальней некуда - нарисовать гистограмму.
Лучше покажи нам фото этой картинки, чтобы развеять все сомнения.
Записан

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

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

« Ответ #76 : 07-06-2010 09:55 » 

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

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

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

WWW
« Ответ #77 : 07-06-2010 10:22 » 

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

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

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

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

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

« Ответ #78 : 07-06-2010 11:13 » 

Так, вот приблизительно где-то так оно должно выглядеть, только ч.б

* Безымянный.JPG (65.71 Кб - загружено 765 раз.)
Записан
goodking
Постоялец

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

« Ответ #79 : 07-06-2010 11:14 » 

Ну, вот... Мы алгоритмы придумываем, а тут банальней некуда - нарисовать гистограмму.
Лучше покажи нам фото этой картинки, чтобы развеять все сомнения.

дело в том, что я понятия не имел как это делается, ну и решил идти от простого к сложному =)
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #80 : 07-06-2010 11:15 » 

тут вообще ничего заливать не надо Улыбаюсь
Записан

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

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

« Ответ #81 : 07-06-2010 11:22 » 

Да, при рисовании гистограмм алгоритм заливки не нужен Улыбаюсь
Записан

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

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

WWW
« Ответ #82 : 07-06-2010 11:42 » 

Dale, все же, если есть желание и время, попробуй реализовать свой алгоритм на Си - интересно все таки.
Записан

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

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

« Ответ #83 : 07-06-2010 11:43 » 

Извиняюсь =). Тогда уж посоветуйте, как нужно делать!
Записан
Dale
Блюзмен
Команда клуба

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

WWW
« Ответ #84 : 07-06-2010 11:45 » 

дело в том, что я понятия не имел как это делается, ну и решил идти от простого к сложному =)

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

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

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

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

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

WWW
« Ответ #85 : 07-06-2010 11:49 » 

RXL, можно бы попробовать, только не ручаюсь, что уж очень оперативно управлюсь.

Сначала было подумал, что напряжно будет рисовать средствами чистого С под MS Windows, а потом прикинул, что можно и буквочками в текстовом файле порисовать, нам же не красоты нужны, а саму идею проверить...
Записан

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

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

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

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

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

Как что делать? Рисовать.
Рисовать гистограмму прямыми отрезками.
У тебя ЧБ (2цвета) или 16/256 gray?
Записан

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

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

« Ответ #87 : 07-06-2010 12:19 » 

Как что делать? Рисовать.
Рисовать гистограмму прямыми отрезками.
У тебя ЧБ (2цвета) или 16/256 gray?
чб
Записан
RXL
Технический
Администратор

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

WWW
« Ответ #88 : 07-06-2010 12:29 » 

goodking, для каждой точки гистограммы (x, y) рисовать вертикальные линии от (x, 0) до (x, y).
Записан

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

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

WWW
« Ответ #89 : 07-06-2010 12:35 » 

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

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Страниц: 1 2 [3] 4 5   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines