с) Для кожного з сус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нних X_left i X_right запам'ятати крайнi пiкселi iнтервалу.

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

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

Предыдущая 1 2 3 4 567 Следующая