ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Простий алгоритм заповнення iз зачiпкою i стеком.

Загрузка...

1. Покласти пiксел зачiпки у стек.

2. Доки стек не є порожнiм:

а) Вибрати пiксел iз стека. Розглядати його як поточний пiксел.

в) Надати пiкселу потрiбне значення.

с) Для кожного з сусiднiх до поточного 4-зв'язних (8- зв'язних) пiкселiв перевiрити: цей пiксел є граничний або пiксел вже має потрiбне значення. Якщо так, тодi не розглядати далi цей пiксел. Iнакше покласти сусiднiй пiксел у стек.

Програмна реалiзацiя алгоритму заповнення з зачiпкою.

unit SimpleSeedUnit1;

interface

uses Windows, Messages, SysUtils, Classes, Graphics, Controls,

Forms, Dialogs, StdCtrls;

const _N = 100; {максимальне число граничних пiкселiв}

_Xmax = 10; {розмiр вiкна по вiсi абсцис}

_Ymax = 8; {розмiр вiкна по вiсi ординат}

_Nstack = 100;{максимальна величина стека}

Type TForm1 = class(TForm)

Button1: TButton;

procedure Button1Click(Sender: TObject);

Private { Private declarations }

public { Public declarations }

end;

Point = array[1..2] of integer; {точка}

Border = array[1.._N] of Point; {границя}

Pi = array[0.._Ymax,0.._Xmax] of boolean;{пiкселi}

tStack = array[1.._Nstack] of Point; {стек пiкселiв}

var Form1: TForm1;

Color, {колiр}

NP, {число граничних пiкселiв}

NS, {число пiкселiв у стекi}

Xmax,Ymax, {макс.число пiкселiв уздовж осей}

X,Y, {координати поточного пiкселя}

i {робоча змiнна}

: integer;

Ptemp, {поточний пiксел}

Zatr {пiксел зачiпки}

: Point;

P: Border; {список граничних пiкселiв}

Stack: tStack; {стек для вiдмiчених пiкселiв}

M: Pi; {массив пiкселiв вiкна}

fin: text; {файл з вхiдними даними}

implementation {$R *.DFM}

// встановлення списку граничних пiкселiв

procedure SetP(var P:Border;var NP:integer;var Zatr:Point);

var i, xs,ys,xf,yf,dx,dy:integer;

begin {SetP}

assign(fin,'Zatr1gr.dat');reset(fin);MP:=0;

readln(fin,Zatr[1],Zatr[2]);

while (not Eof(fin)) do

begin {while not Eof(fin)}

readln(fin,xs,ys,xf,yf);

if xs<xf then dx:=1

else if xs=xf then dx:=0 else dx:=-1;

if ys<yf then dy:=1

else if ys=yf then dy:=0 else dy:=-1;

if (NP<1)or((P[NP,1]<>xs)or(P[NP,2]<>ys))

then begin

NP:=NP+1;

P[NP,1]:=xs;P[NP,2]:=ys;

end;

while ((P[NP,1]<>xf)or(P[NP,2]<>yf)) do

begin

NP:=NP+1;P[NP,1]:=P[NP-1,1]+dx;

P[NP,2]:=P[NP-1,2]+dy;

end;

end; {while not Eof(fin)}

close(fin);

// виведення на полотно контуру багатокутника (червоним)}

for i:=1 to NP do Form1.Canvas.Pixels[P[i,1],P[i,2]]:=clRed;

end; {SetP}

 

// гасiння пiкселiв буферу

procedure SetStartM(var M:Pi;Xmax,Ymax:integer;

P:Border;NP:integer);

var i,j:integer;

begin {SetStartM}

for j:=0 to Xmax do

for i:=0 to Ymax do M[i,j]:=false;

for i:=1 to NP do

begin

M[round(P[i,1]),round(P[i,2])]:=true;

end;

end; {SetStartM}

 

// iнвертування пiксела

procedure Inv(var M:Pi;i,j:integer);

begin

if M[i,j]=true then M[i,j]:=false

else M[i,j]:=true;

end;

 

// розмiщення пiксела у стеку

procedure PushPixel(p:point;var s:tStack;var Ns:integer);

begin

Ns:=Ns+1; s[Ns,1]:=p[1];s[Ns,2]:=p[2];

end;

 

// виймання пiксела з стека

procedure PopPixel(s:tStack;var Ns:integer;var p:point);

begin

p[1]:=s[Ns,1];p[2]:=s[Ns,2];Ns:=Ns-1;

end;

 

{виведення поточного стану растра у вiкно}

procedure TypeRastr(M:Pi;Xmax,Ymax:integer;Color:integer);

var i,j:integer;

begin {TypeRastr}

for i:=0 to Ymax do

for j:=0 to Xmax do

if M[i,j]=true then Form1.Canvas.Pixels[i,j]:=Color;

end; {TypeRastr}

 

function YesMarked(Ptemp:point;M:Pi):boolean;

var i,j:integer;

begin {YesMarked}

i:=round(Ptemp[1]); j:=round(Ptemp[2]);

if M[i,j]=true then YesMarked:=true

else YesMarked:=false;

end;{YesMarked}

 

procedure Mark(Ptemp:point;var M:Pi);

var i,j:integer;

begin

i:=round(Ptemp[1]);

j:=round(Ptemp[2]);M[i,j]:=true;

end;

 

function YesBody(Pnext:Point;P:Border;NP:integer):boolean;

var i:integer;

begin {YesBody}

YesBody:=false;

for i:=1 to NP do if (Pnext[1]=P[i,1])and(Pnext[2]=P[i,2])

then YesBody:=true;

end; {YesBody}

 

procedure Zapoln(var M:Pi;Xmax,Ymax:integer;

P:Border;NP:integer;Zatr:point);

var i,j:integer; Pnext:Point;

begin {Zapoln}

Ptemp[1]:=Zatr[1]; Ptemp[2]:=Zatr[2];

PushPixel(Ptemp,Stack,NS);{занесення пiксела зачiпки у стек}

while NS<>0 do {доки стек не буде порожнiм}

begin {while NS<>0}

PopPixel(Stack,NS,Ptemp);{вiдбiр пикселю з стеку}

if not YesMarked(Ptemp,M) then Mark(Ptemp,M);

for i:=-1 to 1 do

if i<>0 then begin

Pnext[1]:=Ptemp[1]+i;Pnext[2]:=Ptemp[2];

if (not YesMarked(Pnext,M))and(not YesBody(Pnext,P,NP))

then PushPixel(Pnext,Stack,NS);

end;

for j:=-1 to 1 do

if j<>0 then begin

Pnext[1]:=Ptemp[1];Pnext[2]:=Ptemp[2]+j;

if (not YesMarked(Pnext,M))and(not YesBody(Pnext,P,NP))

then PushPixel(Pnext,Stack,NS);

end;

end;{while NS<>0}

end; {Zapoln}

 

procedure TForm1.Button1Click(Sender: TObject);

begin {TForm1.Button1Click}

SetP(P,NP,Zatr);//встановлення списку граничних пiкселiв

NS:=0; {"очищення стеку"}

//стартове встановлення пiкселiв i вст.граничних пiкселiв

SetStartM(M,Xmax,Ymax,P,NP);

Zapoln(M,Xmax,Ymax,P,NP,Zatr);

TypeRastr(M,Xmax,Ymax,clYellow);

end; {TForm1.Button1Click}

 

initialization

Xmax:=_Xmax;

Ymax:=_Ymax;

end.

Лiтература.[ 5, стор. 111-114].

 

Зауваження 10У [ 24, стр.650-651] наведено рекурсивний алгоритм заповнення 4-зв'язної областi ( flood-fill algorithm) у виглядi процедури на мовi C. Вiн змiнює колiр кожного пiксела, що знаходиться у серединi областi i має колiр intColor на новий колiр newColor. Алгоритм послiдовно заповнює область кольором newColor "створюючи власний шлях" newColor вiд "початкового" пiкселя з координатами (x, y) у пошуках пикселiв кольору intColor, змiнюючи колiр кожного зі знайдених пiкселiв на newColor}.

Головна iдея цього алгоритму будується на наступних мiркуваннях. Якщо пiксел з координатами (x ,y) знаходиться у серединi областi (тодi його колiр intColor), то змiнюємо його колiр на newColor i рекурсивно використовуємо цей процес до кожного з чотирьох сусiднiх пiкселiв. У протилежному випадку нiчого не робимо.

Наступна реалiзацiя у середовищі програмування DELPHI здiйснена студентом Анiшевим.

Процедура рекурсивного заповнення 4-зв'язної областi.

procedure FloodFill(canvas:TCanvas;x,y:Integer;

IntColor,NewColor:TColor);

begin

If canvas.Pixels[x,y]=IntColor

then begin

canvas.Pixels[x,y]:=NewColor;

FloodFill(canvas,x-1,y,IntColor,NewColor);

FloodFill(canvas,x+1,y,IntColor,NewColor);

FloodFill(canvas,x,y+1,IntColor,NewColor);

FloodFill(canvas,x,y-1,IntColor,NewColor);

end;

 

procedure TForm1.PaintBox1MouseUp(Sender: TObject;

Button: TMouseButton; Shift: TShiftState; X, Y: Integer);

begin

FloodFill(PaintBox1.Canvas,x,y,

PaintBox1.Canvas.Pixels[x,y],clRed);

end;

 

procedure TForm1.PaintBox1Paint(Sender: TObject);

begin

PaintBox1.Canvas.Brush.Color:=clWhite;

PaintBox1.Canvas.Brush.Style:=bsSolid;

PaintBox1.Canvas.Pen.Color:=clWhite;

PaintBox1.Canvas.Rectangle(PaintBox1.ClientRect);

end;

 

2.2.5 Алгоритм заповнення по рядкам iз зачiпкою

У попередньому алгоритмi стек може бути досить великим, що веде до уповiльнення роботи програми. Ще один недолiк вказаного алгоритму -- у стек часто заносимо дублюючу iнформацiю, що веде до наявностi "холостого ходу". Тому iснує модифiкацiя простого алгоритму заповнення з зачiпкою - алгоритм заповнення за рядками iз зачiпкою. У модифiкованому алгоритмi розмiр стека мiнiмiзується завдяки зберiганню лише одного пiкселя iз зачiпкою для будь-якого неперервного iнтервалу на рядку, що сканується. Даний алгоритм можна використовувати до гранично-визначених областей. Гранично-визначена 4-звязна область може мiстити дiрки. В областi, що є зовнiшня до гранично-визначеної областi, яку ми розглядаємо, не повинно бути пiкселiв, колiр яких спiвпадає з кольором заливки.

Алгоритм заповнення за рядками iз зачiпкою має наступнi етапи:

1. Покласти пiксел зачiпки у стек.

2. Доки стек не є порожнiм:

а) Вибрати пiксел iз стека. Розглядати його як поточний пiксел.

в) Надати пiкселу потрiбне значення.

с) Заповнити (тобто вiдмiтити пiкселi) iнтервал, що мiстить зачiпку, лiворуч i праворуч вiд зачiпки доти, доки не буде досягнута границя. У змiнних Xleft i Xright запам'ятати крайнi пiкселi iнтервалу.

d) У дiапазонi XleftXe ≤Xright перевiряємо рядки, що розташованi безпосередньо над i пiд рядком, що сканується. Визначаємо, є на цих рядках пiкселi (тобто, не всi пiкселi є граничними, або вже є заповненими). Якщо такi пiкселi ще є, то для кожного неперервного iнтервалу з цих рядкiв у дiапазонi XleftXe ≤Xright до стеку заносимо кожен крайнiй правий пiксел (як можливий пiксел зачiпки).

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

Загрузка...

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти