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

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

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

« : 02-06-2010 14:18 » 

Посоветуйте, как лучше закрашивать область ограниченную фигурой произвольной формы на графическом ЖКИ. Пробовал алгоритмы предложенные в различной литературе, но они не подходят т.к. я программирую микроконтроллер (SiLabs) а они предназначены для компьютеров, и выполняются либо слишком медленно, либо из-за большо глубины рекурсии вообще не выполняются  Улыбаюсь
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #1 : 02-06-2010 14:29 » 

>> либо из-за большо глубины рекурсии вообще не выполняются  
организовать ручной стек Улыбаюсь

Природу не обманешь. Если надо затратить необходимое число шагов алгоритма (например волновой), то выполнить придётся
Записан

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

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

« Ответ #2 : 03-06-2010 07:18 » 

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

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

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

« Ответ #3 : 03-06-2010 14:32 » 

>> либо из-за большо глубины рекурсии вообще не выполняются 
организовать ручной стек Улыбаюсь

Природу не обманешь. Если надо затратить необходимое число шагов алгоритма (например волновой), то выполнить придётся

волновой метод МК точно не потянет =)
Записан
goodking
Постоялец

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

« Ответ #4 : 03-06-2010 14:35 » 

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

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

 
Записан
goodking
Постоялец

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

« Ответ #5 : 03-06-2010 14:41 » 

вот по такому принципу пытаюсь делать
Код:

m=120;
n=50;//координаты затравочной точки
while (1)

{
while (readLCD(m,n)!=1){m++;}// чтение данных с экрана (1,0)
while (readLCD(v,n)!=1){v--;}
lim1=v+1;
lim2=m;
straight_line((float)lim1,(float)lim2,(float)n,(float)n);//соединяю линией
n++;
m=120;

Записан
Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #6 : 03-06-2010 14:41 » 

goodking,
Цитата
волновой метод МК точно не потянет =)
а что ему помешает ? Улыбаюсь Я делал такое на компьютере с максимально возможным озу 64кБ . Причём программа столько точно не кушала ) Частота процессора 2,5 МГц. Закрашивал заметно для глаза, но справлялся быстро )) Разрешение экрана было 256*384


про "соединить линией" непонятно. Попадётся такая форма контура, об которую твой алгоритм обломается )))
Записан

goodking
Постоялец

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

« Ответ #7 : 03-06-2010 14:49 » 

Попадётся такая форма контура, об которую твой алгоритм обломается )))

например?? Если контур замкнутый то любая линия пересечет его четное количество раз.
Записан
goodking
Постоялец

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

« Ответ #8 : 03-06-2010 14:51 » 

Насчет волнового, я правильно понял, берется точка внутри контура, проверяются все соседние с ней, если пустые-закрашиваются, затем для каждой из этих точек то же самое...?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #9 : 03-06-2010 14:52 » 

ну да, исключая случаи, когда линия пройдёт по касательной к перегибу. Для начала могу посоветовать испытать алгоритм на писюке - где о ресурсах можно не так сильно заботиться Ага
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #10 : 03-06-2010 14:53 » 

Насчет волнового, я правильно понял, берется точка внутри контура, проверяются все соседние с ней, если пустые-закрашиваются, затем для каждой из этих точек то же самое...?
да, имитируется принцип переизлучения волн в природе, только уже закрашенные точки "не проводят" волну (не кладутся в стек)
Алгоритм всегда гарантированно закрашивает любую замкнутую область. И вроде даже оптимальнее всего ))
« Последнее редактирование: 03-06-2010 14:55 от Алексей1153++ » Записан

goodking
Постоялец

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

« Ответ #11 : 03-06-2010 14:55 » 

Ладно, щас попробую  Улыбаюсь
Записан
Dimka
Деятель
Команда клуба

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

« Ответ #12 : 03-06-2010 15:02 » 

А readLCD быстро работает? Можно ли буферизировать изображение, чтобы работать только с RAM?
Записан

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

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

WWW
« Ответ #13 : 03-06-2010 15:09 » 

попытаться посчитать площадь заливаемой области
Координаты области известны?
Записан

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

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

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

Если контур замкнутый то любая линия пересечет его четное количество раз.

За исключением случая, когда секущая лишь касается контура в точке излома, и точки контура в окрестности точки касания лежат по одну сторону от секущей.

Алгоритм закраски внутренней области контура отрезками секущей будет работать, если такие точки просто игнорировать. Или, если будет на то желание и/или причина, считать такие точки двойными: вошли внутрь области и тут же вышли наружу.
Записан

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

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

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

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

« Ответ #15 : 04-06-2010 11:30 » 


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

попробовал так
Код:
void Fill (unsigned char x, unsigned char y)
{
if (readLCD(x,y)==0)
{
PutPixelXYLCD(x,y,1);// если 0 то закрасить
Fill(x+1,y);
Fill(x-1,y);
Fill(x,y+1);
Fill(x,y-1);
}

в качестве закрашиваемого контура выбрал круг, закрашивает довольно симпатично, но почему-то только 1/4 круга  Не понял
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

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


WWW
« Ответ #16 : 04-06-2010 11:33 » 

goodking, 1/4 - потому что unsigned char x, unsigned char y)
 то есть, знак не учитываешь, красится только первый квадрант Улыбаюсь

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

goodking
Постоялец

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

« Ответ #17 : 04-06-2010 11:49 » 

Перед рекурсивным вызовом проверяй, закрашена ли уже точка, если да - то пропускай
два раза проверять?
оно же и так проверяется if (readLCD(x,y)==0)
Записан
Sla
Команда клуба

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

WWW
« Ответ #18 : 04-06-2010 12:01 » 

на МК рекурсия? Не стремно?
Записан

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

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

« Ответ #19 : 04-06-2010 12:03 » 

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

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

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

использование стека можно уменьшить, используя "глобальные" параметры

типа
Код:
unsigned char x, unsigned char y
void Fill ()
{
if (readLCD(x,y)==0)
{
PutPixelXYLCD(x,y,1);// если 0 то закрасить
Fill(x+1,y);
Fill(x-1,y);
Fill(x,y+1);
Fill(x,y-1);
}
Записан

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

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

WWW
« Ответ #21 : 04-06-2010 12:20 » 

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

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

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

« Ответ #22 : 04-06-2010 12:48 » 

использование стека можно уменьшить, используя "глобальные" параметры

типа
Код:
unsigned char x, unsigned char y
void Fill ()
{
if (readLCD(x,y)==0)
{
PutPixelXYLCD(x,y,1);// если 0 то закрасить
Fill(x+1,y);
Fill(x-1,y);
Fill(x,y+1);
Fill(x,y-1);
}

это как? Не получится рекурсивная же функция!
Записан
Sla
Команда клуба

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

WWW
« Ответ #23 : 04-06-2010 12:55 » 

получится, но объем стека занимаемый ею (рекурсией) уменьшится
Записан

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

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

« Ответ #24 : 04-06-2010 13:00 » 

получится, но объем стека занимаемый ею (рекурсией) уменьшится
не понимаю, если Fill не принимает никаких параметров, то как она будет рекурсивно вызвватся?
Записан
goodking
Постоялец

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

« Ответ #25 : 04-06-2010 13:01 » 

Стоп, я кажется понял..
Записан
Вад
Модератор

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

« Ответ #26 : 04-06-2010 13:05 » 

По-моему, это уже попытка написать итеративный алгоритм с помощью рекурсивной функции Улыбаюсь В каком-нибудь лиспе оно бы совсем не потребовало дополнительных затрат на стек, и всё было бы ОК. А тут - сомнения берут в целесообразности.

Можно заменить 4-way на 8-way, закрашивая и по диагонали тоже. По идее, глубина рекурсии должна уменьшиться.
Записан
goodking
Постоялец

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

« Ответ #27 : 04-06-2010 13:27 » 

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

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


WWW
« Ответ #28 : 04-06-2010 16:15 » 

Перед рекурсивным вызовом проверяй, закрашена ли уже точка, если да - то пропускай
два раза проверять?
оно же и так проверяется if (readLCD(x,y)==0)
а почему именно ноль ? Монохромный экран ?

а проверять не два раза, а аж 5 раз:
1) проверяем, лежит ли точка в стеке. Если лежит - вытаскиваем x,y
2) проверяем, является ли x+0,y-1 закрашенной? Если нет - кладём в стек (вызываем fill(x+0,y-1))
3) проверяем, является ли x+0,y+1 закрашенной? Если нет - кладём в стек (вызываем fill(x+0,y+1))
4) проверяем, является ли x-1,y+0 закрашенной? Если нет - кладём в стек (вызываем fill(x-1,y+0))
5) проверяем, является ли x+1,y+0 закрашенной? Если нет - кладём в стек (вызываем fill(x+1,y+0))

кстати, кроме цвета точки полезно ещё границы перед покладением в стек проверить Улыбаюсь
Записан

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

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

« Ответ #29 : 04-06-2010 19:54 » 

Алексей1153++, шаг 1 лишний - точки в стеке подлежат закрашиванию по построению стека. В остальных случаях ты не так считаешь. Каждая точка действительно проверяется максимум 4 раза, но не из-за упомянутых шагов алгоритма, а из-за того, что алгоритм подходит к ней от каждой из четырёх соседних точек.
Записан

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines