Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Лабораторна робота № 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; } } //--------------------------------------------------------------------------- Висновок: На даній лабораторній роботі я освоїв алгоритм заповнення гранично-визначеної області з запалом і реалізував його програмно.