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

ОТЧЕТ

ПО КУРСУ

“Диалоговые системы и машинная графика”
ЗАДАНИЕ № 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