Implementacja Flood Fill

Question

To jest moja implementacja C# opartego na stosie algorytmu wypełniania powodziowego (który oparłem na definicji wikipedii). Wcześniej, podczas kodowania, chciałem tylko zobaczyć, jak działa. I tak się stało. Następnie chciałem poznać liczbę pikseli, która w rzeczywistości była wypełniona . W moim kodzie zmieniłem typ zwracany na int i zwróciłem zmienną "ctr". Ale okazało się, że ctr jest w przybliżeniu dwa razy większą od rzeczywistej liczby wypełnionych pikseli (wykonałem osobną funkcję wyłącznie w celu zliczania tych pikseli - żeby wiedzieć na pewno).

Czy ktoś może dowiedzieć się, w jaki sposób i dlaczego zmienna "ctr" jest inkrementowana dwukrotnie, tak jak powinna być?

* Klasa Pixel służy tylko jako pojemnik dla wartości x, y i koloru pikseli z bitmapy.

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor) 
{ 
    Bitmap result = new Bitmap(image.Width, image.Height); 
    Stack<Pixel> pixels = new Stack<Pixel>(); 
    Color oldColor = image.GetPixel(x, y); 
    int ctr = 0; 

    pixels.Push(new Pixel(x, y, oldColor)); 

    while (pixels.Count > 0) 
    { 
     Pixel popped = pixels.Pop(); 

     if (popped.color == oldColor) 
     { 
      ctr++; 
      result.SetPixel(popped.x, popped.y, newColor); 

      pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y)); 
      pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y)); 
      pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1)); 
      pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1)); 
     } 
    } 

    return result; 
} 

Answer 1

Robisz sprawdzić kolor piksela tutaj:

if (popped.color == oldColor) 

Ale popped.color może być (i apperently jest w 50% przypadków) przestarzałych. Ponieważ nie zaznaczasz duplikatów, gdy wstawisz piksel do swojego stosu, będziesz mieć duplikaty. Po wyświetleniu tych duplikatów atrybut koloru zostałby zapisany dawno temu.

Może robi się jaśniejsze z rysunku:

Jako przykład wziąłem bitmapę z 9 pikseli. Na pierwszym panelu masz numerację pikseli, a po prawej masz swój stos.

Zaczynasz od piksela nr 5. i przesuwasz piksele 2, 4, 6 i 8 na stosie. Następnie wyłączamy piksel 2 i wciskamy 1 i 3. W następnym kroku wybieramy 1 i wciskamy 2 i 4 (znowu!). Następnie możesz wziąć 2 i zdać sobie sprawę, że już dostał nowy kolor, kiedy został popchnięty. (Trochę późno, ale lepiej późno niż wcale) jednak: pixel no. 4 jest tam dwa razy i zapamiętał stary kolor dwukrotnie. Więc weź piksel nr 4 i pokoloruj go.

Po kilku krokach masz wypełnione zdjęcie, a niektóre przedmioty na stosie. Ponieważ stara wartość koloru jest nadal przechowywana w tych elementach, są one liczone ponownie.

Chociaż mogę mieć nieprawidłową kolejność w stosie, punkt pozostaje ważny.

rozwiązanie problemu: Szybkie i brudne (bo to wciąż nieefektywne)

if (image.GetPixel(popped.x, popped.y) == oldColor) 

liczy pikseli tylko jeśli obecny kolor jest źle, nie pamiętał kolor.

Zalecane: Sprawdź swoje piksele, czy potrzebują farbowania przed wciśnięciem ich na stos.

Answer 2

Jeśli wszystkie Pixel ma zawierać kolor przekazany do swojego konstruktora, nie będzie aktualizować kolor po wypełnieniu piksela, dlatego może zwiększyć ctr więcej niż raz na piksel.

Jeśli zmienisz Pixel, aby umieścić wskaźnik na obrazie w jego konstruktorze, możesz ponownie odczytać kolor (np. Uczynić kolor a uzyskać właściwość, która odczytuje bieżący kolor) lub śledzić współrzędne już wypełnione i nie pchnij je po raz drugi.

[Edytuj]

W przypadku nie było to oczywiste od przyjętego odpowiedź getPixel zwraca Kolor - typ wartości. Pomyśl o tym jako o int, które koduje wartość RGB piksela w tym czasie.

Jeśli chcesz szybko wykonać wypełnienie, wyszukaj przykład Graphics.FloodFill.

Jeśli chcesz osiągnąć cel, zaleciłbym skopiowanie danych obrazu do tablicy w celu przetworzenia i z powrotem - większość klasycznych algorytmów graficznych nie jest zbyt zabawna przy użyciu GetPixel().