Алгоритм построчного заполнения многоугольника с использованием затравочного пикселя

 #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="<-- Нарисуйте гранично-заданную область -->";
      }

#include <stdio.h>
#include <graphics.h>
 
#define MAXARR 300  /* Ìàêñ êîë-âî âåðøèí ìíîãîóãîëüíèêà  */
#define MAXLST 300  /* Ìàêñ ðàçìåð ñïèñêà àêòèâíûõ ðåáåð  */
 
 
/*---------------------------------------------------- FILSTR
 * Çàëèâàåò ñòðîêó iy îò ixn äî ixk
 *
 * void FILSTR (int kod, int iy, int ixn, int ixk)
 */
void FILSTR (kod, iy, ixn, ixk)
int kod, iy, ixn, ixk;
{
   while (ixn <= ixk) putpixel (ixn++, iy, kod);
}  /* FILSTR */
 
 
 
/*--------------- Ãëîáàëû ïðîöåäóðû çàêðàñêè ---------------*/
 
static int   KOD, NWER; /* Êîä çàëèâêè è êîë-âî âåðøèí      */
static float *pt_X;     /* Ìàññèâû âõîäíûõ êîîðäèíàò âåðøèí */
static float *pt_Y;
 
static int   IBGIND;        /* Íîìåð ñëåä âåðøèíû â ñïèñêå */
static int   IEDG[MAXARR];  /* Y-êîîðä âåðøèí ïî âîçðàñòàí */
static int   INOM[MAXARR];  /* è èõ íîìåðà â èñõ ìàññ Py   */
 
/* Ñïèñîê àêòèâíûõ ðåáåð */
static int   IDLSPI;        /* Äëèíà ñïèñêà àêòèâíûõ ðåáåð */
static int   IYREB[MAXLST]; /* Ìàêñ Y-êîîðä àêòèâíûõ ðåáåð */
static float RXREB[MAXLST]; /* Òåê  X-êîîðä àêòèâíûõ ðåáåð */
static float RPRIR[MAXLST]; /* Õ-ïðèðàùåíèå íà 1 øàã ïî Y  */
static float RYSL[MAXLST];  /* Dy ìåæäó òåê è ñîñåäí âåðø  */
                            /* Dy <= 0.0 - îáû÷íàÿ âåðøèíà */
                            /*     > 0.0 - ëîêàë ýêñòðåìóì */
 
 
/*---------------------------------------------------- FORSPI
 * int  FORSPI (int IYBEG)
 *
 *  1) Ôîðìèðóåò ýëåìåíòû ñïèñêà äëÿ ðåáåð,
 *     íà÷èíàþùèõñÿ â IYBEG;
 *  2) Âû÷ècëÿeò IBGIND - èíäeêc ía÷aëa ñëåäóþùåé
 *     âepøèíû â cïècêe âepøèí;
 *  3) Âîçâðàùàåò IYSLED - Y êoopäèíaòy áëèæaéøeé
 *     âepøèíû, äo êoòopoé ìoæío çaëèâaòü áeç
 *     ïepecòpoéêè cïècêa.
 *
 *  Ãëoáaëüíûe âeëè÷èíû :
 *
 *  KOD    - êîä çàëèâêè
 *  NWER   - êoë-âo âepøèí â ècxoäíoì ìíoãoyãoëüíèêe,
 *  *pt_X  - X-êoopäèíaòû ècxoäíoão ìíoãoyãoëüíèêà,
 *  *pt_Y  - Y-êoopäèíaòû ècxoäíoão ìíoãoyãoëüíèêà,
 *  IEDG   - yïopÿäo÷eííûé ïo âoçpacòaíèþ ìaccèâ
 *           Y êoopäèíaò âepøèí ècxoäíoão ìíoãoyãoëüí
 *  INOM   - INOM[i] çaäaeò íoìep âepøèíû â ècxoäíoì
 *           ìíoãoyãoëüíèêe äëÿ IEDG[i],
 *  IBGIND - èíäeêc ìaccèâoâ IEDG, INOM
 *           oïpeäeëÿeò ãäe ìoæeò ía÷aòücÿ ðåápo,
 *  IDLSPI - äëèía ïocòpoeííoão cïècêa aêòèâíûx ðåáep,
 *           cocòoÿùeão èç :
 *           IYREB  - ìaêc êoopäèíaòû ðåáep,
 *           RXREB  - âía÷aëe ìèí, çaòeì òeêyùaÿ X-êoopäèíaòa,
 *           RPRIR  - ïpèpaùeíèe ê X-êoopäèíaòe ía 1 øaã ïo Y,
 *           RYSL   - ïpèçíaê òoão ÷òo ça âepøèía :
 *                    <= 0 - oáû÷íaÿ,
 *                     > 0 - ëoêaëüíûé ýêcòpeìyì
 *                     ïepece÷eíèe còpoêè çaêpacêè
 *                     c ýêcòpeìyìoì c÷èòaeòcÿ ça 2 òo÷êè,
 *                     c oáû÷íoé - ça 1;
 */
 
static int  FORSPI (IYBEG)
int  IYBEG;
{
 
   int   i,ikledg,intek,intabs,isd;
   int   iyt,ixt,nrebra,inc,inpred,inposl;
   float xt, xc, yt, yc, dy;
 
/* ikledg = êoë-âo âepøèí c äaííûì IYBEG */
 
   ikledg= 0;
   for (i=IBGIND; i<=NWER; ++i)
      if (IEDG[i] != IYBEG) break; else ++ikledg;
 
/* Öèêë ïocòpoeíèÿ cïècêa aêòèâíûx ðåáep
   è çaêpaøèâaíèe ãopèçîíòàëüíûõ ðåáep
 */
 
   for (i=1; i<=ikledg; ++i) {
/* Bû÷èñë íîìåðà òåêóùåé âåðøèíû */
      intek= INOM[IBGIND+i-1];
      intabs= abs (intek);
      xt= pt_X[intabs];
      yt= pt_Y[intabs];
 
/*  Bû÷èñë íîìåðîâ ïðåäûä è ïîñëåä âåðøèí */
      if ((inpred= intabs - 1) < 1) inpred= NWER;
      if ((inposl= intabs + 1) > NWER) inposl= 1;
 
/*
 * Ïî çàäàííûì :
 *    NWER   - êîë-âî âåðøèí,
 *    intek  - íîìåð òåêóùåé âåðøèíû,
 *    isd = 0/1 - ïðàâèëó âûáîðà ñîñåäíåé âåðøèíû -
 *                ïðåäûäóùàÿ/ïîñëåäóþùàÿ
 *    âû÷ècëÿeò dy,
 *    Åcëè dy <  0 òo âepøèía yæe oápaáoòaía,
 *    Åcëè dy == 0 òo âepøèíû ía oäíîì Y
 *                 Ïpè ýòoì còpoèòcÿ ãopèçoíòaëüíûé oòpeçoê.
 *                 Ôaêò çaêpacêè ãopèçoíòaëüíoão ðåápa
 *                 oòìe÷aeòcÿ oòpèöaòeëüíûì çía÷eíèeì
 *                 cooòâeòcòâyþùeão çía÷eíèÿ INOM.
 *    Åcëè dy >  0 òo ôopìèpyeòcÿ íoâûé ýëeìåíò cïècêa
 *                 aêòèâíûx ðåáep
 */
 
      for (isd=0;  isd<=1; ++isd) {
         if (!isd) nrebra= inc= inpred; else {
            inc= inposl;  nrebra= intabs;
         }
         yc= pt_Y[inc];
         dy= yc - yt;
         if (dy < 0.0) continue;
         xc= pt_X[inc];
         if (dy != 0.0) goto DYNE0;
            if ((inc= INOM[nrebra]) < 0) continue;
            INOM[nrebra]= -inc;
            iyt= yt;
            inc= xc;
            ixt= xt;
            FILSTR (KOD, iyt, inc, ixt);
            continue;
DYNE0:   ++IDLSPI;
         IYREB[IDLSPI]= yc;
         RXREB[IDLSPI]= xt;
         RPRIR[IDLSPI]= (xc - xt) / dy;
         inc= (!isd) ? inposl : inpred;
         RYSL[IDLSPI]=  pt_Y[inc] - yt;
      }   /* öèêëà ïî isd */
   }  /* ïîñòðîåíèÿ ñïèñêà àêòèâíûõ ðåáåð */
 
/*  Bû÷èñëåíèå Y áëèæàéøåé âåðøèíû */
   if ((i= (IBGIND += ikledg)) > NWER) i= NWER;
   return (IEDG[i]);
} /* Ïðîöåäóðû FORSPI */
 
 
 
/*-----------------------------------------------------  V_FP1
 * Îäíîòîííî çàëèâàåò ìíîãîóãîëüíèê,
 * çàäàííûé êîîðäèíàòàìè âåðøèí
 *
 * void V_FP1 (int pixel, int kol, float *Px, float *Py)
 *
 */
void V_FP1 (pixel, kol, Px, Py)
int  pixel, kol;  float *Px, *Py;
{
int  i,j,k,l;
int  iytek;    /* Y òåêóùåé ñòðîêè ñêàíèðîâàíèÿ        */
int  iymin;    /* Y-ìèí ïðè ñîðòèðîâêå ìàññèâà Y-êîîðä */
int  iybeg;    /* Ìèí Y-êîîðäèíàòà çàëèâêè  */
int  iymak;    /* Max Y-êîîðäèíàòà çàëèâêè  */
int  iysled;   /* Y êoopä áëèæaéøeé âepøèíû, äo êoòopoé */
               /* ìîæíî çaëèâaòü áeç ïepecòpoéêè cïècêa */
int  newysl;
int  ixmin;    /* X-ìèí ïðè ñîðòèðîâêå äëÿ òåê ñòðîêè */
int  ixtek;    /* X-òåê ïðè ñîðòèðîâêå äëÿ òåê ñòðîêè */
int  irabx[MAXLST]; /* X-êîîðä ïåðåñå÷åíèé â ñòðîêå ñêàíèð */
 
   KOD= pixel;    /* Ïàðàìåòðû â ãëîáàëû */
   NWER= kol;
   pt_X= Px;
   pt_Y= Py;
 
/*  Ïîñòðîåíèå ìàññèâîâ Y è èõ íîìåðîâ */
   for (i= 1; i<=NWER; ++i) {IEDG[i]= Py[i];  INOM[i]= i; }
 
/*  Cîâìåñòíàÿ ñîðòèðîâêà ìàññèâîâ IEDG, IHOM */
   for (i= 1; i<=NWER; ++i) {
      iymin= IEDG[i];
      k= 0;
      for (j=i+1; j<=NWER; ++j)
         if ((l= IEDG[j]) < iymin) {iymin= l; k= j; }
      if (k) {
         IEDG[k]= IEDG[i]; IEDG[i]= iymin;
         iymin= INOM[k];
         INOM[k]= INOM[i]; INOM[i]= iymin;
      }
   }
 
/* Hà÷àëüíûå ïðèñâîåíèÿ */
   IDLSPI= 0;
   IBGIND= 1;
   iybeg= IEDG[1];
   iymak= IEDG[NWER];
 
/* Ôîðìèðîâàíèå íà÷àëüíîãî ñïèñêà àêò ðåáåð */
 
   iysled= FORSPI (iybeg);
   if (!IDLSPI) goto KOHGFA;
 
/* Ãîðèçîíòàëüíàÿ ðàñêðàñêà ïî ñïèñêó */
 
ZALIWKA:
 
   for (iytek=iybeg; iytek<=iysled; ++iytek) {
      if (iytek == iysled) {    /* Y-êîîðäèíàòà ïåðåñòðîéêè */
         newysl= FORSPI (iytek);
         if (!IDLSPI) goto KOHGFA;
      }
 
/* Bûáîðêà è ñîðòèðîâêà X-îâ èç ñïèñêà ðåáåð */
      l= 0;
      for (i=1; i<=IDLSPI; ++i)
         if (RYSL[i] > 0.0) irabx[++l]= RXREB[i];
         else RYSL[i]= 1.0;
 
      for (i=1;  i<=l; ++i) {
         ixmin= irabx[i];
         k= 0;
         for (j=i+1;  j<=l; ++j) {
            ixtek= irabx[j];
            if (ixtek < ixmin) {k= j; ixmin= ixtek; }
         }
         if (k) {irabx[k]= irabx[i];  irabx[i]= ixmin; }
      }  /* öèêëà ñîðòèðîâêè */
 
/*  Cîáñòâåííî çàëèâêà */
 
      for (j=1;  j<=l-1;  j+= 2)
         FILSTR (KOD,iytek,irabx[j],irabx[j+1]);
 
      for (j=1;  j<=IDLSPI; ++j)        /*  Ïðèðàùåíèÿ X-îâ */
         RXREB[j]= RXREB[j] + RPRIR[j];
   }  /* öèêëà ãîðèçîíòàëüíîé ðàñêðàñêè */
 
   if (iysled == iymak) goto KOHGFA;
 
/*  Bûáðàñûâàíèå èç ñïèñêà âñåõ ðåáåð ñ YMAK ðåáðà == YSLED */
 
   i= 0;
M1:++i;
M2:if (i > IDLSPI) goto WYBROSILI;
      if (IYREB[i] != iysled) goto M1;
         --IDLSPI;
         for (j=i;  j<=IDLSPI; ++j) {
            IYREB[j]= IYREB[k= j+1];
            RXREB[j]= RXREB[k];
            RPRIR[j]= RPRIR[k];
         }
         goto M2;
WYBROSILI:
   iybeg= iysled + 1;
   iysled= newysl;
   goto ZALIWKA;
 
KOHGFA:;
}  /* V_FP1 */

fncFill(int x,int y,char * pole,char colorFill, char colorMask)
{
   pole[x][y]=colorFill;
  if(pole[x+1][y]==colorMask)
     fncFill(x+1,y,pole,colorFill,colorMask);
 
   if(pole[x][y+1]==colorMask)
     fncFill(x,y+1,pole,colorFill,colorMask);
 
if(pole[x-1][y]==colorMask)
     fncFill(x-1,y,pole,colorFill,colorMask);
 
   if(pole[x][y-1]==colorMask)
     fncFill(x,y-1,pole,colorFill,colorMask);
 
}

enum cell { empty, visited, unvisited };
 
typedef std::vector< cell > T_row;
typedef std::vector< T_row > T_matr;

void paint_ridge(T_matr &matrix, int y, int x )
{
    const int n = matrix.size();
    const int m = matrix[0].size();
    
    std::stack< std::pair< int, int > > stack;
    
    stack.push( std::make_pair( y, x ) );
    
    while ( !stack.empty() )
    {
        std::pair< int, int > temp = stack.top();
        stack.pop();
        
        int i = temp.first;
        int j = temp.second;
        
        if ( matrix[i][j] != unvisited )
            continue;
            
        matrix[i][j] = visited;
        
        #define check(a, b) \
        if ( (a) >= 0 && (a) < n && (b) >= 0 && (b) < m && matrix[a][b] == unvisited ) \
        { \
            stack.push( std::make_pair(a, b) ); \
        } 
        
        check(i - 1, j)
        check(i + 1, j)
        check(i, j - 1)
        check(i, j + 1)
    }
    
}