# Zárt terület kifestése

Czirkos Zoltán · 2023.01.13.

Zárt terület kifestése: a flood fill és a boundary fill algoritmus

Szinte mindegyik rajzolóprogram tartalmazza a zárt terület kifestése eszközt, amellyel egy összefüggő területet tudunk valamilyen színűre festeni. Angolul meg szoktuk különböztetni a „flood fill” és a „boundary fill” algoritmust, de nagy elvi különbség nincsen a kettő között valójában. Az előbbi egy összefüggő, adott színű területet színez át, vagyis mindig csak ugyanarra a színre lép. Az utóbbi pedig egy körvonal által körbehatárolt területet színez be.

Flood fill: a sárga területről indított kifestés csak a sárga területet színezi át, vagyis csak a megadott színre lép.
Boundary fill: bárhonnan indítjuk a kifestést az alakzat belsejéből, a teljes amőba piros lesz: a határ a feketével jelölt körvonal.

A két algoritmust innentől lényegileg egynek tekintjük, hiszen sejthető, hogy csak valamelyik elágazás feltételében térnek el egymástól: `szín == sárga` az egyik, `szín != fekete` a másik esetben.

A feladat tehát a következő. Adott egy két dimenziós tömb, amelyik egy képet reprezentál. A képen egy adott színnel el van kerítve egy terület – vagyis meg van rajzolva egy alakzat. Színezzük ki ennek az alakzatnak a belsejét! Az alakzat lehet konkáv is, abban az esetben is be kell menni minden zugba!

    z4qqq = [
        list("                               "),
        list("            xx   xx            "),
        list("       xxxx x xxx x xxxx       "),
        list("      xx  x x     x x  xx      "),
        list("    xxx  xx x     x xx  xxx    "),
        list("  xxx    x  x     x  x    xxx  "),
        list("  x      x  x     x  x      x  "),
        list(" xx       xx       xx       xx "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" xx    xx             xx    xx "),
        list("  x   x  x xx     xx x  x   x  "),
        list("  xxx  x x x x   x x x x  xxx  "),
        list("    xx x xxx xx xx xxx x xx    "),
        list("     xxx      x x      xxx     "),
        list("              xxx              "),
        list("                               "),
    ]

A rekurzió nélkül lehetetlennek tűnő feladat rekurzív megoldása végtelenül egyszerű. A függvény először megvizsgálja, hogy olyan pozíciót kapott-e, ahova szabad lépni, és amit ki kell festeni. Ha olyan pozícióról van szó, ami kilóg a képről; vagy nem szóköz van az adott helyen (már ki van festve), akkor egyből vissza is tér. Ha viszont kifestendő a pont, akkor kifesti, és kifesti a szomszédait is. A szomszédoknál ugyanez a feladat: az aktuális pontot kifesteni, és mind a négy irányba megpróbálni menni. Ha a festés ilyen módon végül egy zsákutcában elakad, a függvények visszatérnek – és a próbálkozás megy tovább a másik három lehetséges irányba. Zsákutca pedig a saját maga által kifestett pontok miatt is keletkezhet, hiszen onnantól kezdve, hogy egy pontot kifest az algoritmus, az ugyanolyan falnak számít, mint az eredeti alakzat körvonalai.

A kifestő működése. A videóban minden függvényhívás elején pirosra festi a program az adott helyet; és miután az összes irányból visszatértek a hívott függvények, csak akkor kékre. Ezen is, és a bejelölt útvonalon is látszik az, hogy melyek a befejezetlen, nem teljesen lefutott függvénytörzsek.

    def kifest(kep, x, y):
        if y < 0 or x < 0 or y >= len(kep) or x >= len(kep[0]):
            return
        if kep[y][x] != ' ':
            return
        kep[y][x] = '.'
        kifest(kep, x, y - 1)
        kifest(kep, x, y + 1)
        kifest(kep, x - 1,y )
        kifest(kep, x + 1,y )

    def main():
        z4qqq = [
            list("                               "),
            list("            xx   xx            "),
            list("       xxxx x xxx x xxxx       "),
            list("      xx  x x     x x  xx      "),
            list("    xxx  xx x     x xx  xxx    "),
            list("  xxx    x  x     x  x    xxx  "),
            list("  x      x  x     x  x      x  "),
            list(" xx       xx       xx       xx "),
            list(" x                           x "),
            list(" x                           x "),
            list(" x                           x "),
            list(" x                           x "),
            list(" x                           x "),
            list(" xx    xx             xx    xx "),
            list("  x   x  x xx     xx x  x   x  "),
            list("  xxx  x x x x   x x x x  xxx  "),
            list("    xx x xxx xx xx xxx x xx    "),
            list("     xxx      x x      xxx     "),
            list("              xxx              "),
            list("                               "),
        ]

        kifest(z4qqq, 10, 10);

        for sor in z4qqq:
            print("".join(sor))

    main()