Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПРОСТИЙ АЛГОРИТМ ЗАПОВНЕННЯ З ЗАПАЛОМ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Комп'ютерна графіка
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
Лабораторна робота №9
з дисципліни
«Комп’ютерна графіка»
на тему:
“ ПРОСТИЙ АЛГОРИТМ ЗАПОВНЕННЯ З ЗАПАЛОМ”.
Львів – 2008
Мета: Ознайомлення з основами комп‘ютерної графіки.
Теоретичні основи.
Використовуючи стек, можна розробити простий алгоритм заповнення гранично-визначеної області. Стек - це просто масив чи інша структура даних, в яку можна послідовно поміщати значення і з якої їх можна послідовно виймати. Коли нові значення додаються чи поміщаються в стек, всі інші значення опускаються вниз на один рівень. Коли значення виймаються чи видаляються із стека, інші значення спливають чи піднімаються нагору на один рівень. Такий стек називається стеком прямої дії чи стеком з порядком обслуговування "першим прийшов, останнім вийшов" (FILO). Простий алгоритм заповнення з запалом можна представити в наступному вигляді:
Простий алгоритм заповнення з запалом і стеком
Помістити затравочний піксел у стек
Поки стек не порожній
Витягти піксел зі стека
Привласнити пікселу необхідне значення
Для кожного із сусідніх до біжучого 4-зв’язних пікселів перевірити: чи є він граничним пікселом чи не привласнене пікселу необхідне значення. Проігнорувати піксел у кожнім з цих двох випадків. В іншому випадку помістити піксел у стек.
Алгоритм можна модифікувати для 8-зв'язних областей, якщо переглядати 8-связні піксели, а не тільки 4-зв'язні. Наведемо більш формальний виклад алгоритму, у якому передбачається існування затравочного піксела і гранично-визначеної області.
Простий алгоритм заповнення.
Запал (х, у) видає затравочний піксел
Push - процедура, що поміщає піксел у стек
Pop - процедура, що витягає піксел зі стека
Піксел (х, у) = Запал (х, у)
Ініціалізуємо стек
Push Піксел (х, у)
While (стек не порожній)
Вибираємо піксел зі стека
Pop Піксел (х, у)
If Піксел(х, у)<>Нове_значення then
Піксел(х, у)=Нове_значення
End if
Перевіримо, чи треба поміщати сусідні піксели в стек
If (Піксел(х+1, у)<>Нове_значення and
Піксел(х+1, у)<>Гран_значення) Then
Push Піксел(х+1, у)
If (Піксел(х, у+1)<>Нове_значення and
Піксел(х, у+1)<>Гран_значення) Then
Push Піксел(х, у+1)
If (Піксел(х-1, у)<>Нове_значення and
Піксел(х-1, у)<>Гран_значення) Then
Push Піксел(х-1, у)
If (Піксел(х, у-1)<>Нове_значення and
Піксел(х, у-1)<>Гран_значення) Then
Push Піксел(х, у-1)
End if
End while
В алгоритмі перевіряються і поміщаються в стек 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 <math>
#include <stack>
using namespace std;
#include <stdio>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "CSPIN"
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{}
//---------------------------------------------------------------------------
int k;//mashtab
int kp;//k-st' to4ok
struct point{
unsigned x;
unsigned y;};
stack<point> pstack;
const int MaxBuff=50;
void DrawGrid(){
TRect r;
r.Left=0;
r.top=0;
r.right=Form1->Image1->Width;
r.Bottom=Form1->Image1->Height;
Form1->Image1->Canvas->FillRect(r);
int x=0, y=0;
while(x< Form1->Image1->Width){
Form1->Image1->Canvas->MoveTo(x,0);
Form1->Image1->Canvas->LineTo(x,Form1->Image1->Height);
x+=k; }
while(y<Form1->Image1->Height){
Form1->Image1->Canvas->MoveTo(0,y);
Form1->Image1->Canvas->LineTo(Form1->Image1->Width,y);
y+=k;
}}
void SetPixel(int x,int y,int color){
TRect r;
r.Left=x*k+1;
r.top=(y+1)*k;
r.right=(x+1)*k;
r.Bottom=y*k+1;
Form1->Image1->Canvas->Brush->Color=color;
Form1->Image1->Canvas->FillRect(r);
Form1->Image1->Canvas->Brush->Color=0xffffff;
}
void DrawLine(int x1,int y1,int x2,int y2){
int kx=1,ky=1;
double dx,dy,x,y;
int prevx=-1;
int prevy=-1;
int lx=abs(x1-x2);
int ly=abs(y1-y2);
int temp=0;
if(x1>x2) kx=-1;
if(y1>y2) ky=-1;
if(lx>ly){
dy=ly/(double)lx; y=y1;
for(int x=x1;lx>=abs(x1-x);x+=kx){
SetPixel(x,(int)(y+0.5),0xcaca);
y+=dy*ky;
} }else{
dx=lx/(double)ly;
x=x1;
for(int y=y1;ly>=abs(y1-y);y+=ky){
SetPixel((int)(x+0.5),y,0xcaca);
x+=dx*kx;
} }}
bool White(int x,int y){
if(Form1->Image1->Canvas->Pixels[x*k+k/2][y*k+k/2]==0xffffff)
return true;
else
return false;
}void Fill(){
point p,t;
while(!pstack.empty()){
p=pstack.top();
pstack.pop();
if(White(p.x,p.y))
SetPixel(p.x,p.y,0xaaaaaa);
t=p;
t.x++;
if(White(t.x,t.y))
pstack.push(t);
t=p; t.x--;
if(White(t.x,t.y))
pstack.push(t);
t=p; t.y++;
if(White(t.x,t.y))
pstack.push(t);
t=p; t.y--;
if(White(t.x,t.y))
pstack.push(t);
}}
//-----------------------------------------------------------------
void __fastcall TForm1::FormShow(TObject *Sender)
{
k=(Image1->Width < Image1->Height ? Image1->Width : Image1->Height)/CSpinEdit1->Value;
CSpinEdit1->MaxValue=CSpinEdit1->MinValue+MaxBuff;
DrawGrid();
}
//---------------------------------------------------------------------------
int x1,y1,x2,y2;
void __fastcall TForm1::Image1MouseDown(TObject *Sender,
TMouseButton Button, TShiftState Shift, int X, int Y)
{ x1=X/k; y1=Y/k;
if(Button==mbLeft){
SetPixel(x1,y1,0xcacaca);
kp++;
CSpinEdit1->Enabled=false;
if(kp>1)
DrawLine(x1,y1,x2,y2);
x2=x1; y2=y1;
}else{
point p; p.x=x1; p.y=y1;
pstack.push(p);
SetPixel(x1,y1,0x0000ff);
Fill();
}}
//---------------------------------------------------------------------------
void __fastcall TForm1::CSpinEdit1Change(TObject *Sender)
{
k=(Image1->Width < Image1->Height ? Image1->Width : Image1->Height)/CSpinEdit1->Value;
DrawGrid();}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{ CSpinEdit1->Enabled=true;
kp=0;
DrawGrid();}
//---------------------------------------------------------------------------
Виконання програми
Висновок: в даній лабораторній роботі я ознайомився з основами комп’ютерної графіки – простим алгоритмом заповнення з запалом.
.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора