algorytm.org

Flood fill

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Flood fill
Ocena użytkowników:***** / 10
SłabyŚwietny 
Wpisany przez Andrzej Borucki, 22 lutego 2012 20:27

Algorytm Flood Fill służy do wypełniania spójnych obszarów o określonym kolorze.
Wersję rekurencyjną tego algorytmu możemy elegancko przestawić:

FloodFill(int x,int y)
{
  if (punkt x,y leży poza granicami) return;
  if (kolor x,y różny od koloru który chcemy zmieniać) return;
  Zmień kolor punktu x, y;
  FloodFill(x, y-1); // wołanie procedury dla punktu powyżej
  FloodFill(x+1, y); // dla punktu z prawej strony
  FloodFill(x, y+1); // dla punktu poniżej
  FloodFill(x-1, y); // dla punktu z lewej strony
}


Algorytm przydatny jest w programach graficznych do wypełniania obszarów zadanym kolorem. Algorytm Flood Fill pozwala również na klasyfikację które piksele należą do którego obszaru, co może być przydatne w pierwszej fazie wektoryzacji lub rozpoznawania tekstu.
Przestawiony powyżej algorytm to tak zwana wersja czterokierunkowa, istnieje również wersja ośmiokierunkowa, która wywoływana jest również dla pikseli leżących po ukosie:

FloodFill(int x,int y)
{
  if (punkt x,y leży poza granicami) return;
  if (kolor x,y różny od koloru który chcemy zmieniać) return;
  Zmień kolor punktu x, y;
  FloodFill(x, y-1); // wołanie procedury dla punktu powyżej
  FloodFill(x+1, y-1); // dla punktu po ukosie prawo-powyżej
  FloodFill(x+1, y); // dla punktu z prawej strony
  FloodFill(x+1, y+1); // dla punktu po ukosie prawo-poniżej
  FloodFill(x, y+1); // dla punktu poniżej
  FloodFill(x-1, y+1); // dla punktu po ukosie lewo-poniżej
  FloodFill(x-1, y); // dla punktu z lewej strony
  FloodFill(x-1, y-1); // dla punktu po ukosie lewo-powyżej
}


Dlaczego wyróżnia się dwie wersje tego algorytmu i czym się różnią one w działaniu? Otóż wersja 4-kierunkowa nie potrafi "przelać" się przez linię z pojedynczych pikseli pod kątem 45 stopni. Poniżej wywołanie czterokierunkowego Flood Fill dla punktu w lewym górnym rogu:

Flood Fill wersja 4 kierunkowa


Natomiast wersja 8-kierunkowa nie ma z tym problemów:

Flood Fill wersja 8 kierunkowa


Rekurencyjna implementacja wypełniania obszarów jakkolwiek bardzo prosta i intuicyjna ma niestety pewne wady

Przykład w JavaScript:

Plik:
Typ:4-kierunkowy 8-kierunkowy
Kolor wypełnienia:
Wybierz z palety:


Istnieje również odmiana algorytmu wypełnienia obszaru ograniczonego obrysem o określonym kolorze; ta odmiana nosi nazwę Boundary Fill.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Andrzej BoruckiC#Visual C# Express 2010
.cs
.cs
***** / 2
Tomasz LubińskiJavaScript
.js
.js
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 01 września 2012 14:22
Dodaj komentarz