Algorytm Smitha

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
OL038 - podstawowe algorytmy wypełniania obszarów
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 SDL005.

 

Artykuł w PRZEBUDOWIE


SDL

Zaprezentowane w poprzednim rozdziale algorytmy wypełniania konturowego (ang. boundary fill) i powodziowego (ang. flood fill) posiadają istotne wady. Przy dużych powierzchniach stos może rozrastać się znacznie w pamięci i nie jest on efektywnie wykorzystywany - współrzędne tych samych pikseli mogą być wielokrotnie umieszczane na stosie prowadząc do pustych przebiegów głównej pętli algorytmu. Z tego powodu opracowano bardziej efektywne rozwiązania problemu wypełniania obszarów. Jednym z nich jest popularny algorytm Smitha.

Podstawowym ulepszeniem algorytmu wypełniania jest w przypadku algorytmu Smitha operowanie segmentami pikseli, a nie pojedynczymi pikselami. Przez segment będziemy rozumieli zbiór przyległych pikseli tworzących poziomy odcinek na powierzchni graficznej.

Segment definiujemy trójką (x,y,len), gdzie x i y oznaczają współrzędne początku segmentu, a len oznacza długość, czyli liczbę pikseli wchodzących w skład segmentu. Na przykład trójka (5,6,5) oznacza segment rozpoczynający się od piksela (5,6) i zawierający 5 pikseli.

O przynależności pikseli do segmentu decyduje rodzaj wypełniania. Dla wypełniania konturowego (ang. boundary fill) segment będą tworzyły przyległe piksele ograniczone z obu stron albo brzegiem prostokąta obcinania, albo pikselami w kolorze konturu. W tym przypadku kolor pikseli w segmencie nie ma znaczenia - musi być tylko różny od koloru konturu oraz koloru wypełnienia.

Przy wypełnianiu powodziowym (ang. flood fill) wszystkie piksele wchodzące w skład segmentu muszą posiadać ten sam kolor, różny od koloru wypełniania. Segment jest z obu stron ograniczony pikselami w innych kolorach lub prostokątem obcinania.

Pierwszym problemem, który musimy rozwiązać, jest znajdowanie maksymalnego segmentu pikseli, jeśli dane są współrzędne dowolnego piksela wchodzącego w skład segmentu. Problem rozwiązujemy przesuwając się po pikselach segmentu od początkowego punktu w lewo i prawo dopóki jest to możliwe, czyli do momentu, gdy natrafimy na ograniczenie - inny kolor piksela lub krawędź prostokąta obcinania.

Poniżej prezentujemy dwie wersje algorytmu funkcji findSegment() - dla wypełniania konturowego oraz dla wypełniania powodziowego. Znaleziony segment jako trójka (x,y,len) zostaje umieszczony na stosie.

Algorytm funkcji findBSegment() dla wypełniania konturowego

Wejście

x1, y1  -   współrzędne piksela segmentu.
bcolor  - kolor konturu obejmującego obszar wypełniany
cx1, cy1  - lewy górny narożnik prostokąta obcinania
cx2, cy2  - prawy dolny narożnik prostokąta obcinania
q  - stos

Wyjście

Umieszczenie na stosie q trójki definiującej segment. Funkcja jako wartość zwraca współrzędną x2 + 1, czyli pierwszą pozycję na osi X, od której może rozpocząć się nowy segment.

Zmienne pomocnicze

x2  -  współrzędna prawego końca segmentu
len  - długość segmentu w pikselach

Lista kroków

K01: x2 ← x1 ; ustawiamy koniec segmentu
K02:     x1 ← x1 - 1 ; próbujemy rozszerzyć segment w lewo
K03:     Jeśli x1 ≥ cx1 i kolor piksela x1,y1 ≠ bcolor, idź do K02 ; dopóki nie natrafimy na krawędź prostokąta obcinania lub kontur
K04: x1 ← x1 + 1 ; poszliśmy za daleko, cofamy się. W x1 początek segmentu
K05:     x2 ← x2 + 1 ; próbujemy rozszerzyć segment w prawo
K06:     Jeśli x2 ≤ cx2 i kolor piksela x2,y1 ≠ bcolor, idź do K05 ; dopóki nie natrafimy na krawędź prostokąta obcinania lub kontur
K07: len ← x2 - x1 ; obliczamy długość segmentu
K08: Umieść na stosie x1, y1, len ; trójkę definiującą segment umieszczamy na stosie
K09: Zwróć (x2 + 1) i zakończ algorytm  

Algorytm funkcji findFSegment() dla wypełniania powodziowego

Wejście

x1, y1  -   współrzędne piksela segmentu.
rcolor  - kolor wypełnianego obszaru
cx1, cy1  - lewy górny narożnik prostokąta obcinania
cx2, cy2  - prawy dolny narożnik prostokąta obcinania
q  - stos

Wyjście

Umieszczenie na stosie q trójki definiującej segment. Funkcja jako wartość zwracawspółrzędną x2 + 1, czyli pierwszą pozycję na osi X, od której może rozpocząć się nowy segment.

Zmienne pomocnicze

x2  -  współrzędna prawego końca segmentu
len  - długość segmentu w pikselach

Lista kroków

K01: x2 ← x1 ; ustawiamy koniec segmentu
K02:     x1 ← x1 - 1 ; próbujemy rozszerzyć segment w lewo
K03:     Jeśli x1 ≥ cx1 i kolor piksela x1,y1 = rcolor, idź do K02 ; dopóki nie natrafimy na krawędź prostokąta obcinania lub inny kolor
K04: x1 ← x1 + 1 ; poszliśmy za daleko, cofamy się. W x1 początek segmentu
K05:     x2 ← x2 + 1 ; próbujemy rozszerzyć segment w prawo
K06:     Jeśli x2 ≤ cx2 i kolor piksela x2,y1 = rcolor, idź do K05 ; dopóki nie natrafimy na krawędź prostokąta obcinania lub inny kolor
K07: len ← x2 - x1 ; obliczamy długość segmentu
K08: Umieść na stosie x1, y1, len ; trójkę definiującą segment umieszczamy na stosie
K09: Zwróć (x2 + 1) i zakończ algorytm  

Zwróć uwagę, iż oba algorytmy różnią się tylko w krokach K03 oraz K06, gdzie sprawdzamy warunek przynależności nowego piksela do wyznaczanego segmentu.


Drugi problem polega na wyznaczaniu wszystkich segmentów przyległych od góry i od dołu do danego segmentu i umieszczeniu ich na stosie.

W celu rozwiązania tego problemu przeglądamy kolejne piksele leżące ponad i poniżej danego segmentu. Jeśli natrafimy na piksel, który może należeć do nowego segmentu (np. dla wypełnienia konturowego piksel nie posiada ani koloru konturu, ani koloru wypełnienia), uruchamiamy funkcję findSegment() ze współrzędnymi tego piksela. Funkcja wyznaczy współrzędne początku nowego segmentu oraz zwróci jego długość - dodatkowo tę trójkę umieści na stosie. Wykorzystujemy długość wyznaczonego segmentu, aby przesunąć się o odpowiednią ilość pikseli wzdłuż podstawowego segmentu - przesuwamy się o jeden piksel więcej w prawo niż wynosi współrzędna końca znalezionego segmentu. Operację kontynuujemy aż do przejścia przez cały segment. Poniżej przedstawiamy algorytm funkcji searchSegment() dla obu typów wypełnień:

Algorytm funkcji searchBSegment() dla wypełnienia konturowego

Wejście

x1, y1  -   współrzędne początku segmentu do przeszukania
len  - długość przeszukiwanego segmentu
bcolor  - kolor konturu
fcolor  - kolor wypełnienia

Wyjście

Umieszczenie na stosie q wszystkich segmentów wpadających w dany segment.

Zmienne pomocnicze

x2  -  współrzędna prawego końca segmentu

Lista kroków

K01: x2 ← x1 + len - 1 ; wyznaczamy koniec segmentu
K02: Dopóki x1 ≤ x2: wykonuj kroki K03...K06 ; skanujemy segment bazowy
K03:     pcolor ← kolor piksela na pozycji x1,y1 ; odczytujemy kolor piksela
K04:     Jeżeli pcolor = fcolor, zwiększ x1 ← x1 + 2 i kontynuuj pętlę ; przeskakujemy obszar już wypełniony + piksel konturu
K05:     Jeżeli pcolor = bcolor, zwiększ x1 ← x1 + 1 i kontynuuj pętlę ; przeskakujemy piksel konturu
K06:     x1 ← findBSegment(x1,y1) ; przeskakujemy znaleziony segment i umieszczamy go na stosie
K07: Zakończ  

Algorytm funkcji searchFSegment() dla wypełnienia powodziowego

Wejście

x1, y1  -   współrzędne początku segmentu do przeszukania
len  - długość przeszukiwanego segmentu
rcolor  - kolor wypełnianego obszaru
fcolor  - kolor wypełnienia

Wyjście

Umieszczenie na stosie q wszystkich segmentów wpadających w segment (x1,y1,len)

Zmienne pomocnicze

x2  -  współrzędna prawego końca segmentu
pcolor  -  kolor piksela w segmencie

Lista kroków

K01: x2 ← x1 + len - 1 ; wyznaczamy koniec segmentu
K02: Dopóki x1 ≤ x2: wykonuj kroki K03...K06 ; skanujemy segment bazowy
K03:     pcolor ← kolor piksela na pozycji x1,y1 ; odczytujemy kolor piksela
K04:     Jeżeli pcolor = fcolor, zwiększ x1 ← x1 + 2 i kontynuuj pętlę ; przeskakujemy obszar już wypełniony + piksel granicy
K05:     Jeżeli pcolor ≠ rcolor, zwiększ x1 ← x1 + 1 i kontynuuj pętlę ; przeskakujemy piksel granicy
K06:     x1 ← findFSegment(x1,y1) ; przeskakujemy znaleziony segment i umieszczamy go na stosie
K07: Zakończ  

Teraz możemy już opisać algorytm wypełniania obszaru metodą Smitha. Poniżej przedstawiamy dwie wersje algorytmu:

Algorytm Smitha wypełniania konturowego

Wejście

x, y  -   współrzędne ziarna, od którego rozpocznie się wypełnianie obszaru
bcolor  - kolor konturu, który ogranicza wypełniany obszar
fcolor  - kolor wypełnienia
clip  - prostokąt obcinający

Wyjście

Wypełnia kolorem fcolor obszar ograniczony ośmiospójną linią konturu w kolorze bcolor oraz prostokątem obcinającym clip.

Zmienne pomocnicze

q  -  stos
len  - długość przetwarzanych segmentów
cx1, cy1  - lewy górny narożnik prostokąta obcinania
cx2, cy2  - prawy dolny narożnik prostokąta obcinania

Lista kroków

K01: cx1 ← clip.x ; obliczamy prostokąt obcinający
K02: cy1 ← clip.y  
K03: cx2 ← cx1 + clip.w - 1  
K04: cy2 ← cy1 + clip.h - 1  
K05: Wywołaj funkcję findBSegment(x,y) ; znajdujemy pierwszy segment i umieszczamy go na stosie
K06: Dopóki stos q zawiera dane, wykonuj kroki K07...K10  
K07:     Pobierz ze stosu x,y,len ; pobieramy segment ze stosu
K08:     Wypełnij segment kolorem fcolor ; faktyczne wypełnianie obszaru kolorem fcolor
K09:     Jeżeli y > cy1, wywołaj searchBSegment(x,y-1,len) ; przeszukujemy górę segmentu umieszczając na stosie znalezione segmenty
K10:     Jeżeli y < cy2, wywołaj searchBSegment(x,y+1,len) ; przeszukujemy dół segmentu umieszczając na stosie znalezione segmenty
K11: Zakończ  

Algorytm Smitha wypełniania powodziowego

Wejście

x, y  -   współrzędne ziarna, od którego rozpocznie się wypełnianie obszaru
fcolor  - kolor wypełnienia
clip  - prostokąt obcinający

Wyjście

Wypełnia kolorem fcolor obszar ograniczony ośmiospójnymi obszarami i liniami w kolorach różnych od koloru obszaru oraz prostokątem obcinającym clip.

Zmienne pomocnicze

q  -  stos
len  - długość przetwarzanych segmentów
rcolor  - kolor wypełnianego obszaru
cx1, cy1  - lewy górny narożnik prostokąta obcinania
cx2, cy2  - prawy dolny narożnik prostokąta obcinania

Lista kroków

K01: cx1 ← clip.x ; obliczamy prostokąt obcinający
K02: cy1 ← clip.y  
K03: cx2 ← cx1 + clip.w - 1  
K04: cy2 ← cy1 + clip.h - 1  
K05: rcolor ← kolor piksela x,y ; zapamiętujemy kolor obszaru dla findFSegment() i searchFSegment()
K06: Wywołaj funkcję findFSegment(x,y) ; znajdujemy pierwszy segment i umieszczamy go na stosie
K07: Dopóki stos q zawiera dane, wykonuj kroki K08...K11  
K08:     Pobierz ze stosu x,y,len ; pobieramy segment ze stosu
K09:     Wypełnij segment kolorem fcolor ; faktyczne wypełnianie obszaru kolorem fcolor
K10:     Jeżeli y > cy1, wywołaj searchFSegment(x,y-1,len) ; przeszukujemy górę segmentu umieszczając na stosie znalezione segmenty
K11:     Jeżeli y < cy2, wywołaj searchFSegment(x,y+1,len) ; przeszukujemy dół segmentu umieszczając na stosie znalezione segmenty
K12: Zakończ  

Na podstawie dwóch powyższych algorytmów napiszemy programy testujące ich działanie. Na obszarze graficznym zostaną narysowane prostokąty oraz sześciokąty. Prostokąty posiadają kontur czterospójny, a sześciokąty posiadają kontur ośmiospójny. Prostokąty i sześciokąty będą rysowane tak, aby nie obejmowały środka powierzchni graficznej, który będzie ziarnem wypełnienia.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P020 - algorytm Smitha - 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

SDL_Surface * screen;
Uint32 bcolor = 0xffff00;  // kolor konturu
Uint32 fcolor = 0xff0000;  // kolor wypełniania
Sint32 cx1,cx2,cy1,cy2;    // współrzędne prostokąta obcinającego
stack<Sint32> q;           // stos

inline void lock()
{
  if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
}

inline void unlock()
{
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
}

// funkcja wyznacza współrzędne segmentu
// x1, y1 - punkt startowy
// Wynikiem funkcji jest długość segmentu
// segment jest automatycznie umieszczany na stosie
//-------------------------------------------------
Sint32 findBSegment(Sint32 x1, Sint32 y1)
{
  Sint32 x2 = x1;
  Sint32 len;
  while(true)
  {
    x1--;
    if((x1 < cx1) || (gfxGetPixel(screen, x1, y1) == bcolor))
    {
      x1++; break;
    }
  }
  while(true)
  {
    x2++;
    if((x2 > cx2) || (gfxGetPixel(screen, x2, y1) == bcolor)) break;
  }
  len = x2 - x1;
  q.push(x1); q.push(y1); q.push(len);
  return x2 + 1;
}
  
// funkcja znajduje wszystkie segmenty leżące wewnątrz
// danego segmentu ekranu
// x1, y1 - współrzędne początku przeszukiwanego segmentu
// len  - długość przeszukiwanego segmentu
//---------------------------------------------------------
void searchBSegment(Sint32 x1, Sint32 y1, Sint32 len)
{
  Sint32 x2 = x1 + len - 1;
  
  while(x1 <= x2)
  {
    Uint32 pcolor = gfxGetPixel(screen, x1, y1);
    if(pcolor == fcolor)      x1 += 2;
    else if(pcolor == bcolor) x1++;
    else                      x1 = findBSegment(x1, y1);
  }
}

// Tutaj rozpoczyna się program główny

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);
  
  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 100 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 < 100; i++)
  {
    do
    {
      r->x = rand() % screen->w;
      r->y = rand() % screen->h;
      r->w = rand() % (screen->w >> 4) + 3;
      r->h = rand() % (screen->h >> 4) + 3;
    } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h));
    gfxClipRectangle(screen, r, bcolor);
  }
  
// rysujemy 100 losowych sześciokątów tak, aby nie przykrywały środka
// sześciokąty są 8-spójne

  Sint32 xs, ys, rs;

  for(int i = 0; i < 100; i++)
  {
    do
    {
      xs = rand() % screen->w;
      ys = rand() % screen->h;
      rs = rand() % (screen->w >> 4) + 4;
    } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs);
    gfxMoveTo(xs + rs, ys);
    for(int j = 1; j < 7; j++)
      gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 6)),
                            lround(ys + rs * sin(6.2831 * j / 6)), bcolor);
  }
  
// tutaj umieszczamy algorytm wypełniania

// obliczamy prostokąt obcinania

  cx1 = cy1 = 10;
  cx2 = screen->w - 10;
  cy2 = screen->h - 10;
  
// wyznaczamy pierwszy segment
  
  findBSegment(x,y);
  
// Główna pętla algorytmu wypełniania

  while(!q.empty())
  {
    Sint32 len;    // długość segmentu w pikselach

// pobieramy ze stosu segment
    
    len = q.top(); q.pop();  
    y   = q.top(); q.pop();  
    x   = q.top(); q.pop();
    
// wypełniamy segment kolorem wypełnienia

    gfxHLine(screen, x, y, fcolor, len);

//  odświeżamy ekran

    unlock();
    SDL_UpdateRect(screen, 0, 0, 0, 0);
    lock();

// przeglądamy górę segmentu
    
    if(y > cy1) searchBSegment(x, y - 1, len);

// przeglądamy dół segmentu

    if(y < cy2) searchBSegment(x, y + 1, len);
 
  }

  unlock();
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Druga wersja programu realizuje wypełnianie powodziowe - kolorem wypełnienia zostanie zamalowany obszar o jednolitym kolorze. Ograniczeniem tego obszaru są piksele w dowolnych innych kolorach niż on sam. Dlatego stosujemy białe prostokąty i żółte sześciokąty.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P021 - algorytm Smitha - 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

SDL_Surface * screen;
Uint32 rcolor = 0xffff00;  // kolor wypełnianego obszaru
Uint32 fcolor = 0xff0000;  // kolor wypełniania
Sint32 cx1,cx2,cy1,cy2;    // współrzędne prostokąta obcinającego
stack<Sint32> q;           // stos

inline void lock()
{
  if(SDL_MUSTLOCK(screen)) SDL_LockSurface(screen);
}

inline void unlock()
{
  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
}

// funkcja wyznacza współrzędne segmentu
// x1, y1 - punkt startowy
// Wynikiem funkcji jest długość segmentu
// segment jest automatycznie umieszczany na stosie
//-------------------------------------------------
Sint32 findFSegment(Sint32 x1, Sint32 y1)
{
  Sint32 x2 = x1;
  Sint32 len;
  while(true)
  {
    x1--;
    if((x1 < cx1) || (gfxGetPixel(screen, x1, y1) != rcolor))
    {
      x1++; break;
    }
  }
  while(true)
  {
    x2++;
    if((x2 > cx2) || (gfxGetPixel(screen, x2, y1) != rcolor)) break;
  }
  len = x2 - x1;
  q.push(x1); q.push(y1); q.push(len);
  return x2 + 1;
}
  
// funkcja znajduje wszystkie segmenty leżące wewnątrz
// danego segmentu ekranu
// x1, y1 - współrzędne początku przeszukiwanego segmentu
// len  - długość przeszukiwanego segmentu
//---------------------------------------------------------
void searchFSegment(Sint32 x1, Sint32 y1, Sint32 len)
{
  Sint32 x2 = x1 + len - 1;
  
  while(x1 <= x2)
  {
    Uint32 pcolor = gfxGetPixel(screen, x1, y1);
    if(pcolor == fcolor)      x1 += 2;
    else if(pcolor != rcolor) x1++;
    else                      x1 = findFSegment(x1, y1);
  }
}

// Tutaj rozpoczyna się program główny

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);
  
  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 100 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 < 100; i++)
  {
    do
    {
      r->x = rand() % screen->w;
      r->y = rand() % screen->h;
      r->w = rand() % (screen->w >> 4) + 3;
      r->h = rand() % (screen->h >> 4) + 3;
    } while((r->x <= x) && (x < r->x + r->w) && (r->y <= y) && (y < r->y + r->h));
    gfxClipRectangle(screen, r, 0xffffff);
  }
  
// rysujemy 100 losowych sześciokątów tak, aby nie przykrywały środka
// sześciokąty są 8-spójne

  Sint32 xs, ys, rs;

  for(int i = 0; i < 100; i++)
  {
    do
    {
      xs = rand() % screen->w;
      ys = rand() % screen->h;
      rs = rand() % (screen->w >> 4) + 4;
    } while(sqrt((x - xs) * (x - xs) + (y - ys) * (y - ys)) <= rs);
    gfxMoveTo(xs + rs, ys);
    for(int j = 1; j < 7; j++)
      gfxClipLineTo(screen, lround(xs + rs * cos(6.2831 * j / 6)),
                            lround(ys + rs * sin(6.2831 * j / 6)), 0xffff00);
  }
  
// tutaj umieszczamy algorytm wypełniania

// obliczamy prostokąt obcinania

  cx1 = cy1 = 10;
  cx2 = screen->w - 10;
  cy2 = screen->h - 10;
  
// odczytujemy kolor obszaru

  rcolor = gfxGetPixel(screen, x, y);
  
// wyznaczamy pierwszy segment
  
  findFSegment(x, y);
  
// Główna pętla algorytmu wypełniania

  while(!q.empty())
  {
    Sint32 len;    // długość segmentu w pikselach

// pobieramy ze stosu segment
    
    len = q.top(); q.pop();  
    y   = q.top(); q.pop();  
    x   = q.top(); q.pop();
    
// wypełniamy segment kolorem wypełnienia

    gfxHLine(screen, x, y, fcolor, len);

//  odświeżamy ekran

    unlock();
    SDL_UpdateRect(screen, 0, 0, 0, 0);
    lock();

// przeglądamy górę segmentu
    
    if(y > cy1) searchFSegment(x, y - 1, len);

// przeglądamy dół segmentu

    if(y < cy2) searchFSegment(x, y + 1, len);
 
  }

  unlock();
  MessageBox(0, "Kliknij przycisk OK", "Koniec", MB_OK);
  return 0;
}

Na podstawie opisanych powyżej algorytmów tworzymy dwie funkcje biblioteczne:

Funkcje biblioteczne zostały odpowiednio zoptymalizowane na szybkość działania, zatem ich kod różni się nieco od kodu powyższych programów. Jednakże pracują one dokładnie wg podanego algorytmu.

Na początku pliku SDL_gfx.cpp dopisz wiersze zaznaczone na czerwono:

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne 2007
//
// Biblioteka procedur graficznych dla trybów 32 bitowych
//-------------------------------------------------------

#include <SDL/SDL_gfx.h>

#include <stack>

using namespace std;

//------------------
// DEFINICJE FUNKCJI
//------------------

Na końcu pliku SDL_gfx.cpp dopisz kody funkcji gfxBoundaryFill() oraz gfxFloodFill():

// gfxBoundaryFill wypełnia obszar ograniczony prostokątem obcinania
// zawartym w strukturze SDL_Surface oraz konturem
// screen - wskaźnik struktury SDL_Surface
// x,y    - adres ziarna początkowego
// fcolor - kolor wypełniania
// bcolor - kolor konturu - brzegu
//------------------------------------------------------------------

void gfxBoundaryFill(SDL_Surface * screen, Sint32 x, Sint32 y, Uint32 fcolor, Uint32 bcolor)
{
  Sint32 cx1 = screen->clip_rect.x;
  Sint32 cy1 = screen->clip_rect.y;
  Sint32 cx2 = cx1 + screen->clip_rect.w - 1;
  Sint32 cy2 = cy1 + screen->clip_rect.h - 1;
  Sint32 x1;
  Sint32 x2 = x;
  Sint32 bx1;
  Sint32 bx2;
  Uint32 * p1 = (Uint32 *)screen->pixels + y * screen->w + x;
  Uint32 * p2 = p1;
  Sint32 len = x2 - x;
  stack<Sint32> q;

  while((--x >= cx1) && (*(--p1) != bcolor));

  x++;

  while((++x2 <= cx2) && (*(++p2) != bcolor));

  q.push(x); q.push(y); q.push(len);

  while(!q.empty())
  {
    len = q.top(); q.pop();
    y   = q.top(); q.pop();
    x   = q.top(); q.pop();

    gfxHLine(screen, x, y, fcolor, len);

    if(y > cy1)
    {
      x1 = x;
      x2 = x1 + len - 1;

      p1 = (Uint32 *)screen->pixels + (y - 1) * screen->w + x1;

      while(x1 <= x2)
      {
         if(* p1 == fcolor)
         {
           x1 += 2; p1 += 2;     
         }
         else if(* p1 == bcolor)
         {
           x1++; p1++;
         }
         else
         {
           bx1 = x1;
           bx2 = x1;
           p2 = p1;

           while((--bx1 >= cx1) && (*(--p2) != bcolor));

           bx1++;
           p2 = p1;

           while((++bx2 <= cx2) && (*(++p2) != bcolor));
 
           q.push(bx1); q.push(y - 1); q.push(bx2 - bx1);
           x1 = bx2 + 1; p1 = p2 + 1;
         }
      }
    }
    if(y < cy2)
    {
      x1 = x;
      x2 = x1 + len - 1;

      p1 = (Uint32 *)screen->pixels + (y + 1) * screen->w + x1;

      while(x1 <= x2)
      {
         if(* p1 == fcolor)
         {
           x1 += 2; p1 += 2;     
         }
         else if(* p1 == bcolor)
         {
           x1++; p1++;
         }
         else
         {
           bx1 = x1;
           bx2 = x1;
           p2 = p1;

           while((--bx1 >= cx1) && (*(--p2) != bcolor));

           bx1++;
           p2 = p1;

           while((++bx2 <= cx2) && (*(++p2) != bcolor));

           q.push(bx1); q.push(y + 1); q.push(bx2 - bx1);
           x1 = bx2 + 1; p1 = p2 + 1;
         }
      }         
    }
  }
}

// gfxFloodFill wypełnia obszar ograniczony prostokątem obcinania
// zawartym w strukturze SDL_Surface oraz obszarami w innych kolorach
// screen - wskaźnik struktury SDL_Surface
// x,y    - adres ziarna początkowego
// fcolor - kolor wypełniania
//------------------------------------------------------------------

void gfxFloodFill(SDL_Surface * screen, Sint32 x, Sint32 y, Uint32 fcolor)
{
  Sint32 cx1 = screen->clip_rect.x;
  Sint32 cy1 = screen->clip_rect.y;
  Sint32 cx2 = cx1 + screen->clip_rect.w - 1;
  Sint32 cy2 = cy1 + screen->clip_rect.h - 1;
  Sint32 x1;
  Sint32 x2 = x;
  Sint32 bx1;
  Sint32 bx2;
  Uint32 * p1 = (Uint32 *)screen->pixels + y * screen->w + x;
  Uint32 * p2 = p1;
  Uint32 rcolor = * p1;
  Sint32 len = x2 - x;
  stack<Sint32> q;

  while((--x >= cx1) && (*(--p1) == rcolor));

  x++;

  while((++x2 <= cx2) && (*(++p2) == rcolor));

  q.push(x); q.push(y); q.push(len);

  while(!q.empty())
  {
    len = q.top(); q.pop();
    y   = q.top(); q.pop();
    x   = q.top(); q.pop();

    gfxHLine(screen, x, y, fcolor, len);

    if(y > cy1)
    {
      x1 = x;
      x2 = x1 + len - 1;

      p1 = (Uint32 *)screen->pixels + (y - 1) * screen->w + x1;

      while(x1 <= x2)
      {
         if(* p1 == fcolor)
         {
           x1 += 2; p1 += 2;     
         }
         else if(* p1 != rcolor)
         {
           x1++; p1++;
         }
         else
         {
           bx1 = x1;
           bx2 = x1;
           p2 = p1;

           while((--bx1 >= cx1) && (*(--p2) == rcolor));

           bx1++;
           p2 = p1;

           while((++bx2 <= cx2) && (*(++p2) == rcolor));

           q.push(bx1); q.push(y - 1); q.push(bx2 - bx1);
           x1 = bx2 + 1; p1 = p2 + 1;
         }
      }
    }
    if(y < cy2)
    {
      x1 = x;
      x2 = x1 + len - 1;

      p1 = (Uint32 *)screen->pixels + (y + 1) * screen->w + x1;

      while(x1 <= x2)
      {
         if(* p1 == fcolor)
         {
           x1 += 2; p1 += 2;     
         }
         else if(* p1 != rcolor)
         {
           x1++; p1++;
         }
         else
         {
           bx1 = x1;
           bx2 = x1;
           p2 = p1;

           while((--bx1 >= cx1) && (*(--p2) == rcolor));

           bx1++;
           p2 = p1;

           while((++bx2 <= cx2) && (*(++p2) == rcolor));

           q.push(bx1); q.push(y + 1); q.push(bx2 - bx1);
           x1 = bx2 + 1; p1 = p2 + 1;
         }
      }         
    }
  }     
}

Na końcu pliku SDL_gfx.h dopisz:


void gfxBoundaryFill(SDL_Surface * screen, Sint32 x, Sint32 y, Uint32 fcolor, Uint32 bcolor);

void gfxFloodFill(SDL_Surface * screen, Sint32 x, Sint32 y, Uint32 fcolor);

Parametry funkcji gfxBoundaryFill() i gfxFloodFill() są następujące:

screen  -   wskaźnik struktury SDL_Surface definiującej powierzchnię graficzną
x,y  - współrzędne piksela, który jest ziarnem wypełnienia
fcolor  - kolor wypełnienia
bcolor  - dla gfxBoundaryFill() określa kolor konturu, który ogranicza wypełniany obszar

Obie funkcje reagują na prostokąt obcinający zdefiniowany wewnątrz struktury SDL_Surface.

Poniżej przedstawiamy program testujący dla obu funkcji. Program wypełnia ekran ramkami, które następnie otwiera linią w kolorze czarnym. Dla funkcji gfxBoundaryFill() ramki są w kolorze konturu - żółtym. Dla funkcji gfxFloodFill() ramki są w różnych kolorach.

// I Liceum Ogólnokształcące
// w Tarnowie
// Koło informatyczne
//
// P022 - algorytm Smitha - wypełnianie konturowe i powodziowe
//------------------------------------------------------------

#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));

// Współrzędna x środka ekranu

  Sint32 x = screen->w >> 1;
  
// W lewej połówce rysujemy ramki żółte

  SDL_Rect * r = new SDL_Rect;
  
  r->x = r->y = 0;
  r->w = x - 1;
  r->h = screen->h;
  
  do
  {
    gfxRectangle(screen, r, 0xffff00);
    r->x += 4; r->y += 4; r->w -= 8; r->h -= 8;           
  }while((r->w > 8) && (r->h > 8));
  
// W prawej połówce rysujemy ramki różnokolorowe

  r->x = x + 1;
  r->y = 0;
  r->w = x - 1;
  r->h = screen->h;
  
  do
  {
    gfxRectangle(screen, r, ((rand() % 256) << 16) | ((rand() % 256) << 8) | (rand() % 256));
    r->x += 4; r->y += 4; r->w -= 8; r->h -= 8;           
  }while((r->w > 8) && (r->h > 8));
   
// Rozdzielamy ramki ukośną czarną linią

  gfxLine(screen, 3, 3, x - 3, screen->h - 3, 0);
  gfxLine(screen, screen->w - 3, 3, x + 3, screen->h - 3, 0);
  
// Lewą połówkę wypełniamy konturowo kolorem czerwonym

  gfxBoundaryFill(screen, x >> 1, screen->h >> 1, 0xff0000, 0xffff00);
  
// Prawą połówkę wypełniamy powodziowo kolorem niebieskim

  gfxFloodFill(screen, x + (x >> 1), screen->h >> 1, 0x0000ff);

  if(SDL_MUSTLOCK(screen)) SDL_UnlockSurface(screen);
  
  SDL_UpdateRect(screen, 0, 0, 0, 0);
  
  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.