|
Закраска гранично-заданной области с затравкой, Машинная графика, C++ Builder 4.0Закраска гранично-заданной области с затравкой, Машинная графика, 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 #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 (tx420) 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 (tx420) 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(txPaintBox1->Canvas- >Pixels[tx][ty]!=bcolor)&& (Form1->PaintBox1->Canvas- >Pixels[tx][ty]!=kraska)&&(txPixels[tx][ty]==kraska)) tx--; 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 |
|
