Algorytmy

Algorytm wypełniania przez przesianie

  • 2006-06-29 20:29
  • 4 komentarze
  • 1062 odsłony
  • Oceń ten tekst jako pierwszy
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.

4 komentarze

lukaswhite 2008-01-17 12:40

czy ktos moze podeslac plik z gotowym juz programem?albo zamiescic tutaj odnosnik? dzieki z góry

JeanQ 2010-06-08 17:39

Zalety:
     - kod krótki i przejrzysty
     - funkcja po skompilowaniu zajmie kilkadziesiąt bajtów
Wady:
     - nie za szybkie
     - niech bozia ma stos w opiece

Unabomber 2003-03-28 09:30

ladne ale dla duzych figur zajmuje za duzo czasu i staje sie metoda nieefektywna

Vogel 2002-12-30 11:49

Można zrezygnować z rekurencji odkładając kolejne współrzędne na kolejkę i je potem z niej pobierając.