Закраска гранично-заданной области с затравкой, Машинная графика, 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 (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)&&(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