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


Програма, що реал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].

2.2.3 Алгоритм заповнення iз списком ребер i прапорцем

Алгоритм заповнення iз списком ребер i прапорцем є двокроковим.

Перший крок.Креслення контуру, завдяки чому на кожному рядку, що сканується, утворюються пари обмежуючих (граничних) пiкселiв. Користуючись угодою про середину iнтервалу мiж рядками, що скануються, для кожного ребра, яке перетинає такий рядок, потрiбно вiдмiтити самий лiвий пiксел, середина якого лежить справа вiд точки перетину xcross, тобто x+1/2>xcross

Другий крок.Заповнення пiкселiв мiж парами обмежуючих пiкселiв:

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

Початок.

Inside = FALSE;

for X=0 {лiва границя} to X = Xmax {права границя} do

begin

if < x-пiксел має граничне значення > then < iнвертування змiнної Inside >

if Inside=TRUE

then < вiдмiтити x-пiксел як належний до середини багатокутника >

else < вiдмiтити x-пiксел як зовнiшнiй до багатокутника >

Кiнець.

 

Програмна реалiзацiя

unit SidesAndFlagUnit1;

іnterface

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

Forms, Dialogs, StdCtrls;

const _Nborder =100; {максимальна кiлькiсть вершин}

type TForm1 = class(TForm)

Button, Button2, Button3: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure FormDestroy(Sender: TObject);

private { Private declarations }

public { Public declarations }

end;

PointInt=array[1..2] of integer;

Polygon=array[1.._NBorder] of PointInt;

var

Form1: TForm1;

YesContour:boolean;{ознака введення вершин}

NP, {число вершин багатокутника}

Xmin,Xmax, {границi по вiсi ОХ багатокутника}

Ymin,Ymax {дiапазон рядкiв, що скануються}

: integer;

P:Polygon; {вершини багатокутника}

implementation {$R *.DFM}

// Iнвертування ознаки Inside

procedure InvBool(var Inside:boolean);

begin {InvBool}

if Inside then Inside:=false else Inside:=true;

end; {InvBool}

 

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

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

var

x,y:integer;

fin : text; {файл з вершинами багатокутника}

begin {SetP}

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

while (not Eof(fin)) do

begin

NP:=NP+1;readln(fin,x,y);P[NP,1]:=x;P[NP,2]:=y;

if NP=1

then begin Xmin:=x;Xmax:=x;Ymin:=y;Ymax:=y; end

else begin

if Xmin>x then Xmin:=x; if Xmax<x then Xmax:=x;

if Ymin>y then Ymin:=y; if Ymax<y then Ymax:=y;

end;

end;

CloseFile(fin);

end; {SetP}

 

// Креслення контуру

procedure AbrisLine(Xs,Ys,Xf,Yf,ColorR:integer);

var

x,y,Ystrt,Yfin,Xcross: real;

begin {AbrisLine}

if Ys<>Yf

then begin {Ys<>Yf}

// встановлення промiжку [Ystrt,Yfin] змiни y

if Ys>Yf then begin Ystrt:=Yf;Yfin:=Ys;end;

if Ys<Yf then begin Ystrt:=Ys;Yfin:=Yf;end;

y:=Ystrt+0.5;

while (y<Yfin) do begin

// знаходження х-координати перетину рядка з вiдрiзком

Xcross:=Xs+(y-Ys)*((Xs-Xf)/(Ys-Yf));

// знаходження найбiльш лiвого цiлого х,

що лежить справа вiд перетину

x:=round(Xcross-0.5);

if x<=Xcross-0.5 then x:=x+1;

// виведення вiдповiдного пiкселя

Form1.Canvas.Pixels[round(x),round(y-0.5)]:=ColorR;

// встановлення наступного значення у

y:=y+1;

end;

end; {Ys<>Yf}

end; {AbrisLine}

 

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

procedure FlagRasterPolygon(P:Polygon;

NP:integer;ColorR:integer);

var Inside:boolean; {прапорець}

i,j:integer;s:string;

begin {FlagRasterPolygon}

for j:=Ymin to Ymax do

begin {j:=Ymin to Ymax}

Inside:=false;

for i:=Xmin to Xmax do

begin {i:=Xmin to Xmax}

if B[i,j] then InvBool(Inside);

if Inside

then begin

B[i,j]:=true;Form1.Canvas.Pixels[i,j]:=ColorR;

end;

end; {i:=Xmin to Xmax}

end; {j:=Ymin to Ymax}

end; {FlagRasterPolygon}

 

procedure TForm1.Button1Click(Sender: TObject);

var i:integer;

begin {TForm1.Button1Click}

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

YesContour:=true;SetP(P,NP);

for i:=1 to NP-1 do

AbrisLine(P[i,1],P[i,2],P[i+1,1],P[i+1,2],clRed);

AbrisLine(P[NP,1],P[NP,2],P[1,1],P[1,2],clRed);

end; {TForm1.Button1Click}

 

procedure TForm1.Button2Click(Sender: TObject);

begin {TForm1.Button2Click}

if YesContour then FlagRasterPolygon(P,NP,clBlack);

end; {TForm1.Button2Click}

 

procedure TForm1.Button3Click(Sender: TObject);

begin {TForm1.Button3Click}

Form1.Close;

end; {TForm1.Button3Click}

 

procedure TForm1.FormCreate(Sender: TObject);

begin {TForm1.FormCreate}

YesCountour:=false;

end; {TForm1.FormCreate}

 

end. {SidesAndFlagUnit1}

 

Зауваження 7 У алгоритмі заповнення за ребрами i прапорцем кожен пiксел обробляється тiльки один раз. Тому вiн бiльш доцiльнiший нiж алгоритм з списком ребер або алгоритм з перегородкою.

Зауваження 8 Алгоритм заповнення за ребрами (з перегородкою чи нi) або алгоритм заповнення за ребрами з прапорцем при роботi з буфером кадру не потребують побудови, пiдтримки i сортування будь-яких спискiв.

Зауваження 9 При програмнiй реалiзацiї алгоритм з упорядкованим списком ребер i алгоритм з списком ребер i прапорцем виконуються приблизно з однаковою швидкiстю. Але при апаратнiй реалiзацiї алгоритм з списком ребер i прапорцем виконується на один-два порядка швiдше нiж алгоритм з упорядкованим списком ребер.

Лiтература.[14, стор. 107-111].

 

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 G1={(x, y)|2 ≤ x ≤ 8,2 ≤ y ≤ 6} -- внутрiшнє-визначена область.

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

Г2= {(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 Область G1 з прикладу 1 визначена границею

Г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Область G3, яка визначена границею

Г3={(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-звязними. Область G1$ з прикладу 1 є як 4- так i 8-зв'язною. Область

G4= {(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.

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