2.2.4 Простий алгоритм заповнення 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шнє-визначеної областi пiкселi, що належать до середини областi, мають один колiр (iнтенсивнiсть), а всi пiкселi, що є зовнiшнiми до цiєї областi, мають iнший колiр (iнтенсивнiсть).

Приклад 1 G₁={(x, y)|2 ≤ x ≤ 8,2 ≤ y ≤ 6} -- внутрiшнє-визначена область.

Приклад 2 Область G₂, яка має граничнi пiкселi

Г₂= {(1,3),(2,3),(1,4),(2,4); (3,1),(3,2),(4,1),(4,2)}

є гранично-визначеною областю.

Для гранично-визначеної областi пiкселi на границi областi мають визначений колiр, а всi пiкселi, що належать до середини областi, не можуть мати цього кольору (але пiкселi, що є зовнiшнiми до цiєї границi, вже можуть мати цей колiр).

Приклад 3 Область G₁ з прикладу 1 визначена границею

Г₁= {(1,2),(1,3),(1,4),(1,5);\;(2,6),(3,6),(4,6),(5,6),(6,6),(7,6);

(8,2),(8,3),(8,4),(8,5);(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)}

як гранично-визначена область.

Приклад 4 Область G₃, яка визначена границею

Г₃={(2,6),(3,6);\;(4,5),(4,4),(5,4);\;(3,6),(2,6);

(5,1),(4,1_;\;(3,2),(3,3),(2,3);\;(1,4),(1,5)\},

є гранично-визначеною областю.

Внутрiшнє- або гранично-визначенi областi можуть бути 4- або 8-зв'язними.

Область є 4-зв'язною, якщо вiд будь-якого пiкселя цiєї областi можна перейти до будь-якого iншого пiкселя цiєї областi за допомогою комбiнацiї перемiщень на один крок у 4-x напрямках: праворуч, лiворуч, догори i униз.

Для 8-зв'язної областi до цих перемiщень ще додаються 4 перемiщення у 4-x дiагональних напрямках. Будь-який алгоритм з зачiпкою для 8-зв'язної областi можна використовувати для заповнення 4-зв'язної областi, зворотне вже може бути не вiрним.

Внутрiшнє-визначенi областi можуть бути як 4- так i 8-звязними. Область G₁$ з прикладу 1 є як 4- так i 8-зв'язною. Область

G₄= {(1,3),(2,3);\;(1,4),(2,4);\;(3,1),(3,2);\;(4,1),(4,2)}

є 8-зв'язною.

Гранично-визначенi областi також можуть бути як 4- так i 8-звязними. Наприклад, гранично-визначена область з прикладу 2 є як 4- так i 8- зв'язною. Але гранично-визначена область з прикладу 4 є 8-звязною.

Далi 8-зв'язнi областi, якi є також 4-зв'язними, будемо вважати тiльки 4-зв'язними.

Легко перевiрити, що областi, границi яких породжуються вiдрiзками прямих i дугами кола за алгоритмами Брезенхема, є 4-зв'язнi областi.

Далi будемо розглядати лише алгоритми заповнення 4-звязних областей, але їх легко переробити на 8-зв'язнi областi, якщо заповнення проводити не у 4-х, а у 8-и напрямках.

Наведемо простий алгоритм заповнення гранично-визначеної областi з використанням стека.

Стек - це масив або iнша структура даних, у яку можна послiдовно розмiщати значення, i з якої їх можна послiдовно вибирати. Коли новi значення додаються до або розмiщуються у стеку, всi iншi значення перемiщуються вниз на один рiвень. Коли значення видаляються або вибираються з стеку, iншi значення випливають або пiдiймаються угору на один рiвень. Такий стек має назву стека прямої дiї або стеком з дисциплiною обслуговування "першим прийшов, останнiм вийшов" (FILO - First In Last Out). Простий алгоритм заповнення з зачiпкою можна подати у наступному виглядi.

Простий алгоритм заповнення 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;