Jaki jest najlepszy algorytm „wypełniania wiadra”?

Jestem całkiem nowy w przetwarzaniu obrazu i obecnie pracuję nad aplikacją podobną do farby, która będzie zawierała wypełnienie wiadra. Nie mam jednak pojęcia, jaki jest najlepszy algorytm wypełniania wiadra.

Wdrożyłem przykład, który znalazłem na tej stronie , jednak wystąpiły problemy z nieskończoną pętlą, gdy użytkownik próbował wypełnić wiadro obszarem, który został już wypełniony wiadrem tego samego koloru.

Obecnie pracuję nad tym problemem, wypełniając w lewo, w prawo, w górę, a następnie w dół; jednak zrobiłem to, aby po wypełnieniu piksela po lewej stronie nie mógł wypełnić się po prawej stronie, co oznacza, że kształty takie jak:

Przykład

nie zostanie prawidłowo wypełniony, jeśli narzędzie łyżki zostanie użyte w czerwonej kropce.

Dlatego mam nadzieję, że ktoś zna algorytm lub link do takiego, który rozwiąże wszystkie te problemy.

Informacje dodatkowe: Zostanie to zaimplementowane przy użyciu Javascript jako narzędzia do malowania. Będzie on używany online z wykorzystaniem elementu Canvas.

algorithms

— Ivan
źródło

Czy ten wektor lub bitmapa jest oparta? Zakładam bitmapę na podstawie obrazu, ale upewniam się, że ...

— Demian Brecht

Myślę, że coś źle wdrożyłeś. Przejrzałem dokument i zgodnie z przykładami obrazów powinien on wypełniać obrazy takie jak powyższy. Skopiowałeś i wkleiłeś jego kod, czy napisałeś go od nowa?

— RLH

Pomyśl o przejściu przez wykres.

— Bwmat

@RLH: Skopiowałem i wkleiłem jego kod z kilkoma zmianami, aby działał z moją konfiguracją.

— Ivan

@Ivan: nie zaczynaj szukać nowego algo, zanim nie rozwiążesz problemów związanych z „nieskończoną pętlą”. Jeśli nawet nie możesz tego naprawić dla istniejącej implementacji, na pewno napotkasz o wiele więcej kłopotów, gdy będziesz chciał przepisać wszystko od nowa.

— Doc Brown,

Odpowiedzi:

Wygląda na to, że tak naprawdę szukasz algorytmu Flood Fill. Być może dlatego nie znalazłeś na to mnóstwo przykładów. Algorytm zawiera kilka metod wypełniania powodzi na stronie Wikipedii . Bardzo polecam jedną z nierekurencyjnych, „kolejkowanych” metod.

— Grandmaster B.
źródło

I highly recommend one of the non-recursive, 'queued' methods.- Czy możesz wyjaśnić dlaczego?

— Elfayer

@Elfayer Za każdym razem, gdy wywoływana jest funkcja (powiedzmy, że „X ()” wywołuje „Y ()”), parametry i lokalizacja pamięci z funkcji inicjującej („X ()”) są zapisywane na stosie. Jeśli więc wypełniasz dużą i skomplikowaną przestrzeń, pojawi się wiele wywołań funkcji rekurencyjnych. W zależności od kompilatora i języka może to prowadzić do przepełnienia stosu lub nadmiernego zużycia pamięci.

— boxcartenant

-1

Obecnie robię to samo. Jednak kiedy natknąłem się na problem, który wskazałeś, zdecydowałem się po prostu zakończyć funkcję, jeśli narzędzie zostało kliknięte nad obszarem tego samego koloru, który próbujesz malować (wydaje się to również zachowaniem MS-paint) .

Metoda kolejkowania powinna być wyjątkowo intuicyjna dla każdego, kto ma pewne doświadczenie w programowaniu.

Jeśli malowanie obszaru otaczającego plamę tego samego koloru co twoja farba jest problemem, możesz:

sprawdź kolor tła.
wyszukaj krawędź klikniętego miejsca w tym samym kolorze.
ustaw kolejkę wokół otaczających punktów na miejsce.
kontynuuj normalne wykonywanie, używając tej (w tym przypadku) kolejki wypełnionej białymi kropkami.

Jeśli chcesz, możesz rzucić okiem na mój (dość zawstydzający) kod tutaj .

Nie jest szybki, ale działa dobrze ...

— Juan Pablo Alvarez Alfaro
źródło

Dlaczego opinie negatywne? :( Wiem, że metoda nie jest szczególnie „szybka”, ale działa, podobnie jak proponowane rozwiązanie :(

— Juan Pablo Alvarez Alfaro

ten post jest raczej trudny do odczytania (ściana tekstu). Czy mógłbyś edytować go w lepszym kształcie?

— komara

Poważnie? Ludzie masowo głosowali, ponieważ trudno było je odczytać? Dlaczego nie zdecydować się na edycję? To nie jest tak, że treść jest problematyczna.

— l46kok

@ l46kok 'Istnieją inne powody, by głosować coś, ale „trudny do odczytania” jest uzasadniony. To nie jest jakiś konkurs na esej w szkole ... ”

— komiks