| |
Problem wypełniania obszaru można różnie definiować. Na początek
zajmę się dyskretną wersja zagadnienia, czyli algorytmami
działającymi bezpośrednio na zbiorze pikseli - rastrze.
Intuicja wskazuje, ze zagadnienie wypełniania obszaru ma sens
wyłącznie dla obszaru spójnego. Wyróżnia się obszary czterospójne
tj. takie gdzie sąsiednie piksele leżą bezpośrednio pod, nad, na
lewo lub na prawo oraz obszary ośmiospójne (patrz rysunek b) gdzie
dodatkowo piksele leżą wzdłuż przekątnych. |
|
|
W przypadku dyskretnym zakładamy, ze wnętrze obszaru jest zbiorem
czterospójnym, a otaczający je brzeg zbiorem czterospójnym.
Zakładamy, że brzeg i wnętrze obszaru określone są pewnymi kolorami.
Dopuszczamy także istnienie „wysp” wewnątrz wypełnianego obszaru.
Ostatnim założeniem jest to, ze znane jest położenie dowolnego
piksela wewnątrz obszaru.
Założenie o kolorze brzegu i wnętrza można poddawać modyfikacji.
Przykładowa implementacja opisanych poniżej algorytmów funkcjonuje w
ten sposób, że sprawdzany jest tylko kolor wypełnianego obszaru.
Każdy piksel o innym kolorze niż kolor tła traktowany jest jako
brzeg obszaru. |
| |
| |
| Rekurencyjny algorytm powodziowy |
Rekurencyjny algorytm powodziowy, zwany także wypełnianiem przez
sianie, zakłada sprawdzanie koloru każdego z czterech sąsiadów
piksela startowego. Dalej postępujemy tak samo badając kolor pikseli
sąsiadujących z sąsiadami piksela startowego itd. Rekurencyjny opis
przedkłada się zazwyczaj na rekurencyjną implementacje algorytmu, co
jest jego główną wadą (łatwo można doprowadzić do przepełnienia
stosu). Drugą wadą jest rozrzutność algorytmu objawiająca się
wielokrotnym badaniem koloru tego samego piksela. W niektórych
przypadkach kolor pojedynczego piksela badany jest nawet
pięciokrotnie.
|
| Algorytm Smitha |
| |
Algorytm Smitha nie posiada niedostatków opisanego przed chwilą
rekurencyjnego algorytmu powodziowego. W algorytmie Smitha [6]
obszar wypełniany jest liniami poziomymi w następujący sposób:
- zrzuć współrzędne piksela startowego (x, y) na stos
- dopóki stos nie jest pusty powtarzaj:
- pobierz współrzędne punktu ze stosu
- zrzuć na stos współrzędne punktów leżących nad i pod punktem
bieżącym, jeżeli ich kolor jest różny od koloru brzegu i koloru
wypełnienia; sprowadza się to do obserwacji sytuacji pod i nad
rysowaną linia - punkt powinien być zrzucany tylko jeden raz przy
zmianie koloru nad (pod) linia, np. podczas „wyjścia” spod pikseli
brzegowych
- wypełnij obszar w lewo (prawo), aż do napotkania piksela
brzegowego (czyli o kolorze brzegu lub wypełnienia).
Zastosowanie stosu w algorytmie Smitha gwarantuje wypełnienie
dowolnego obszaru.
|
|
|
|