САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
“Диалоговые системы и машинная графика”
ЗАДАНИЕ № 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){
raz=raz+1;
while((Form1->PaintBox1->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))&&(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
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |