Закраска гранично-заданной области с затравкой, Машинная графика, C++ Builder 4.0

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ОТЧЕТ

ПО КУРСУ

“Диалоговые системы и машинная графика”

ЗАДАНИЕ № 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 <vcl.h>

#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);

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 (tx<=0) break;

if (ty<=0) break;

if (tx>420) break;

if (ty>420) 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 (tx<=0) break;

if (ty<=0) break;

if (tx>420) break;

if (ty>420) break;

}

tx=tx+1;

if(Form1->PaintBox1->Canvas->Pixels[tx-1][ty]==bcolor) xl=tx;

}

Stack()

{

tx=xl;

ty=ty+j;

while(tx<=xr)

{

c=0;

while((Form1->PaintBox1->Canvas-

>Pixels[tx][ty]!=bcolor)&&

(Form1->PaintBox1->Canvas-

>Pixels[tx][ty]!=kraska)&&(tx<xr))

{tx++;c=1;}

if(c==1)

tx=tx+1;

while(((Form1->PaintBox1->Canvas-

>Pixels[tx][ty]==bcolor)||

(Form1->PaintBox1->Canvas-

>Pixels[tx][ty]==kraska))&&(tx<xr)&&(tx>xl))

{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