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

[goodking]

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

[Алексей++]

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

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

[Dimka]

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

[goodking]

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

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

волновой метод МК точно не потянет =)

[goodking]

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

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

 

[goodking]

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

Код:

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;

[Алексей++]

goodking,

волновой метод МК точно не потянет =)

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


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

[goodking]

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

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

[goodking]

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

[Алексей++]

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

[Алексей++]

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

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

[goodking]

Ладно, щас попробую 

[Dimka]

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

[Sla]

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

[Dale]

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

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

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

[goodking]

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

попробовал так

Код:

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 круга 

[Алексей++]

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

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

[goodking]

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

два раза проверять?
оно же и так проверяется if (readLCD(x,y)==0)

[Sla]

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

[goodking]

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

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

[Sla]

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

типа

Код:

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]

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

[goodking]

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

типа

Код:

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]

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

[goodking]

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

не понимаю, если Fill не принимает никаких параметров, то как она будет рекурсивно вызвватся?

[goodking]

Стоп, я кажется понял..

[Вад]

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

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

[goodking]

не, виснет, буду пробовать с массивом

[Алексей++]

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

два раза проверять?
оно же и так проверяется 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]

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