Wypełnianie obszarów

Powrót do spisu treści

Wymagane jest zapoznanie się z następującymi podrozdziałami:

P019 - Pierwszy program dla Windows
OL031 - Instalacja biblioteki SDL w środowisku Dev-C++
OL032 - Inicjalizacja biblioteki SDL
OL033 - Powierzchnie graficzne w SDL
OL034 - Przygotowanie plików własnej biblioteki graficznej
OL035 - Rysowanie po powierzchni graficznej
OL036 - algorytm Bresenhama rysowania odcinka
OL037 - obcinanie grafiki do prostokąta

UWAGA!!!

Bieżące opracowanie NIE JEST KURSEM programowania biblioteki SDL. Są to materiały przeznaczone do zajęć na kole informatycznym w I LO w Tarnowie.

Przed pracą z tym rozdziałem utwórz w środowisku Dev-C++ nowy projekt SDL i dołącz do niego pliki SDL_gfx.cpp oraz SDL_gfx.h. Jeśli nie przeczytałeś zalecanych rozdziałów, koniecznie zrób to, a wszystko stanie się jasne. W przeciwnym razie odpuść sobie również ten rozdział. Opis funkcji bibliotecznych znajdziesz w podsumowaniu SDL004.

 

Artykuł w PRZEBUDOWIE


SDL

Grafika komputerowa nie składa się tylko z linii. Bardzo często musimy wypełniać różne obszary określonym kolorem. Istnieje wiele algorytmów wypełniania (ang. fill) na powierzchni rastrowej (tj. powierzchni graficznej zbudowanej z pikseli). Tutaj przeanalizujemy kilka z nich. Algorytmy wypełniania odczytują zawartość pikseli na powierzchni graficznej, aby określić, czy dany piksel należy ustawić na zadany kolor, czy też jest on granicą wypełnianego obszaru. Dlatego musimy posiadać funkcję zwracającą kod piksela na zadanych współrzędnych x ,y. Struktura funkcji gfxGetPixel() jest praktycznie identyczna do funkcji gfxPlot(). Różnica polega jedynie na tym, iż gfxGetPixel() nie zapala piksela, lecz odczytuje jego kod koloru z wyliczonego adresu w buforze ekranu.

UWAGA: Poniższy kod funkcji gfxGetPixel() dopisz do końca pliku SDL_gfx.cpp.

// gfxGetPixel() odczytuje 32 bitowy kod piksela
// screen - wskaźnik struktury SDL_Surface
// x,y    - współrzędne piksela
//------------------------------------------------------------------

Uint32 gfxGetPixel(SDL_Surface * screen, Sint32 x, Sint32 y)
{
  return * ((Uint32 *)screen->pixels + y * screen->w + x);
}

UWAGA: Na końcu pliku nagłówkowego SDL_gfx.h dopisz:


Uint32 gfxGetPixel(SDL_Surface * screen, Sint32 x, Sint32 y);

Poniższy program testowy dzieli ekran na cztery równe ćwiartki. W pierwszej ćwiartce rysuje 25 linii na losowych współrzędnych. Następnie odczytuje kolejne piksele z tej ćwiartki i umieszcza je w odpowiedni sposób w pozostałych ćwiartkach, co w wyniku daje efekt kalejdoskopu.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P015 - odczyt pikseli
//----------------------

#include <windows.h>
#include <SDL/SDL_gfx.h>
#include <time.h>     // do inicjalizacji generatora pseudolosowego

const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach

int main(int argc, char *argv[])
{

  if(SDL_Init(SDL_INIT_VIDEO))
  {
    MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK);
    exit(-1);
  }

  atexit(SDL_Quit);
  
  SDL_Surface * screen;

  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE)))
  {
    MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK);
    exit(-1);
  }

  if(SDL_MUSTLOCK(screen))
    if(SDL_LockSurface(screen) < 0)
    {
      MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK);
      exit(-1);
    }

// inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// obliczamy współrzędne środka ekranu

  Sint32 x = screen->w >> 1;
  Sint32 y = screen->h >> 1;

// W pierwszej ćwiartce ekranu rysujemy 25 przypadkowych linii

  for(int i = 0; i < 25; i++)
  {
    Sint32 x1 = rand() % x;
    Sint32 y1 = rand() % y;
    Sint32 x2 = rand() % x;
    Sint32 y2 = rand() % y;
    Uint32 color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256);
    gfxLine(screen, x1, y1, x2, y2, color);
  } 

// Odczytujemy kolejne piksele z pierwszej ćwiartki i zapisujemy je w pozostałych
// ćwiardkach odpowiednio odbijając w pionie i poziomie

  for(int i = 0; i < x; i++)
    for(int j = 0; j < y; j++)
    {
      Uint32 color = gfxGetPixel(screen, i, j);                     // odczytujemy piksel z 1 ćwiartki ekranu
      gfxPlot(screen, screen->w - i - 1, j, color);                 // kopiujemy do 2 ćwiartki
      gfxPlot(screen, screen->w - i - 1, screen->h - j - 1, color); // kopiujemy do 3 ćwiartki
      gfxPlot(screen, i, screen->h - j - 1, color);                 // kopiujemy do 4 ćwiartki
    }

  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Wypełnianie obszarów prostokątnych

W bibliotece SDL istnieje już funkcja wypełniająca zadany obszar prostokątny pikselami w wybranym kolorze. Opisaliśmy ją w rozdziale OL035.

int SDL_FillRect(SDL_Surface * dst, SDL_Rect * dstrect, Uint32 color);

Powtórzmy. Parametry wywołania SDL_FillRect() są następujące:

dst  -   wskazuje strukturę SDL_Surface z powierzchnią graficzną, po której chcemy rysować. Jeśli na powierzchni jest zdefiniowany prostokąt obcinania, to prostokąt wypełniający pojawi się tylko wewnątrz prostokąta obcinania, w obszarze wspólnym. Powierzchnia graficzna może być dowolnego typu, niekoniecznie 32-bitowa.
dstrect  - wskazuje strukturę SDL_Rect definiującą prostokątny obszar do wypełnienia kolorem na powierzchni graficznej dst. Jeśli wskaźnik ma wartość NULL, to wypełniona zostanie cała powierzchnia graficzna (patrz wyżej - prostokąt obcinania).
color  - 32 bitowy kolor punktu. Kod piksela musi być kompatybilny z formatem graficznym powierzchni. Dla dowolnej powierzchni można go uzyskać przy pomocy wywołania funkcji biblioteki SDL:
Uint32 SDL_MapRGB(SDL_PixelFormat *fmt, Uint8 r, Uint8 g, Uint8 b); 
fmt  -  wskazuje strukturę SDL_PixelFormat definiującą format pikseli. Można tutaj podać zawartość pola format struktury SDL_Surface, po której chcemy rysować.
r,g,b  - składowe kolorów bazowych: r - czerwony, g - zielony i b - niebieski

Jak widzimy, funkcja SDL_FillRect() automatycznie reaguje na prostokąt obcinający, umieszczony w polu clip_rect struktury SDL_Surface, której wskaźnik jest pierwszym argumentem funkcji. Poniższy program testuje tę funkcję razem z funkcją gfxClipRectangle(), która rysuje prostokątne ramki. Definiuje on na ekranie prostokąt obcinający, a następnie rysuje 100 wypełnionych ramek, obciętych do prostokąta.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P016 - wypełnianie prostokątów
//-------------------------------

#include <windows.h>
#include <SDL/SDL_gfx.h>
#include <time.h>     // do inicjalizacji generatora pseudolosowego

const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach

int main(int argc, char *argv[])
{

  if(SDL_Init(SDL_INIT_VIDEO))
  {
    MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK);
    exit(-1);
  }

  atexit(SDL_Quit);
  
  SDL_Surface * screen;

  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE)))
  {
    MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK);
    exit(-1);
  }

  if(SDL_MUSTLOCK(screen))
    if(SDL_LockSurface(screen) < 0)
    {
      MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK);
      exit(-1);
    }

// inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// tworzymy prostokąt obcinania oraz prostokąt wypełniania

  SDL_Rect * clip = new SDL_Rect;
  SDL_Rect * fill = new SDL_Rect;

// ustawiamy prostokąt obcinania

  clip->x = screen->w >> 3;      // 1/8 szerokości ekranu
  clip->y = screen->h >> 3;      // 1/8 wysokości ekranu
  clip->w = screen->w - (screen->w >> 2);
  clip->h = screen->h - (screen->h >> 2);

// Rysujemy żółtą ramkę na krawędzi prostokąta

  gfxRectangle(screen, clip, 0xffff00);

// pomniejszamy prostokąt obcinający

  clip->x++;
  clip->y++;
  clip->w -= 2;
  clip->h -= 2;

// ustawiamy na ekranie obcinanie do prostokąta clip

  SDL_SetClipRect(screen, clip);

// w prostokącie clip rysujemy 100 ramek wypełnionych różnymi kolorami

  for(int i = 0; i < 100; i++)
  {
    fill->x = rand() % ((screen->w >> 1) + (screen->w >> 2));
    fill->y = rand() % ((screen->h >> 1) + (screen->h >> 2));
    fill->w = 10 + rand() % (screen->w >> 2);
    fill->h = 10 + rand() % (screen->h >> 2);
    SDL_FillRect(screen, fill, ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256));
    gfxClipRectangle(screen, fill, ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256));
  }

  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Wypełnianie obszarów ograniczonych

W ogólnym przypadku obszar do wypełnienia jest ograniczony linią oraz prostokątem obcinającym i posiada nieregularny kształt. Zadaniem algorytmu wypełniającego jest znalezienie wszystkich pikseli leżących wewnątrz tego obszaru i pokolorowanie ich na zadany kolor.

 

          

Na początek podamy kilka ważnych definicji.

Obszar jest cztero-spójny (ang. four-way connected region), jeśli zawarte w nim piksele posiadają ten sam kolor oraz do każdego z nich można dotrzeć poruszając się po pikselach tego obszaru tylko w 4 kierunkach - góra, dół, prawo, lewo. Poniższy rysunek przedstawia obszar cztero-spójny (zielone piksele) oraz drogi dojścia (żółta linia) do każdego z nich. Zwróć uwagę na podobieństwo do grafów, jeśli piksele potraktujemy jako węzły, a drogi dojścia jako krawędzie!

Obszar jest ośmio-spójny (ang. eigth-way connected region), jeśli dodatkowo zezwolimy na drogi przekątne. Wtedy do pikseli obszaru możemy przechodzić na 8 sposobów.

Linia ograniczająca obszar może być cztero- lub ośmio-spójna (podany przez nas algorytm Bresenhama tworzy linie ośmiospójne).

          

Zwróć uwagę, iż obszar ośmio-spójny musi być otoczony linią cztero-spójną (w przeciwnym razie "wycieknie" w kierunkach ukośnych), natomiast obszar cztero-spójny można otoczyć linią ośmio-spójną (rysunek po prawej stronie). Zrozumienie tego prostego faktu ma bardzo istotne znaczenie przy doborze odpowiednich algorytmów wypełniających.

Istnieją dwa rodzaje sposobów wypełniania ograniczonych obszarów:

Wypełnianie konturowe (ang boundary-fill) - wszystkie piksele zawarte wewnątrz konturu (zamkniętej linii zbudowanej z pikseli o tym samym kolorze) zostają pokolorowane na ten sam kolor wypełnienia. Zawartość objętego konturem obszaru nie jest istotna (patrz poniżej). Nie może on jedynie zawierać pikseli o kolorze wypełnienia.

          

Wypełnianie powodziowe (ang. floodfill) - wszystkie piksele spójne (tzn. przyległe w 4 lub 8 kierunkach) do piksela startowego i posiadające ten sam co on kolor zostaną pokolorowane na nowy kolor wypełnienia. Wynika z tego, iż wypełniany obszar musi posiadać przed operacją jednolity kolor. Natomiast obszary przyległe mogą posiadać kolory dowolne, ale różne od koloru wypełnianego obszaru.

          

Piksel, od którego rozpoczynamy wypełnianie obszaru nazywamy ziarnem wypełnienia (ang. fill seed). Musi on znajdować się wewnątrz wypełnianego obszaru. Pozostałe piksele znajdujemy wykorzystując cztero- lub ośmio-spójność. Opisane poniżej algorytmy należą do grupy algorytmów wypełniania przez sianie (ang. seed fill algorithm) . Wewnątrz wypełnianego obszaru umieszczamy ziarno wypełnienia, a następnie próbujemy je propagować (siać) w czterech lub ośmiu kierunkach w zależności od rodzaju spójności wypełnianego obszaru. Jeśli ziarno trafi na podatny grunt, to wypełnia go kolorem i próbuje dalej się propagować w czterech lub ośmiu kierunkach. W ten sposób cały obszar zostanie zamalowany określonym kolorem. W zależności od warunków akceptacji ziarna otrzymamy algorytm wypełnienia konturowego - ziarno sieje się tylko na pikselu o kolorze różnym od koloru konturu, lub algorytm wypełnienia powodziowego - ziarno sieje się tylko na pikselu o kolorze pierwszego ziarna. Poniżej prezentujemy oba algorytmy wypełniające wraz z odpowiednimi programami testowymi.

Algorytm cztero-spójnego wypełniania konturowego

Wejście

x, y  -   współrzędne ziarna wypełnienia. Ziarno musi się zawierać w prostokącie obcinającym clip.
ccolor  - kolor konturu obejmującego obszar wypełniany
fcolor  - kolor wypełnienia
clip  - prostokąt obcinający

Wyjście

Wypełnienie kolorem fcolor obszaru ograniczonego konturem w kolorze ccolor i obejmującego punkt x,y. Jeśli obszar rozpościera się poza prostokąt obcinający, to wypełnienie ograniczy się tylko do prostokąta obcinania.

Zmienne pomocnicze

q  -   stos przechowujący współrzędne punktów.
cx1,cy1  - współrzędne lewego górnego narożnika prostokąta obcinania
cx2,cy2  - współrzędne prawego dolnego narożnika prostokąta obcinania
pcolor  - kolor piksela

Lista kroków

K01: cx1 ← clip.x ; obliczamy współrzędne wierzchołków prostokąta obcinającego
K02: cy1 ← clip.y  
K03: cx2 ← cx1 + clip.w - 1  
K04: cy2 ← cy1 + clip.h - 1  
K05: Wyzeruj stos q  
K06: Umieść na szczycie stosu x i y  
K07: Dopóki stos q nie jest pusty, wykonuj kroki K08...K20  
K08:     Pobierz ze stosu x i y ; pobieramy współrzędne ziarna wypełniania
K09:     Jeżeli x < cx1, wykonaj kolejny obieg pętli K07 ; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania
K10:     Jeżeli x > cx2, wykonaj kolejny obieg pętli K07 ; jeśli nie, punktu x,y nie przetwarzamy dalej w pętli
K11:     Jeżeli y < cy1, wykonaj kolejny obieg pętli K07  
K12:     Jeżeli y > cy2, wykonaj kolejny obieg pętli K07  
K13:     pcolor = kolor piksela x,y  
K14:     Jeżeli pcolor = ccolor, wykonaj kolejny obieg pętli K07 ; natrafiliśmy na kontur, nie przetwarzamy
K15:     Jeżeli pcolor = fcolor, wykonaj kolejny obieg pętli K07 ; natrafiliśmy na punkt już wypełniony, nie przetwarzamy
K16:     Ustaw kolor piksela x,y na fcolor ; piksel kolorujemy na kolor wypełnienia
K17:     Umieść na stosie x i y - 1 ; na stos przesyłamy współrzędne czterech sąsiednich pikseli
K18:     Umieść na stosie x + 1 i y  
K19:     Umieść na stosie x i y + 1  
K20:     Umieść na stosie x - 1 i y  
K21: Zakończ  

Algorytm ośmio-spójnego wypełniania konturowego jest praktycznie identyczny. Różnica polega jedynie na tym, iż na stosie dodatkowo umieszczamy w pętli współrzędne pikseli leżących na kierunkach przekątnych.

Na podstawie powyższego algorytmu napiszemy prosty program testowy, który rysuje kilka ramek oraz okręgów na powierzchni graficznej, a następnie rozpoczyna wypełnianie obszaru począwszy od środka ekranu. Wypełnianie jest specjalnie spowolnione, aby można było je wygodnie obserwować.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P017 - wypełnianie konturowe
//-----------------------------

#include <windows.h>
#include <SDL/SDL_gfx.h>
#include <math.h>     // funkcje sin, cos i sqrt
#include <time.h>     // do inicjalizacji generatora pseudolosowego
#include <stack>      // używamy STL do implementacji stosu

using namespace std;  // potrzebne dla STL!

const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach

int main(int argc, char *argv[])
{

  if(SDL_Init(SDL_INIT_VIDEO))
  {
    MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK);
    exit(-1);
  }

  atexit(SDL_Quit);
  
  SDL_Surface * screen;

  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE)))
  {
    MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK);
    exit(-1);
  }

  if(SDL_MUSTLOCK(screen))
    if(SDL_LockSurface(screen) < 0)
    {
      MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK);
      exit(-1);
    }

// inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// wyznaczamy środek ekranu

  Sint32 x = screen->w >> 1;
  Sint32 y = screen->h >> 1;
  
// rysujemy 20 losowych ramek tak, aby nie przykrywały środka ekranu
// ramki są zawsze 4-spójne

  SDL_Rect * r = new SDL_Rect;
  
  for(int i = 0; i < 20; i++)
  {
    do
    {
      r->x = rand() % screen->w;
      r->y = rand() % screen->h;
      r->w = rand() % (screen->w >> 3) + 4;
      r->h = rand() % (screen->h >> 3) + 4;
    }while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h));
    gfxClipRectangle(screen, r, 0xffff00);
  }
  
// rysujemy 20 losowych okręgów   tak, aby nie przykrywały środka
// okręgi są 8-spójne

  Sint32 xs, ys, rs;
  
  for(int i = 0; i < 20; i++)
  {
    do
    {
      xs = rand() % screen->w;
      ys = rand() % screen->h;
      rs = rand() % (screen->w >> 3) + 4;
    }while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs);
    gfxMoveTo(xs + rs, ys);
    for(int j = 1; j < 51; j++)
      gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)),
                            lround(ys + rs * sin(6.2831 * j / 50)), 0xffff00);
  }
    
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
// tutaj umieszczamy algorytm wypełniania

  Uint32 ccolor = 0xffff00;  // kolor konturu
  Uint32 fcolor = 0xff0000;  // kolor wypełnienia
  Uint32 pcolor;             // kolor piksela
  stack<Sint32> q;           // stos
  Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego

// obliczamy prostokąt obcinający

  cx1 = cy1 = 10;
  cx2 = screen->w - 10;
  cy2 = screen->h - 10;
  
  q.push(x); q.push(y);
  
  while(!q.empty())
  {
    y = q.top(); q.pop(); // pobieramy ze stosu x i y
    x = q.top(); q.pop();

// jeśli x,y jest w prostokącie obcinającym, przetwarzamy punkt

    if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2))
    {

// pobieramy kolor piksela na pozycji x,y

      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      pcolor = gfxGetPixel(screen, x, y);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

// jeśli ma on kolor konturu lub wypełnienia, nie przetwarzamy go

      if((pcolor == ccolor) || (pcolor == fcolor)) continue;

// wypełniamy piksel kolorem wypełnienia

      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      gfxPlot(screen, x, y, fcolor);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

// uaktualniamy ekran. Aby przyspieszyć, użyj SDL_UpdateRect(screen, x, y, 1, 1)

      SDL_UpdateRect(screen, 0, 0, 0, 0);

// na stosie umieszczamy współrzędne czterech sąsiednich pikseli

      q.push(x); q.push(y - 1);
      q.push(x + 1); q.push(y);
      q.push(x); q.push(y + 1);
      q.push(x - 1); q.push(y);           
    }
  }
  
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Sprawdź co się stanie, jeśli w powyższym programie zmienisz kolory ramek lub kolory okręgów. Wyjaśnij zachowanie się algorytmu.

Algorytm cztero-spójnego wypełniania powodziowego

Wejście

x, y  -   współrzędne ziarna wypełnienia. Ziarno musi się zawierać w prostokącie obcinającym clip.
fcolor  - kolor wypełnienia
clip  - prostokąt obcinający

Wyjście

Wypełnienie kolorem fcolor obszaru o kolorze ziarna z pozycji x,y. Jeśli obszar rozpościera się poza prostokąt obcinający, to wypełnienie ograniczy się tylko do prostokąta obcinania.

Zmienne pomocnicze

q  -   stos przechowujący współrzędne punktów.
cx1,cy1  - współrzędne lewego górnego narożnika prostokąta obcinania
cx2,cy2  - współrzędne prawego dolnego narożnika prostokąta obcinania
scolor  - kolor ziarna

Lista kroków

K01: cx1 ← clip.x ; obliczamy współrzędne wierzchołków prostokąta obcinającego
K02: cy1 ← clip.y  
K03: cx2 ← cx1 + clip.w - 1  
K04: cy2 ← cy1 + clip.h - 1  
K05: scolor ← kolor piksela na pozycji x,y ; odczytujemy kolor ziarna wypełnienia, wg którego będziemy śledzić piksele
K06: Wyzeruj stos q  
K07: Umieść na szczycie stosu x i y  
K08: Dopóki stos q nie jest pusty, wykonuj kroki K09...K19  
K09:     Pobierz ze stosu x i y ; pobieramy współrzędne ziarna wypełniania
K10:     Jeżeli x < cx1, wykonaj kolejny obieg pętli K08 ; sprawdzamy, czy ziarno x,y znajduje się w prostokącie obcinania
K11:     Jeżeli x > cx2, wykonaj kolejny obieg pętli K08 ; jeśli nie, punktu x,y nie przetwarzamy dalej w pętli
K12:     Jeżeli y < cy1, wykonaj kolejny obieg pętli K08  
K13:     Jeżeli y > cy2, wykonaj kolejny obieg pętli K08  
K14:     Jeżeli kolor piksela x,y ≠ scolor, wykonaj kolejny obieg pętli K08 ; natrafiliśmy na kolor brzegu obszaru, piksela nie przetwarzamy
K15:     Ustaw kolor piksela x,y na fcolor ; piksel kolorujemy na kolor wypełnienia
K16:     Umieść na stosie x i y - 1 ; na stos przesyłamy współrzędne czterech sąsiednich pikseli
K17:     Umieść na stosie x + 1 i y  
K18:     Umieść na stosie x i y + 1  
K19:     Umieść na stosie x - 1 i y  
K20: Zakończ  

Algorytm jest bardzo podobny do poprzedniego algorytmu wypełniania konturowego. Różnice leżą jedynie w warunkach sprawdzania kolorów wypełnianych pikseli. W algorytmie konturowym piksel nie mógł być w kolorze konturu oraz bieżącego wypełnienia. W algorytmie wypełniania obszaru piksel musi być w kolorze pierwszego ziarna.

Na podstawie powyższego algorytmu napiszemy prosty program testowy, który rysuje w różnych kolorach kilka ramek oraz okręgów na powierzchni graficznej, a następnie rozpoczyna wypełnianie obszaru począwszy od środka ekranu. Wypełnianie jest specjalnie spowolnione, aby można było je obserwować.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P018 - wypełnianie powodziowe
//------------------------------

#include <windows.h>
#include <SDL/SDL_gfx.h>
#include <math.h>     // funkcje sin, cos i sqrt
#include <time.h>     // do inicjalizacji generatora pseudolosowego
#include <stack>      // używamy STL do implementacji stosu

using namespace std;  // potrzebne dla STL!

const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach

int main(int argc, char *argv[])
{

  if(SDL_Init(SDL_INIT_VIDEO))
  {
    MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK);
    exit(-1);
  }

  atexit(SDL_Quit);
  
  SDL_Surface * screen;

  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE)))
  {
    MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK);
    exit(-1);
  }

  if(SDL_MUSTLOCK(screen))
    if(SDL_LockSurface(screen) < 0)
    {
      MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK);
      exit(-1);
    }

// inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// wyznaczamy środek ekranu

  Sint32 x = screen->w >> 1;
  Sint32 y = screen->h >> 1;
  
// rysujemy 20 losowych ramek w różnych kolorach tak, aby nie przykrywały środka ekranu
// ramki są zawsze 4-spójne

  SDL_Rect * r = new SDL_Rect;
  Uint32 color;

  for(int i = 0; i < 20; i++)
  {
    do
    {
      r->x = rand() % screen->w;
      r->y = rand() % screen->h;
      r->w = rand() % (screen->w >> 3) + 4;
      r->h = rand() % (screen->h >> 3) + 4;
    } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h));
    color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256);
    gfxClipRectangle(screen, r, color);
  }
  
// rysujemy 20 losowych okręgów w różnych kolorach tak, aby nie przykrywały środka
// okręgi są 8-spójne

  Sint32 xs, ys, rs;

  for(int i = 0; i < 20; i++)
  {
    do
    {
      xs = rand() % screen->w;
      ys = rand() % screen->h;
      rs = rand() % (screen->w >> 3) + 4;
    } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs);
    color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256);
    gfxMoveTo(xs + rs, ys);
    for(int j = 1; j < 51; j++)
      gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)),
                            lround(ys + rs * sin(6.2831 * j / 50)), color);
  }
    
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
// tutaj umieszczamy algorytm wypełniania

  Uint32 scolor;             // kolor ziarna
  Uint32 fcolor = 0xff0000;  // kolor wypełnienia
  Uint32 pcolor;             // kolor piksela
  stack<Sint32> q;           // stos
  Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego

// obliczamy prostokąt obcinający

  cx1 = cy1 = 10;
  cx2 = screen->w - 10;
  cy2 = screen->h - 10;
  
 if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
 scolor = gfxGetPixel(screen, x, y);
 if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);


  q.push(x); q.push(y);
  
  while(!q.empty())
  {
    y = q.top(); q.pop(); // pobieramy ze stosu x i y
    x = q.top(); q.pop();
    if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2))
    {
      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      pcolor = gfxGetPixel(screen, x, y);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

      if(pcolor != scolor) continue;

      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      gfxPlot(screen, x, y, fcolor);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

      SDL_UpdateRect(screen, 0, 0, 0, 0);

      q.push(x); q.push(y - 1);
      q.push(x + 1); q.push(y);
      q.push(x); q.push(y + 1);
      q.push(x - 1); q.push(y);           
    }
  }
  
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Zwróć uwagę na różnicę w działaniu algorytmu wypełnienia konturowego i powodziowego. Wypełnienie szuka konturu w zadanym kolorze, który ogranicza wypełniany obszar. Wszystkie inne kolory są zamalowywane kolorem wypełnienia. Natomiast wypełnienie powodziowe wypełnia tylko obszar tego samego koloru. Jeśli natrafi w nim na piksele w innym kolorze, to pozostawia je nienaruszone.

Sprawdź co się stanie, jeśli zamiast stosu użyjesz struktury kolejki jednokierunkowej - nowe elementy odkładamy na koniec listy, a pobieramy z początku listy - efekt jest bardzo ciekawy i pouczający. Eksperymentuj z podanymi przykładami, np. umieszczaj na stosie tylko niektórych sąsiadów ziarna - jak wpłynie to na sposób wypełniania obszaru?


Jeśli interesują cię wariackie sposoby wypełniania, to sprawdź działanie poniższego programu:

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P019 - wypełnianie zwariowane
//------------------------------

#include <windows.h>
#include <SDL/SDL_gfx.h>
#include <math.h>     // funkcje sin, cos i sqrt
#include <time.h>     // do inicjalizacji generatora pseudolosowego
#include <stack>      // używamy STL do implementacji stosu

using namespace std;  // potrzebne dla STL!

const int SCRX = 320; // stałe określające szerokość i wysokość
const int SCRY = 240; // ekranu w pikselach

int main(int argc, char *argv[])
{

  if(SDL_Init(SDL_INIT_VIDEO))
  {
    MessageBox(0, SDL_GetError(), "Błąd inicjalizacji SDL", MB_OK);
    exit(-1);
  }

  atexit(SDL_Quit);
  
  SDL_Surface * screen;

  if(!(screen = SDL_SetVideoMode(SCRX, SCRY, 32, SDL_HWSURFACE)))
  {
    MessageBox(0, SDL_GetError(), "Błąd tworzenia bufora obrazowego", MB_OK);
    exit(-1);
  }

  if(SDL_MUSTLOCK(screen))
    if(SDL_LockSurface(screen) < 0)
    {
      MessageBox(0, SDL_GetError(), "Błąd blokady bufora obrazowego", MB_OK);
      exit(-1);
    }

// inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));
  
// wyznaczamy środek ekranu

  Sint32 x = screen->w >> 1;
  Sint32 y = screen->h >> 1;
  
// rysujemy 20 losowych ramek w różnych kolorach tak, aby nie przykrywały środka ekranu
// ramki są zawsze 4-spójne

  SDL_Rect * r = new SDL_Rect;
  Uint32 color;

  for(int i = 0; i < 20; i++)
  {
    do
    {
      r->x = rand() % screen->w;
      r->y = rand() % screen->h;
      r->w = rand() % (screen->w >> 3) + 4;
      r->h = rand() % (screen->h >> 3) + 4;
    } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h));
    color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256);
    gfxClipRectangle(screen, r, color);
  }
  
// rysujemy 20 losowych okręgów w różnych kolorach tak, aby nie przykrywały środka
// okręgi są 8-spójne

  Sint32 xs, ys, rs;

  for(int i = 0; i < 20; i++)
  {
    do
    {
      xs = rand() % screen->w;
      ys = rand() % screen->h;
      rs = rand() % (screen->w >> 3) + 4;
    } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs);
    color = ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256);
    gfxMoveTo(xs + rs, ys);
    for(int j = 1; j < 51; j++)
      gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 50)),
                            lround(ys + rs * sin(6.2831 * j / 50)), color);
  }
    
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
// tutaj umieszczamy algorytm wypełniania

  Uint32 scolor;             // kolor ziarna
  Uint32 fcolor = 0xff0000;  // kolor wypełnienia
  Uint32 pcolor;             // kolor piksela
  stack<Sint32> q;           // stos
  Sint32 cx1, cy1, cx2, cy2; // współrzędne prostokąta obcinającego

// obliczamy prostokąt obcinający

  cx1 = cy1 = 10;
  cx2 = screen->w - 10;
  cy2 = screen->h - 10;
  
 if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
 scolor = gfxGetPixel(screen, x, y);
 if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);


  q.push(x); q.push(y);
  
  while(!q.empty())
  {
    y = q.top(); q.pop(); // pobieramy ze stosu x i y
    x = q.top(); q.pop();
    if((x >= cx1) && (x <= cx2) && (y >= cy1) && (y <= cy2))
    {
      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      pcolor = gfxGetPixel(screen, x, y);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

      if(pcolor != scolor) continue;

      if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
      gfxPlot(screen, x, y, fcolor);
      if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);

      SDL_UpdateRect(screen, 0, 0, 0, 0);

      switch(rand() % 4)
      {

        case 0: q.push(x);     q.push(y - 1);
                q.push(x + 1); q.push(y);
                q.push(x);     q.push(y + 1);
                q.push(x - 1); q.push(y);
                break;
        case 1: q.push(x + 1); q.push(y);
                q.push(x - 1); q.push(y);
                q.push(x);     q.push(y + 1);
                q.push(x);     q.push(y - 1);
                break;
        case 2: q.push(x);     q.push(y + 1);
                q.push(x);     q.push(y - 1);
                q.push(x - 1); q.push(y);
                q.push(x + 1); q.push(y);
                break;
        case 3: q.push(x - 1); q.push(y);
                q.push(x + 1); q.push(y);
                q.push(x);     q.push(y - 1);
                q.push(x);     q.push(y + 1);
                break;
     }
    }
  }
  
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Podsumowanie



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.