Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН- 411
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 9
з дисципліни “Комп’ютерна графіка”
Тема: Простий алгоритм заповнення з запалом
Мета: Освоїти алгоритм заповнення гранично-визначеної області
ТЕОРЕТИЧНІ ОСНОВИ
ПОРЯДКОВИЙ АЛГОРИТМ ЗАПОВНЕННЯ З ЗАПАЛОМ
Даний алгоритм застосовується до гранично-визначених областей. Гранично-визначена 4-зв'язна область може бути як опуклою, так і не опуклою, а також може містити діри. В зовнішній області, пов'язаній з нашою гранично-визначеною областю, не повинно бути пікселів з кольором, яким заповнюється область чи багатокутник. Схематично роботу алгоритму можна розбити на чотири етапи.
Порядковий алгоритм заповнення з запалом
Затравочний піксел на інтервалі витягається зі стека, що містить затравочні піксели.
Інтервал із затравочним пікселем заповнюється вліво і вправо від запалу уздовж скануючого рядка доти, поки не буде знайдена границя. У змінних Хлів і Хправ запам'ятовуються крайній лівий і крайній правий піксели інтервалу.
У діапазоні Хлів<х<Хправ перевіряються рядки, розташовані безпосередньо над і під біжучим рядком. Визначається, чи є на них ще не заповнені піксели. Якщо такі піксели є (тобто не всі піксели граничні, чи уже заповнені), то в зазначеному діапазоні крайній правий зазначений піксел у кожнім інтервалі відзначається як затравочний і поміщується в стек.
При ініціалізації алгоритму в стек поміщується єдиний затравочний піксел, робота завершується при спустошенні стека. Алгоритм справляється з дірами і зубцями на границі.
Порядковий алгоритм заповнення з запалом
Запал (х, у) видає затравочний піксел
Pop - процедура, що витягає піксел зі стека
Push - процедура, що поміщає піксел у стек
Ініціалізуємо стек
Push Запал(х, у)
While (стек не порожній)
Вибираємо піксел зі стека і привласнюємо йому нове значення
Pop Піксел(х, у)
Піксел(х, у)=Нове_значення
Зберігаємо х-координату затравочного піксела
ТимЧас_х=х
Заповнюємо інтервал праворуч від запалу
х=х+1
while Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х+1
end while
зберігаємо крайній праворуч піксел
Хправ=х-1
Відновлюємо х-координату запалу
х=ТимЧас_х
заповнюємо інтервал ліворуч від запалу
х=х-1
While Піксел(х, у)<>Гран_значення
Піксел(х, у)=Нове_значення
х=х-1
end while
зберігаємо крайній ліворуч піксел
Хлів=х+1
Відновлюємо х-координату запалу
х=ТимЧас_х
перевіримо, що рядок вище не є ні границею багатокутника, ні вже цілком заповнений; якщо це не так, то знайти запал, починаючи з лівого краю підінтервала скануючого рядка.
х=Хлів
у=у+1
while х ? Хправ
шукаємо запал на рядку вище
Прапор=0
While (Піксел(х, у)<>Гран_значення and
Піксел(х, у)<>Нове_значення and х<Хправ
If Прапор=0 then Прапор=1
х=х+1
end while
поміщаємо в стек крайній правий піксел
if Прапор=1 then
if (х=Хправ and Піксел(х, у)<>Гран_значення
and Піксел(х, у)<>Нове_значення) then
Push Піксел(х, у)
Else
Push Піксел(х-1, у)
End if
Прапор=0
End if
Продовжимо перевірку, якщо інтервал був перерваний
Хвход=х
While ((Піксел(х, у)=Гран_значення or Піксел(х, у)=Нове_значення)
and х<Хправ)
х=х+1
end while
упевнимося, что координата піксела збільшена
if х=Хвход then х=х+1
end while
перевіримо, що рядок нижче не є ні границею багатокутника, ні вже цілком заповнений
ця частина алгоритму зовсім аналогічна перевірці для рядка вище, за винятком того, що замість у=у+1 треба поставити у =у-1
end while
finish
Тут функція Pop вибирає координати х, у піксела із стека, а функція Push поміщає їх у стек.
Текст програми:
//---------------------------------------------------------------------------
#include <vcl.h>
#include <mmsystem.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
TColor newcol,oldcol;
int x,y;
int ig, ix[350][10], c;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
int i, j;
// Defaults
Polygon->Cells[0][0]=" X";
Polygon->Cells[0][1]=" Y";
Polygon->Cells[1][0]="3";
Polygon->Cells[1][1]="3";
Polygon->Cells[2][0]="5";
Polygon->Cells[2][1]="9";
Polygon->Cells[3][0]="9";
Polygon->Cells[3][1]="7";
Polygon->Cells[4][0]="11";
Polygon->Cells[4][1]="7";
Polygon->Cells[5][0]="10";
Polygon->Cells[5][1]="2";
Polygon1->Cells[0][0]=" X";
Polygon1->Cells[0][1]=" Y";
Polygon1->Cells[1][0]="4";
Polygon1->Cells[1][1]="4";
Polygon1->Cells[2][0]="5";
Polygon1->Cells[2][1]="7";
Polygon1->Cells[3][0]="6";
Polygon1->Cells[3][1]="8";
Polygon1->Cells[4][0]="7";
Polygon1->Cells[4][1]="7";
Polygon1->Cells[5][0]="6";
Polygon1->Cells[5][1]="5";
StringGrid1->Cells[0][0]="X";
StringGrid1->Cells[0][1]="Y";
StringGrid1->Cells[1][0]="4";
StringGrid1->Cells[1][1]="5";
DefaultDrawing();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::DefaultDrawing(void)
{
int i,j,sc;
// Drawing
Screen->Canvas->Pen->Color=clBlack;
Screen->Canvas->Pen->Width=1;
Screen->Canvas->Rectangle(0,0,360,360);
// axis OX
Screen->Canvas->MoveTo(10,350);
Screen->Canvas->LineTo(350,350);
// axis OY
Screen->Canvas->MoveTo(10,10);
Screen->Canvas->LineTo(10,350);
// Scaling
sc=StrToInt(3);
Screen->Canvas->Pen->Color=clGray;
for(i=10,j=350;i<=350 || j>=10;i+=10*sc,j-=10*sc)
{
Screen->Canvas->MoveTo(i,1);
Screen->Canvas->LineTo(i,352);
Screen->Canvas->MoveTo(349,j);
Screen->Canvas->LineTo(9,j);
}
for(i=9,j=0;i<350;j++,i+=30){
Screen->Canvas->TextOutA(i,350,j);
}
for(i=315,j=0;i>0;j++,i-=30){
Screen->Canvas->TextOutA(3,i,j+1);
}
Screen->Canvas->Pen->Color=clBlack;
for(i=0;i<350;i++)
{
for(j=0;j<10;j++) { ix[i][j]=0; }
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ScalingChange(TObject *Sender)
{
DefaultDrawing();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ClearClick(TObject *Sender)
{
DefaultDrawing();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BuiltClick(TObject *Sender)
{
int s,xA, yA, xB, yB, xC, yC, xD, yD, xE, yE, sc;
DefaultDrawing();
sc=StrToInt(3);
s=ComboBox1->ItemIndex;
Edit1->Text=IntToStr(s);
xA=StrToInt(Polygon->Cells[1][0]);
yA=StrToInt(Polygon->Cells[1][1]);
xB=StrToInt(Polygon->Cells[2][0]);
yB=StrToInt(Polygon->Cells[2][1]);
xC=StrToInt(Polygon->Cells[3][0]);
yC=StrToInt(Polygon->Cells[3][1]);
xD=StrToInt(Polygon->Cells[4][0]);
yD=StrToInt(Polygon->Cells[4][1]);
xE=StrToInt(Polygon->Cells[5][0]);
yE=StrToInt(Polygon->Cells[5][1]);
Screen->Canvas->Pen->Color=clBlack;
Screen->Canvas->Pen->Width=1;
Screen->Canvas->MoveTo(xA*10*sc+10,-yA*10*sc+350);
Screen->Canvas->LineTo(xB*10*sc+10,-yB*10*sc+350);
Screen->Canvas->LineTo(xC*10*sc+10,-yC*10*sc+350);
if (s==1) {
Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350);
Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
}
if (s==2) {
Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350);
Screen->Canvas->LineTo(xE*10*sc+10,-yE*10*sc+350);
Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
}
if(s==0) Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
Screen->Canvas->Pen->Color=clBlack;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
Flood (int x,int y,TColor oldcol,TColor newcol)
{
if (Form1->Screen->Canvas->Pixels[x][y]==Form1->Color || Form1->Screen->Canvas->Pixels[x][y]==clGray)
{
Form1->Screen->Canvas->Pixels[x][y]=newcol;
Flood(x+1,y,oldcol,newcol);
Flood(x-1,y,oldcol,newcol);
Flood(x,y-1,oldcol,newcol);
Flood(x,y+1,oldcol,newcol);
}
}
void __fastcall TForm1::FillBClick(TObject *Sender)
{
int x0,y0,tempx, tempy , x_pot, y_pot;
x0=40;
y0=540;
x_pot=StrToInt(StringGrid1->Cells[1][0]);
y_pot=StrToInt(StringGrid1->Cells[1][1]);
tempx=x_pot*30+10;
tempy=-y_pot*30+350;
//Form1->Screen->Canvas->Pixels[tempx][tempy]=clBlue;
Flood(tempx,tempy,clWhite,clBlue);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::CheckPoint(void)
{
int ks,sc, j;
float m[10], x,y, x1,y1, x2,y2, Dx,Dy, s1,s2, Obmin, Temp, i, e;
sc=StrToInt(3);
ks=(ComboBox1->ItemIndex)*2+6;
Edit1->Text=ks;
m[0]=StrToInt(Polygon->Cells[1][0]);
m[1]=StrToInt(Polygon->Cells[1][1]);
m[2]=StrToInt(Polygon->Cells[2][0]);
m[3]=StrToInt(Polygon->Cells[2][1]);
m[4]=StrToInt(Polygon->Cells[3][0]);
m[5]=StrToInt(Polygon->Cells[3][1]);
if (ks==8||ks==10) {
m[6]=StrToInt(Polygon->Cells[4][0]);
m[7]=StrToInt(Polygon->Cells[4][1]);
}
else {m[6]=0; m[7]=0;}
if (ks==10){
m[8]=StrToInt(Polygon->Cells[5][0]);
m[9]=StrToInt(Polygon->Cells[5][1]);
}
else {m[8]=0; m[9]=0;}
for(j=0;j<ks;j+=2)
{
x1=m[j]*10*sc;
y1=m[j+1]*10*sc;
if(j==8&&ks==10)
{
x1=m[0]*10*sc;
y1=m[1]*10*sc;
x2=m[8]*10*sc;
y2=m[9]*10*sc;
goto A;
}
if(j==6&&ks==8)
{
x1=m[0]*10*sc;
y1=m[1]*10*sc;
x2=m[6]*10*sc;
y2=m[7]*10*sc;
goto A;
}
if(j==4&&ks==6)
{
x1=m[0]*10*sc;
y1=m[1]*10*sc;
x2=m[4]*10*sc;
y2=m[5]*10*sc;
goto A;
}
// else {
x2=m[j+2]*10*sc;
y2=m[j+3]*10*sc;
// }
A: x=x1;
y=y1;
Dx=abs(x2-x1);
Dy=abs(y2-y1);
s1=x2-x1<0?-1:1;
if(Dx==0) { s1=0; }
s2=y2-y1<0?-1:1;
if(Dy==0) { s2=0; }
if(Dx<Dy)
{
Temp=Dx;
Dx=Dy;
Dy=Temp;
Obmin=1;
}
else
{
Obmin=0;
}
e=2*Dy-Dx;
for(i=0;i<=Dx;i++)
{
//point
if(ig==y)
{
if(x==ix[ig][c-1])
{
if(((m[j+1]>m[j+3] && m[j+1]>m[j-1]) || (m[j+1]<m[j+3] && m[j+1]<m[j-1])))
{
ix[ig][c]=x;
c++;
}
goto NeL;
}
ix[ig][c]=x;
c++;
goto NeL;
}
while(e>=0)
{
if(Obmin==1) { x=x+s1; }
else { y=y+s2; }
e=e-2*Dx;
}
if(Obmin==1) { y=y+s2; }
else { x=x+s1; }
e=e+2*Dy;
}
NeL:
}
}
void __fastcall TForm1::Timer1Timer(TObject *Sender)
{
int i,ks;
ks=(ComboBox1->ItemIndex)*2+6;
if(ig==350)
{
Timer1->Enabled=false;
}
else
{
Screen->Canvas->Pen->Color=clRed;
for(i=0;i<ks;i+=2)
{
if(ix[ig][i]!=0 && ix[ig][i+1]!=0)
{
Screen->Canvas->MoveTo(ix[ig][i]+10,-ig+350);
Screen->Canvas->LineTo(ix[ig][i+1]+10,-ig+350);
}
}
Screen->Canvas->Pen->Color=clBlack;
}
ig++;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ComboBox1Change(TObject *Sender)
{
int s;
char ch[10];
s=ComboBox1->ItemIndex;
Edit1->Text=s;
ch[1]=Edit1->Text[1];
switch(ch[1]){
case '0':
Polygon->ColCount=4;
Polygon->Width=38*(4);
break;
case '1':
Polygon->ColCount=5;
Polygon->Width=38*(5);break;
case '2':
Polygon->ColCount=6;
Polygon->Width=38*(6);break;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
int s,xA, yA, xB, yB, xC, yC, xD, yD, xE, yE, sc;
//DefaultDrawing();
sc=StrToInt(3);
s=ComboBox2->ItemIndex;
Edit1->Text=IntToStr(s);
xA=StrToInt(Polygon1->Cells[1][0]);
yA=StrToInt(Polygon1->Cells[1][1]);
xB=StrToInt(Polygon1->Cells[2][0]);
yB=StrToInt(Polygon1->Cells[2][1]);
xC=StrToInt(Polygon1->Cells[3][0]);
yC=StrToInt(Polygon1->Cells[3][1]);
xD=StrToInt(Polygon1->Cells[4][0]);
yD=StrToInt(Polygon1->Cells[4][1]);
xE=StrToInt(Polygon1->Cells[5][0]);
yE=StrToInt(Polygon1->Cells[5][1]);
Screen->Canvas->Pen->Color=clBlack;
Screen->Canvas->Pen->Width=1;
Screen->Canvas->MoveTo(xA*10*sc+10,-yA*10*sc+350);
Screen->Canvas->LineTo(xB*10*sc+10,-yB*10*sc+350);
Screen->Canvas->LineTo(xC*10*sc+10,-yC*10*sc+350);
if (s==1) {
Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350);
Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
}
if (s==2) {
Screen->Canvas->LineTo(xD*10*sc+10,-yD*10*sc+350);
Screen->Canvas->LineTo(xE*10*sc+10,-yE*10*sc+350);
Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
}
if(s==0) Screen->Canvas->LineTo(xA*10*sc+10,-yA*10*sc+350);
Screen->Canvas->Pen->Color=clBlack;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ComboBox2Change(TObject *Sender)
{
int s;
char ch[10];
s=ComboBox2->ItemIndex;
Edit1->Text=s;
ch[1]=Edit1->Text[1];
switch(ch[1]){
case '0':
Polygon1->ColCount=4;
Polygon1->Width=38*(4);
break;
case '1':
Polygon1->ColCount=5;
Polygon1->Width=38*(5);break;
case '2':
Polygon1->ColCount=6;
Polygon1->Width=38*(6);break;
}
}
//---------------------------------------------------------------------------
Висновок:
На даній лабораторній роботі я освоїв алгоритм заповнення гранично-визначеної області з запалом і реалізував його програмно.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора