Algorytm wypełniania przez przesianie

Algorytm wypełniania przez przesianie (seed fill algorithm).

Programując pod Windows mamy do dyspozycji doskonały DirectX, pod Linux mamy nie gorszy OpenGL (załączony też do Windows) - pakiety te oferują multum możliwości graficznych. Zachęcam jednak do zapoznania się z algorytmem wypełniania figury zamkniętej - jest do dobry przykład wykorzystania rekurencji, niezbędnej (i bardzo użytecznej) przy studiach graficznych. Posłużmy się językiem C. Potrzebna nam będą tylko dwie funkcje: potrafiąca zapalić punkt na ekranie i odczytać punkt z ekranu (jego kolor czyli, możemy się tu posłużyć choćby parą putpixel, setpixel znajdującą się w BGI Borland'a). Zakodujmy więc nagłówek naszej funkcji (będzie ona typu void, wynik nie jest nam żaden potrzebny):

void fill_seed (int x, int y, int edge_color,int color);

Argumenty x, y to miejsce startowe naszego wysiewania, color to kolor wysiewu, natomiast edge_color to kolor krawędzi, której nie wolno nam przekroczyć. Dalej mamy:

{
  int c=getpixel (x, y);
  if ((c!=edge_color) && (c!=color))
 {
    putpixel (x, y, color);
    fill_seed (x, y-1, edge_color, color);
    fill_seed (x, y+1, edge_color, color);
    fill_seed (x-1, y, edge_color, color);
    fill_seed (x+1, y, edge_color, color);
  }
}

Po pierwsze sprawdzamy kolor początku naszego wysiewu, następnie porównujemy ten kolor z kolorem krawędzi i kolorem wypełniania. Jeśli są one różne to zapalamy nasz pixel. Potem nasza funkcja wywołuje samą siebie, rozszerzając obszar wysiewu. Zauważ, że za każdym razem zmieniają się współrzędne początkowe (x i y) - o to się cały algorytm (poza porównaniami) rozbija. W ten sposób zasiewamy wybranym kolorem coraz większy obszar.

Zaletą tego rozwiązania jest prostota i wykorzystanie rekurencji, wadą (jak każdej funkcji rekurencyjnej) pamięciożerność. Więc upewnij się, że dysponujesz zawsze odpowiednim wolnym obszarem pamięci przed rozpoczęciem wysiewu. Im on większy, tym więcej pamięci potrzeba.