Zalewanie flood-fill'em

Tutaj możesz podyskutować na tematy nie kwalifikujące się do żadnego z pozostałych forów

Zalewanie flood-fill'em

Postautor: narbej » 08 lut 2015, 21:40

Wikipedia en pisze:Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.
Wikipedia pl pisze:Flood fill to algorytm używany np. w programach graficznych do wypełniania zamkniętych obszarów bitmapy kolorem. Korzysta z kolejki lub stosu.
W Wikipedi pl napisano: flood fill korzysta z kolejki lub stosu, ale z tego tylko powodu [z powodu korzystania] to absolutnie nie algorytm BSF czy DSF!
Algorytm, jak napisano powyżej potrzebuje zamkniętego, ograniczonego obszaru, otoczonego np murkiem. Pierwotnie wymyślono go dla bitmapy, ale łatwo go rozszerzyć na nasze [char] mapy-plany, czy na inną dowolną tablicę, np tablicę int.
Jest najbardziej prostym i jednocześnie efektywnym algorytmem do tego celu. Czy jednak, nie jest za bardzo prymitywnym? Szukając najkrótszej [najtańszej] drogi w grafie [algorytm Dijkstry], kolejne odległości zapamiętujemy w odwiedzanych węzłach. Jak wykorzystać flood fila też do takiego celu?.
Pseudo algorytm do Krainy Oz [znajdowanie odległóści pomiędzy wyspami] - jeżeli chcesz rozwiązać to zadanie całkowicie samodzielnie, skończ lekturę w tym miejscu.
  1. Zapuszczamy flooda "lądowego", na pierwszej napotkanej wyspie [pomijamy te w depresji], aby "zbudować" pierwotne ziarno wokół niej i po to aby ją "zaznaczyć", zatopić np zaznaczyć ją jako depresję.
  2. Po tych przygotowaniach włączamy stoper
  3. Zapamiętujemy wielkość kolejki K i uruchamiamy "pierwszą/następną falę" flooda.
  4. Gdy fala napotka dowolną inną wyspę, natychmiast zapisujemy stan stopera i zapuszczamy fluda lądowego na tej wyspie, aby żadna kolejna fala nie wprowadziła nas w błąd. Ale tym razem wznosimy ją odpowiednio wysoko nad poziom oceanu [mały wybuch wulkanu lub małej bombki]
  5. Po zdjęciu K elementów z kolejki, przesuwamy stoper [taki prymityw] o sekundę do przodu [warto to zautomatyzować].
  6. Gdy kolejka nie jest pusta Goto 3
  7. W ten sposób obsłużyliśmy wszystkie wyspy.
  8. Przywracamy mapę do pierwotnej postaci, oprócz wysp, które są w depresji
  9. goto 1
Widać więc, że mimo swego prymitywizmu flood fill współpracując z dokładnym stoperem i z pomiarem "objętości/wielkości" kolejnego czoła fali, może wykonywać skomplikowane zadania. W pseudokodzie powyżej brakuje jeszcze co najmniej jednego ważnego elementu - to już praca domowa dla Ciebie. Zamiast pomiaru aktualnej pojemności kolejki [wielkości czoła fali], można zastosować dwa przełączane na zmianę stosy [lub dwie kolejki]. Co kto i jak lubi.

Bezpieczne wkładanie i wyjmowanie do/z kolejki/stosu.
Ja jako trochę starszy i bardziej doświadczony, lubię to robić powoli i dokładnie. Najpierw dokładnie sprawdzam i jeżeli nadaje się, to dopiero wtedy powoli wkładam i wyjmuję. Całość trwa dłużej, ale wszyscy są raczej zadowoleni z efektów końcowych, nawet pani Maria Wesołowska vel sędzia Sędziospoj.
Młodzi wkładają bez sprawdzania, byle szybko i dużo, a efekty końcowe są z tego powodu/mogą być bardzo często dużo gorsze lub marne. Właśnie taki jeden z wielu przykładów: http://devel.sphere-research.com/phpBB3 ... 26f#p16908,
funkcja flood_fill (pozycja,zamieniany_kolor,nowy_kolor)
{
utwórz kolejka;
kolejka.wstaw(pozycja); // tu autor wkłada, bez sprawdzenia, co wkłada
dopóki(ilość_elementów(kolejka)>0)
{
nowa_pozycja = kolejka.ściągnij_element(); // tu wyciąga
jeżeli (kolor_na_pozycji(nowa_pozycja) = zamieniany_kolor) // a tu sprawdza co wyciagnął, ale ja bym to sprawdził co najmnie dwa razy '==', a nie raz '='
// ale może jestem nadmiernie podejrzliwy

{
ustaw_kolor(nowa_pozycja, nowy_kolor); // i tu wprawdzie zmienia pozycję na nową i zmienia kolor po sprawdzeniu, ale już poniżej:
kolejka.wstaw(lewo(nowa_pozycja)); // wkłada po kolei jak leci, bez sprawdzania, co wkłada, chyba, że robi to w nowej pozycji
kolejka.wstaw(prawo(nowa_pozycja)); // i tu wkłada po kolei jak leci, bez sprawdzania, chyba, że robi to w nowej pozycji
kolejka.wstaw(góra(nowa_pozycja)); // i tu wkłada po kolei jak leci, bez sprawdzania, chyba, że robi to w nowej pozycji
kolejka.wstaw(dół(nowa_pozycja)); // i tu wkłada po kolei jak leci, bez sprawdzania, chyba, że robi to w nowej pozycji
}
}
}
Nie mówię, że to jest źle. Chciałem tylko wyjątkowo obrazowo, pokazać, że można i że ja robię to trochę inaczej, ale możliwe, że wolniej.

Wnioski.
Flood-fill'a można łatwo zmusić [przystosować] do dowolnych innych potrzeb, np pomiaru długości linii brzegowej. Jeżeli masz jakieś pytania wątpliwości pytaj.
Jak zwykle, są tam prawdopodobnie małe/jakieś możliwości optymalizacji - trzeba to jeszcze głęboko przemyśleć. W zadaniu liniie brzegowe, oprócz murku, dodatkowy rów/rowy z wodą jest/są bardzo pożądane i korzystne. A jak w Krainie OZ? Czy tam też rów z wodą jest potrzebny i korzystny?

PS
Ta kraina, to nie kraina i to nie Oz, a trochę inne zadanie. To zadanie o trochę innym Imperium.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Wróć do Forum ogólne

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 1 gość

cron