Problem

Przypuśćmy, że mam matrycę 2D, z pewnymi losowymi liczbami całkowitymi są albo 0 lub 1. Jak mogę wypełnić ciągły region w mojej tablicy?

Algorytm ten można szczególnie być używany w przetwarzaniu obrazu, aby wypełnić kolor z innym kolorem w zamkniętym regionie, jak narzędzie do malowania.

Przykład

Załóżmy, że moja tablica to:

1 0 1 1 1 1 0
0 0 1 1 1 1 1
0 0 0 1 1 1 1
0 1 0 0 0 1 1
0 0 0 1 1 1 1

Chcę wypełnić region 1 s w prawym górnym rogu z czymś innym jak 8. Jak to wdrożyć? Znam wskaźniki jakiegokolwiek 1 w tym regionie, a ja mam wskaźniki dowolnej z 1 s.

Po wypełnieniu 8 s, tablica powinna wyglądać tak:

1 0 8 8 8 8 0
0 0 8 8 8 8 8
0 0 0 8 8 8 8
0 1 0 0 0 8 8
0 0 0 8 8 8 8 

Moje wysiłki:

Wypróbowałem następujące metody:

  • Przechodząc przez każdy element w tablicy, sprawdzając, czy jest 1, zastępując go za pomocą 8. Najwyraźniej nie działa, ponieważ po prostu zastąpił wszystkie 1 s z 8 s. Nawet 1 s poza regionem przekonwertowano na 8 s.
  • Korzystanie z koordynatów względnych, sprawdzanie 1 s, i zastąpienie za pomocą 8 s dla początkowymi indeksów podanych. Krótko mówiąc, zastępując wszystkich sąsiadów, których wartości są 1 za pomocą 8. To również nie działało, ponieważ zastąpiła tylko najbliższych 8 sąsiadów i nie wypełnił regionu, jak chciałam.
4
Soumitra Shewale 13 styczeń 2020, 11:49

1 odpowiedź

Najlepsza odpowiedź

Voila! Odpowiedź kłamała w rekurencji:

Funkcja zajmuje twoją tablicę jako arr, a współrzędne (lub indeksy) 1 Wiesz w postaci krotki (x, y) jako argumentów.

Korzystając z koordynatów względnych, nazywamy funkcję Flood_Fill na każdym z nich:

function flood_fill(arr, (x, y))
    # check every element in the neighborhood of the element at (x, y) in arr
    for x_off in -1:1
        for y_off in -1:1
            # put the next part in a try-catch block so that if any index
            # is outside the array, we move on to the next element.
            try
                # if the element is a 1, change it to an 8 and call flood_fill 
                # on it so it fills it's neighbors
                if arr[x + x_off, y + y_off] == 1
                    arr[x + x_off, y + y_off] = 8
                    flood_fill(arr, (x + x_off, y + y_off))
                end
            catch
                continue
            end
        end
    end
end
4
Soumitra Shewale 13 styczeń 2020, 08:49