На этом шаге мы рассмотрим указанный алгоритм.

    Данный алгоритм получил широкое распространение в компьютерной графике. От приведенного ранее простейшего рекурсивного алгоритма он отличается тем, что на каждом шаге закрашивания рисуется горизонтальная линия, которая размещается между пикселями контура. Алгоритм рекурсивный, но поскольку вызов функции осуществляется для линии, а не для каждого отдельного пикселя, то количество вложенных вызовов уменьшается пропорционально длине линии. Это уменьшает нагрузку на стековую память компьютера. Приведем запись алгоритма на языке C++. Этот алгоритм взят из [1] и незначительно переработан.

int LineFill (HDC hdc,int x,int y,int dir,int preXL,int preXR)
{
 int xl=x,xr=x;
 COLORREF clr,BORDER=RGB(0,0,0);
 do {
   clr=GetPixel(hdc,--xl,y);
    }
 while(clr!=BORDER); //BORDER - цвет контура

 do {
  clr=GetPixel(hdc,++xr,y); }
  while(clr!=BORDER);
  xl++; xr--;  // Левая и правая границы текущей горизонтали
  MoveToEx(hdc,xl,y,NULL);
  LineTo(hdc,xr+1,y);
  for(x=xl;x<=xr;x++)
  {
    clr=GetPixel(hdc,x,y+dir);
    if (clr!=BORDER)
    {
      x=LineFill(hdc,x,y+dir,dir,xl,xr);
    }
  }
  for(x=xl;x<preXL;x++)
  {
    clr=GetPixel(hdc,x,y-dir);
    if (clr!=BORDER)
      x=LineFill(hdc,x,y-dir,-dir,xl,xr);
  }
  for(x=preXR;x<xr;x++)
  {
    clr=GetPixel(hdc,x,y-dir);
    if (clr!=BORDER)
      x=LineFill(hdc,x,y-dir,-dir,xl,xr);
  }
  return xr;
}

    В программе функция LineFill используется таким образом:

  LineFill (xst, yst, 1, xst, xst);

    Пример работы алгоритма закрашивания линиями приведен на рисунке 1.

Рис.1. Пример работы приложения

    Так же, но немного быстрее, работает функция FloodFill API Windows. Разница в быстродействии обусловлена тем, что для LineFill мы использовали стандартные функции для интерфейса прикладных программ, a FloodFill оптимизирована на системном уровне.

    Со следующего шага мы начнем рассматривать алгоритмы заполнения, которые используют математическое описание контура.

Предыдущий шаг Содержание Следующий шаг