2.2.2 Алгоритм заповнення за ребрами

Алгоритм з упорядкованим списком ребер дуже потужний. Кожний пiксел зображення активується тiльки один раз, отже мiнiмiзованi операцiї введення-виведення. Головний недолiк -- дуже великi втрати на пiдтримання i сортування рiзних спискiв. У наступному алгоритмi заповнення за ребрами бiльшiсть з таких спискiв вiдсутня.

Алгоритм заповнення за ребрами: Для кожного рядка, що сканується i що перетинає ребро багатокутника в точцi (x_k, y_k), iнвертувати всi пiкселi, у яких центри лежать справа вiд точки перетину (x_k, y_k), тобто для яких x+1/2>x_k .

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

Головний недолiк цього алгоритму -- для складного багатокутника (без перетинiв сторiн) кожен пiксел буде iнвертуватися багато разiв. Отже, ефективнiсть алгоритму обмежена швидкiстю вводу/виведення.

Програма, що реалiзує алгоритм заповнення за ребрами.

unit FillBySides1;

interface

uses

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

Forms, Dialogs, StdCtrls;

const

N = 100; {максимальне число вершин багатокутника}

_Xmax = 10; _Ymax = 8;{розмiри буфера кадру}

type

TForm1 = class(TForm)

Button1: TButton;

procedure Button1Click(Sender: TObject);

private { Private declarations }

public { Public declarations }

end;

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

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

Pi = array[0.._Ymax,0.._Xmax] of boolean; {буфер кадру}

var

Form1: TForm1;

NP,Xmax,Ymax,i : integer;

X,Y : real;

P : Border;

M : Pi;

fin : text;

implementation {$R *.DFM}

{встановлення границi багатокутника}

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

begin {SetP}

AssignFile(fin,'Raster1b.dat'); reset(fin); NP:=0;

while (not Eof(fin)) do

begin NP:=NP+1; readln(fin,P[NP,1],P[NP,2]) end;

CloseFile(fin);

end; {SetP}

{встановлення початкових значень елементiв буфера кадру}

procedure SetM(var M:Pi;Xmax,Ymax:integer);

var i,j:integer;

begin {SetM}

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

end; {SetM}

{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;

{виведення растра}

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

var i,j:integer;

begin {TypeRastr}

for i:=0 to Ymax do

begin {for j}

for j:=0 to Xmax do begin {for i}

if M[i,j]=true

then Form1.Canvas.Pixels[j,i]:=clRed

else Form1.Canvas.Pixels[j,i]:=clBlack;

end; {for i}

end; {for j}

end; {TypeRastr}

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

procedure Scan(P:Border;NP:integer;

var M:Pi;Xmax,Ymax:integer);

var i,j,k:integer; x,y:real;

begin {Scan}

for k:=1 to NP-1 do

begin {for k}

for i:=0 to Ymax-1 do

begin {for i}

y:=i+0.5;

if (P[k,2]<>P[k+1,2])and(((P[k,2]<=y)and(y<=P[k+1,2]))

or((P[k+1,2]<=y)and(y<=P[k,2])))

then begin

x:=P[k,1]+(P[k+1,1]-P[k,1])*((y-P[k,2])/(P[k+1,2]-P[k,2]));

for j:=0 to Xmax do

begin if j+0.5>x then Inv(M,i,j); end;

end;

end; {for i}

TypeRastr(M,Xmax,Ymax);

end; {for k}

for i:=0 to Ymax-1 do

begin {for i}

y:=i+0.5;

if (P[NP,2]<>P[1,2])and (((P[NP,2]<=y)and(y<=P[1,2]))

or((P[1,2]<=y)and(y<=P[NP,2])))

then begin

x:=P[NP,1]+(P[1,1]-P[NP,1])*((y-P[NP,2])/(P[1,2]-P[NP,2]));

for j:=0 to Xmax do begin if j+0.5>x then Inv(M,i,j); end;

end;

end; {for i}

TypeRastr(M,Xmax,Ymax);

end; {Scan}

procedure TForm1.Button1Click(Sender: TObject);

begin {TForm1.Button1Click}

// встановлення розмiрiв буфера кадру

Xmax:=_Xmax; Ymax:=_Ymax;

// встановлення вершин багатокутника

SetP(P,NP);

// початкове встановлення буфера кадру

SetM(M,Xmax,Ymax);

// заповнення багатокутника за ребрами

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

// виведення буфера кадру

TypeRastr(M,Xmax,Ymax);

end; {TForm1.Button1Click}

end.

Зауваження 3 Для багатокутника, який було розглянуто в алгоритмi з упорядкованим списком ребер, дiя алгоритму заповнення за ребрами вiдрiзняється вiд дiї алгоритму з упорядкованим списком ребер. Наприклад, у даному алгоритмi не активуються пiкселi (5,3), (6,4) i (7,5). Вiдмiна буде для тих пiкселiв, що подiляються ребром навпiл. У алгоритмi з упорядкованим списком ребер цi пiкселi завжди активуються, а у алгоритмi заповнення за ребрами вони активуються тiльки тодi, коли середня частина багатокутника є злiва вiд центру пiкселя.

Зауваження 4 Найбiльш зручне використання цього алгоритму сумiсно з буфером кадру, що дозволяє обробляти ребра у довiльному порядку.

Зауваження 5 Завдяки симетрiї вiдносно напрямкiв осей у буферi кадру можливi чотири реалiзацiї цього алгоритму. Якщо попереднiй напрямок iнвертування пiкселiв назвати як "вiтер справа - налiво", то iншi напрямки iнвертування це вiтри "злiва - у право", "зверху - у низ", "знизу - до верху".

Зауваження 6 Число пiкселiв, які обробляються, можна скоротити, якщо ввести так звану перегородку i отримати алгоритм заповнення з перегородкою. Перегородка - це прямолiнiйний сегмент з пiкселiв, який обмежує габаритну область багатокутника.

Алгоритм заповнення з перегородкою. Для кожного рядка, що сканується i що перетинає ребро багатокутника:

1. Якщо перетин є зліва вiд перегородки, тодi iнвертувати всi пiкселi, якi лежать злiва вiд перетину рядка, що сканується, з ребром i злiва вiд перегородки.

2. Якщо перетин знаходиться справа в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тература. [ 5, стор. 105-106].