САНКТ-Петербурзького державного технічного університету
ЗВІТ
ПО КУРСУ
"Діалогові системи та машинна графіка"
ЗАВДАННЯ № 4
Викладач: Курочкін М.А.
Студент: Дмітроченко А.А.
Група 4086
2001р.
1. Постановка завдання:
Необхідно реалізувати алгоритм заливки гранично-заданої області з затравкою.
2. Модель
Здається заливається (перефарбовуються) область, код піксела, яким буде виконуватися заливка і початкова точка в області, починаючи з якої почнеться заливка.
За способом завдання області поділяються на два типи:
- гранично-певні, що задаються своєї (замкнутої) кордоном такий, що коди пікселів кордону відмінні від кодів внутрішньої, перефарбовуй частині області. На коди пікселі внутрішньої частини області накладаються дві умови - вони повинні бути відмінні від коду пікселів кордону та коду пікселя перефарбовування. Якщо всередині гранично-певній галузі є ще одна межа, намальована пікселями з тим самим кодом, що й зовнішній кордон, то відповідна частина області не повинна перефарбовуватися;
- внутрішньо певні, намальовані одним певним кодом пікселя. При заливанні цей код замінюється на новий код зафарбовування.
У цьому полягає основна відмінність заливки області з затравкою, від заповнення багатокутника. В останньому випадку ми маємо всю інформацію про граничні розміри частини екрану, зайнятої багатокутників. Тому визначення приналежності пікселя багатокутника базується на швидко працюють алгоритми, що використовують когерентність рядків і ребер. В алгоритмах ж заливки області з затравкою нам спочатку треба прочитати піксель, потім визначити чи належить він краю і якщо належить, то перефарбувати.
заливається область або її межа - деякий зв'язне безліч пікселів. За способами доступу до сусідніх пікселям області поділяються на 4 - х та 8-ми зв'язківці. В 4-х зв'язкових областях доступ до сусідніх пікселям здійснюється по чотирьох напрямах - горизонтально ліворуч і праворуч і в вертикально вгору і вниз. У 8-ми зв'язкових областях до цих напрямках додаються ще 4 діагональних. Використовуючи зв'язаність, ми можемо, рухаючись від точки затравки досягти і зафарбувати всі пікселі області.
Важливо відзначити, що для 4-х зв'язковий прямокутної області кордон 8-ми складно і, навпаки, у 8-ми зв'язковий області кордон 4-х зв'язкових.
Тому заповнення 4-х зв'язковий області 8-ми зв'язковим алгоритмом може призвести до "просочування" через кордон і заливанні пікселів в примикає області.
порядковий алгоритм заливки з затравкою:
Використовує просторову когерентність:
- пікселі в рядку змінюються тільки на кордонах;
- при переміщенні до наступному рядку розмір заливається рядка швидше за все або незмінний або змінюється на 1 піксель.
Таким чином, на кожен закрашується фрагмент рядка в стеку зберігаються координати тільки одного початкового пікселя, що призводить до суттєвого зменшення розміру стека.
Послідовність роботи алгоритму для гранично -певної областінаступна:
1. Координата затравки поміщається в стек, потім до вичерпання стека виконуються пункти 2-4.
2. Координата черговий затравки витягується з стека і виконується максимально можливе зафарбовування вправо і вліво по рядку з затравкою, тобто поки не попадеться граничний піксель. Нехай це хліви і Хправ, відповідно.
3. Аналізується рядок нижче закрашується в межах від хліви до Хправ і в ній знаходяться крайні праві пікселі всіх, не зафарбованих фрагментів. Їх координати заносяться в стек.
4. Те ж саме проробляється для рядки вище зафарбовувати.
3. Реалізація
Даний алгоритм був реалізований у Borland C + + Builder 4.
При запуску програми користувачеві пропонується задати гранично-задану область. Алгоритм правильно заповнює будь-якої області, включаючи достатньо складні області, в яких присутні отвори. Далі необхідно вказати початкову точку заливки.
У результаті роботи буде отримана зафарбовані область.
4. Лістинг
//---------------------------------------- -----------------------------
------
# include
# pragma hdrstop
# include "windows.h"
# include "Unit1.h"
// -- -------------------------------------------------- -----------------
------
# pragma package (smart_init)
# pragma resource "*. dfm"
TForm1 * Form1; int x0 = 0, y0 = 0, start = 0, xtmp, ytmp, xmet =- 4, ymet =- 2, metka = 0;// змінні для побудови графіка
int tx, ty, xm, xr, xl, j, c, meta;// Змінні самого алгоритму
TColor kraska = clRed, bcolor = clBlue , nomy, my; struct pointt (unsigned int x; unsigned int y;
);
static pointt pont [500] [500];// Матриця реалізацій int raz;
cel ()
(
Form1-> PaintBox1-> Canvas-> Pen-> Color = bcolor;
Form1-> PaintBox1-> Canvas-> Brush-> Color = RGB (255,255,255);
Form1-> PaintBox1-> Canvas-> Rectangle (10,10,210,110);
)
//-------------------------------------------- -------------------------
------
__fastcall TForm1:: TForm1 (TComponent * Owner)
: TForm (Owner)
(kraska = RGB (255,0,0); bcolor = RGB (0,0,255); < p> cel ();
Edit1-> Text ="";
)
//------------ -------------------------------------------------- -------
------
Zakras ()
(xm = tx; while (Form1-> PaintBox1-> Canvas-> Pixels [tx] [ty]! = bcolor)
(
Form1-> PaintBox1-> Canvas-> Pixels [tx] [ty] = kraska; tx = tx 1; if (tx420) break;
)
if (Form1-> PaintBox1-> Canvas-> Pixels [tx] [ty] == bcolor) xr = tx -1;
tx = xm; while (Form1-> PaintBox1-> Canvas-
> Pixels [tx] [ty]! = bcolor)
(
Form1-> PaintBox1-> Canvas-> Pixels [tx] [ty] = kraska; tx = tx-1; if (tx420) break;
)
tx = tx 1; if (Form1-> PaintBox1-> Canvas-> Pixels [tx-1] [ty] == bcolor) xl = tx;
)
Stack ()
(
tx = xl; ty = ty + j; while (txPaintBox1-> Canvas-
> Pixels [tx] [ty]! = bcolor )&&
(Form1-> PaintBox1-> Canvas-
> Pixels [tx] [ty]! = kraska) & & (txPaintBox1-> Canvas -
> Pixels [tx] [ty] == bcolor )||
(Form1-> PaintBox1-> Canvas-
> Pixels [tx] [ ty] == kraska)) tx -; pont [raz] -> x = tx; pont [raz] -> y = ty;
) tx = tx 1; while (((Form1 -> PaintBox1-> Canvas-
> Pixels [tx] [ty] == bcolor )||
(Form1-> PaintBox1-> Canvas-
> Pixels [tx] [ty] == kraska ))&&( txxl))
(tx = tx 1;)
)
)
Zaliv ()
(raz = 1; pont [raz] -> x = x0; pont [raz] -> y = y0; while (raz> 0)
(tx = pont [raz] -> x; ty = pont [raz] -> y; raz = raz-1;
Form1-> PaintBox1-> Canvas-> Pixels [ tx] [ty] = kraska;
Zakras (); j = 1;
Stack (); j =- 2;
Stack ();
)
Form1-> Edit1-> Text = "Все закінчилося";
)
void __fastcall TForm1:: drawing ( TObject * Sender, TMouseButton Button,
TShiftState Shift, int X, int Y)
(if (start == 5) (x0 = X; y0 = Y; Canvas-> Pixels [X] [Y] = kraska;
Zaliv ();
)
if ((Button == mbLeft) & & (start! = 5 ))
(
Canvas-> Pen-> Color = bcolor;// вибрати колір контуру
// Brush-> Color = clYellow;// вибрати колір заливки if (metka == 1) Canvas-> LineTo (X, Y); metka = 1;
// намалювати еліпс xtmp = X; ytmp = Y;
Canvas-> MoveTo (X, Y); if (start == 0) (x0 = X, y0 = Y; start = 1;)
// randomize ();
// Canvas-> Brush-> Color = (Graphics:: TColor) $ (00FF0000);
)
if (Button == mbRight)
(
Canvas-> Pen-> Color = bcolor;
Canvas-> LineTo (x0, y0); metka = 0; start = 0;
)
)
//------------------------------- --------------------------------------
----- -
//---------------------------------------- -----------------------------
------ void __fastcall TForm1:: movexy (TObject * Sender, TShiftState Shift, int
X, int Y)
(
Label2-> Caption = X;
Label4 - > Caption = Y;
// xtmp = X; ytmp = Y;
// Label6-> Caption = Canvas-> Pixels [x0] [y0];
// Zaliv ();
)
//----------------------- ----------------------------------------------
------ void __fastcall TForm1:: vpered (TObject * Sender, TMouseButton Button,
TShiftState Shift, int X, int Y)
(
Edit1-> Text = "Виберіть точку зафарбовування"; start = 5;
)
//-------------- -------------------------------------------------- -----
------
void __fastcall TForm1:: reset_key (TObject * Sender, TMouseButton
Button,
TShiftState Shift, int X, int Y)
(start = 0;
PaintBox1-> Visible = false;
PaintBox1-> Visible = true;
start = 0;
Edit1-> Text ="";
)
//----- -------------------------------------------------- --------------
------
5. Висновок
У процесі роботи розібрався з методами зафарбовування гранично-заданій області,а також відпрацьовані прийоми програмування на С + +. Сталося більшедетальне знайомство з Borland C + + Builder 4.
Використані джерела інформації:
- Математичні основи машинної графіки (Д. Роджерс, Дж. Адамс)
«видавництво СВІТ »
- Алгоритмічні основи машинної графіки (Д. Роджерс)« МИР »
- Internet
