Elárasztásos kitöltés

Az elárasztásos kitöltés, egy algoritmus, amely meghatározza az adott csomóponthoz kapcsolódó területet egy többdimenziós tömbben . Ezen algoritmust alkalmazza például a Paint az ún. „vödör” kitöltés eszközként (kitöltés színnel), hogy a kapcsolódó hasonlóan színezett területeket feltöltse különböző színnel. Játékok esetében is használatos mint például a Go és Aknakereső amelynél megállapítja mely részek lettek eltávolítva.

Az algoritmus[szerkesztés]

Az elárasztásos kitöltés algoritmusa három paramétert vesz igénybe: a kezdő csomópontot, egy célszínt és egy csereszínt. Az algoritmus megkeresi a tömb összes csomópontját, amelyek a cél szín útvonalával kapcsolódnak a kezdő csomóponthoz, és megváltoztatja azokat a csere színre. Az elárasztásos kitöltés algoritmusa sokféle módon felépíthető, ám ezek mindegyike egy sor vagy a verem adatszerkezetét használja fel, explicit vagy implicit módon.

Attól függően, hogy figyelembe vesszük a csomópontokat, amelyek érintkeznek a csatlakoztatott sarkokban, vagy sem, két változatunk van: nyolc és négy irányú.

Verem alapú rekurzív megvalósítás (négyirányú)[szerkesztés]

Egy implicit módon verem alapú (rekurzív) elárasztásos kitöltés megvalósítása (kétdimenziós tömb esetén) a következő:

 Elárasztásos kitöltés (csomópont, cél szín, csere szín):
 1. Ha (if) a célszín megegyezik a csere színével, visszatérés.
 2. Egyébként, ha (else if) a csomópont színe nem egyezik meg a célszínnel, visszatérés.
 3. Különben (else) állítsa be a csomópont színét a csere színre.
 4. Végezz Elárasztásos kitöltés (egy lépés a csomóponttól délre, célszín, csere szín).
   Végezz Elárasztásos kitöltés (egy lépés a csomóponttól északra, célszín, csere szín).
   Végezz Elárasztásos kitöltés (egy lépés nyugatra a csomóponttól, célszín, csere szín).
   Végezz Elárasztásos kitöltés (egy lépés keletre a csomóponttól,       célszín, csere szín).
 5. Visszatérés.

Bár könnyen érthető, a fentebb használt algoritmus megvalósítása kivitelezhetetlen olyan programozási nyelveken és környezetekben ahol a verem mérete szigorúan korlátozott. (pl. Java kisalkalmazások).

Alternatív megvalósítások[szerkesztés]

Az alábbiakban látható egy kifejezetten soron alapuló megvalósítás pszeudokódja az ún. "Erdő Tűz" (Forest Fire) algoritmus.^[1] Ez hasonló az egyszerű rekurzív megoldáshoz, azzal a különbséggel, hogy a rekurzív hívások helyett a csomópontokat egy felhasználási sorra állítja:

 Elárasztásos kitöltés (csomópont, célszín, csere szín):
 1. Ha a célszín megegyezik a csere színével, visszatérés.
 2. Ha a csomópont színe nem egyezik meg a célszinttel, visszatérés.
 3. Állítsa be a csomópont színét csere színre.
 4. Állítsa Q-t az üres sorra.
 5. Adja hozzá a csomópontot a Q végéhez.
 6. Amíg a Q nem üres:
 7. Állítsa n- et a Q első elemével egyenlőre.
 8. Távolítsa el az első elemet a Q-ból.
 9. Ha az n-től nyugatra eső csomópont színe a célszín,
       állítsa a csomópont színét a csere színre, és adja hozzá ezen csomópontot a Q végéhez.
 10. Ha az n-től keletre eső csomópont színe a célszín,
       állítsa a csomópont színét a csere színre, és adja hozzá ezen csomópontot a Q végéhez.
 11. Ha az n-től északra található csomópont színe a célszín,
       állítsa a csomópont színét a csere színre, és adja hozzá ezen csomópontot a Q végéhez.
 12. Ha az n-től délre található csomópont színe a célszín,
       állítsa a csomópont színét a csere színre, és adja hozzá ezen csomópontot a Q végéhez.
 13. Folytassa a hurkot (ciklust), amíg a Q nem üres.
 14. Visszatérés.

Téglalap alakú területek kitöltésére szolgáló gyakorlati megvalósítások használhatnak egy hurkot a nyugati és a keleti irányba, optimalizáció céljából, hogy elkerüljék a verem vagy a sorkezelés túlterhelését:

 Elárasztásos kitöltés (csomópont, cél szín, csere szín):
 1. Ha a célszín megegyezik a csere színével, visszatérés.
 2. Ha a csomópont színe nem egyezik meg a célszínnel, visszatérés.
 3. Állítsa Q-t üres sorra.
 4. Adja hozzá a csomópontot a Q-hoz.
 5. A Q minden N elemére:
 6. Állítsa w és e értékét N-re.
 7. Mozgassa w nyugatra, amíg a csomópont színe a w-től nyugatra nem egyezik meg a cél színnel.
 8. Mozgassa e keletre, amíg a csomópont színe az e-től keletre nem egyezik meg cél színnel.
 9. Minden n csomópontra w és e között:
10. Állítsa az n színét a csere színre.
11. Ha az n- től északra található csomópont színe célszín, adja hozzá a csomópontot a Q-hoz .
12. Ha az n- től délre található csomópont színe célszín, adja hozzá a csomópontot a Q-hoz .
13. Folytassa a hurkot (ciklust), amíg a Q nem üres.
14. Visszatérés.

Az algoritmus megváltoztatásával használhatunk egy további tömböt arra, hogy tárolni tudjuk a terület alakját amely lehetővé teszi azt, hogy elfedjük az ún. "zavaros” elárasztásos kitöltést, ahol egy elem egy meghatározott küszöbértékig különbözhet a forrásjeltől. Ennek a kiegészítő tömbnek az alfa-csatornaként történő használata lehetővé teszi, hogy a kitöltött részek szélei valamely szinten beolvadjanak a nem kitöltött régióval.

Rögzített memória alapú metódus (jobb oldali kitöltési módszer)[szerkesztés]

Létezik egy olyan módszer, mely lényegében nem használ memóriát négy összekapcsolt régió számára, amely úgy tesz, mintha festő lenne, aki megpróbálja festeni a régiót anélkül, hogy magát egy sarokba festené. Ezen módszer a labirintusok megoldására is alkalmas. Az elsődleges határvonalat alkotó négy pixelt megvizsgáljuk, hogy megtudjuk, milyen lépéseket kell tenni. A festő a következő feltételek egyikében találhatja magát:

A határ képkockái közül mind a négy ki van töltve.
A határ pixelek közül három ki van töltve.
A határ képkockái közül kettő van kitöltve.
Egy képkocka van kitöltve a határok közül.
Egy határ képkocka sincs kitöltve.

Ha utat vagy határt kell követni, akkor a jobb oldali szabályt kell használni. A festő követi a régiót úgy, hogy jobb kezét a falhoz pozicionálja (a régió határa), és a régió széle körül halad, anélkül, hogy a kezét eltávolítaná.

1. Azon eset amelyben a festő megfesti (kitölti) a képkockát, amelyen a festő áll, és leállítja az algoritmust.

2. Ezen esetben létezik a területről kivezető út. Fesse le azt a képkockát, amelyen a festő áll, és induljon a nyitott (elérhető) útvonal irányába.

3. Itt a két határ pixelei meghatároznak egy utat, amelynél ha az aktuális képkockát festettük, akkor az megakadályozhat abban, hogy bármikor visszatérjünk az útvonal másik oldalára. Szükségünk van egy "jelre", hogy meghatározzuk, hol vagyunk, és milyen irányba haladunk, hogy megnézhessük, vissza térünk-e valaha ugyanahhoz a képkockához. Ha már létrehoztunk egy ilyen "jelet", akkor megőrizzük ezen jelölést, és a jobb oldali szabályt követve mozgunk a következő képkockára.

A jelölést az első 2 képpontos határnál használják, hogy emlékezzenek arra, hogy hol kezdődött az átjárató, és milyen irányban haladt a festő (painter). Ha újra találkozunk a jelöléssel, és a festő ugyanazon irányba halad, akkor a festő tudja, hogy biztonságos a jelöléssel levő négyzet festése, és a haladás folytatása ugyanazon irányban. Ennek oka az, hogy (valamilyen ismeretlen úton keresztül) a jel másik oldalán lévő pixeleket a jövőben elérhetik és megfesthetik. A jelölést eltávolítják későbbi felhasználás céljából.

Ha a festő találkozik a jelöléssel, de eltérő irányba halad, akkor valamilyen hurok történt, amely miatt a festőt visszatért a jelöléshez. Ezt a hurkot meg kell szüntetni. A jelölést felveszik, és a festő ezután a jelölés által korábban jelzett irányba halad a baloldali szabály segítségével a határhoz (hasonlóan a jobbkezes szabályhoz, de a festő bal kezét használva). Ez addig folytatódik, amíg meg nem találják a kereszteződést (három vagy több nyitott határponttal). A bal oldali szabály alkalmazásával a festő most egy egyszerű átjárót keres (két határképpont alapján). Miután megtalálta ezt a két képpontos határútvonalat, ezen pixel kitöltésre kerll. Ez megszakítja a hurkot, és lehetővé teszi az algoritmus folytatását.

4. esetnél ellenőriznünk kell az ellentétes 8 csatlakoztatott sarkot, hogy ki vannak-e töltve vagy sem. Ha az egyik vagy mindkettő ki van töltve, akkor ez több irányú kereszteződést hoz létre, és nem tölthető ki. Ha mindkettő üres, akkor az aktuális pixel ki lehet tölteni, és a festő a jobb oldali szabályt követve mozoghat.

Az algoritmus többlet futási idővel spórol memóriát. Az egyszerű alakzatoknál nagyon hatékony. Azonban, ha az alakzat bonyolult és több tulajdonsággal rendelkező, az algoritmus sok időt tölt a régió széleinek nyomon követésével annak biztosítása érdekében, hogy mindegyik kitölthető legyen.

Ezen algoritmus először 1981-ben vált elérhetővé a Vicom Systems Inc. által gyártott Vicom képalkotási rendszerben. A klasszikus rekurzív elárasztásos kitöltés algoritmusa is elérhető volt ezen képalkotási módszerben.

Pszeudókód[szerkesztés]

Alább látható egy optimális, rögzített-memóriájú elárasztásos kitöltés algoritmus megvalósítás, strukturált magyar nyelven:

A változók: jelenlegi, jel és jel2 mindegyike pixelkoordinátákat vagy null értéket tartalmaz.

 MEGJEGYZÉS: Ha a "jel" nullára van állítva, ne törölje annak korábbi koordináta értékét.
      Meg kell tartani ezen koordinátákat, hogy szükség esetén visszahívhatóak legyenek.

A jelenlegi_irany, a jel_irany és a jel2-irany mindegyike egy irány értékkel rendelkezik (balra, jobbra, fel vagy le). A "visszalepes", és a "hurok_keres" mindkettő logikai értékkel rendelkezik és egész számnak számít.

Az algoritmus:

(MEGJEGYZÉS: Az összes irány (elöl, hátul, balra, jobbra) relatív a "jelenlegi-irany"-hoz.)

Állítsa "jelenlegi"-t a kezdő pixelre
Állítsa "jelenlegi-irany"-t az alapértelmezett irányba
Törölje a "jel" és a "jel2" értékét (állítsa az értékeket null-ra)
Állítsa a "visszalepes"-t és a "hurok_keres"-t hamisra

Ciklus amíg elől levő pixel üres //Adott útvonalon jelen pixelt követő
  lépj előre
CiklusVége

ugrás a KEZDET-re

BELSŐ CIKLUS
  lépés előre
  Ha jobb-pixel üres akkor
    Ha 'visszalepes' igaz és 'hurok_keres' hamis és az elülső pixel vagy bal oldali pixel üres akkor
      állítsa a 'hurok_keres'-t igazra
    HaVége
    jobbra pozícionálás
FESTÉS:
    lépés előre
  HaVége
KEZDET:
  Állíts megszamlalas-t (count) a nem átlósan szomszédos kitöltött pixelek számára (első / hátsó / bal / jobb)
  Ha megszamlalas nem 4 akkor
    csináld
      jobbra pozícionálás
    Amíg előrébb levő képpont üres //Adott – jelenlegi ponthoz képest
    csináld
      balra pozícionálás
    Amíg előrébb levő pixel kitöltött
  HaVége
  Kapcsoló megszamlalas
    1. eset
      Ha 'visszalepes' igaz akkor
        állítsa a 'hurok_keres' igazra
      Különben, Ha 'hurok_keres' igaz akkor
        Ha jel null, akkor
          állítsa vissza a "jel"-t
        HaVége
      Különben, ha bal első pixel és bal-hátsó-képpont üres akkor
        törölje a 'jel' értékét
        töltse ki a 'jelenlegi'-t
        ugrás a FESTÉS-hez
      HaVége
    EsetVége
    2. eset
      Ha hátsó pixel ki van töltve akkor
        Ha első-bal pixel nincs kitöltve akkor
          törölje a "jel" értékét
          töltse ki a "jelenlegi"-t
          ugrás a FESTÉS-hez
        HaVége
      Különben, ha "jel" nincs beállítva akkor
        állítsa a "jel"-et a "jelen"-re
        állítsa a "jel_irany"-t "jelenlegi_irany"-ra
        törölje a "jel2" értékét
        állítsa a "hurok_keres" és a "visszalepes"-t hamis értékre
      Különben
        Ha "jel2"-nek nincs érték adva akkor
          Ha "jelenlegi" a "jel"-nél van akkor
            Ha "jelenlegi_irany" ugyanaz, mint a "jel_irany" akkor
              törölje a "jel" értékét"
              megfordulas
              töltse ki a "jelen"-t
              ugrás a "FESTÉS"-hez
            Különben
              állítsa igazra a "visszalepes"-t
              állítsa a "hurok_keres"-t hamisra
              állítsa a "jelenlegi_irany"-t "jel_irany"-ra
            HaVége
          Különben, ha "hurok_keres" igaz akkor
            állítsa a "jel2"-t a "jelenlegi"-re
            állítsa a "jel2_irany" értékét "jelenlegi_irany"-ra
          HaVége
        Különben
          Ha "jelenlegi" a "jel"-nél van akkor
            állítsa a "jelenlegi"-t a "jel2"-re
            állítsa a "jelenlegi_irany"-t "jel2_irany"-ra
            törölje a "jel" és "jel2" értékét
            állítsa a "visszalepes"-t hamisra
            megfordulas
            töltse ki a "jelenlegi"-t
            ugrás a "FESTÉS"-hez
          Különben, ha a "jelenlegi" a "jel2"-nél van akkor
            állítsa a "jel"-t a "jelenlegi" értékére
            állítsa a "jelenlegi_irany"-t és a "jel_irany"-t a "jel2_irany"-ra
            törölje a "jel2" értékét
          HaVége
        HaVége
      HaVége
    EsetVége
    3. eset
      törölje a "jel" értékét
      töltse ki a "jelenlegi"-t
      ugrás a "FESTÉS"-hez
    EsetVége
    4. eset
      töltse ki a "jelenlegi"-t
      Kész
    EsetVége
  KapcsolóVége
CIKLUS VÉGE

Letapogatásos kitöltés[szerkesztés]

Az algoritmus a sorok kitöltésével felgyorsítható. Ahelyett, hogy az egyes potenciális jövőbeli képpont-koordinátákat a verembe tolná, megvizsgálja a szomszédos vonalakat (az előzőt és a következőt), hogy megtalálja a szomszédos szegmenseket, amelyek egy jövőbeli áthaladással kitölthetők; a vonalszakasz koordinátáit (akár elejét, akár végét) a veremre tolják. A legtöbb esetben ez a letapogatási algoritmus legalább egy nagyságrenddel gyorsabb, mint az egy pixelre eső.

Hatékonyság : minden pixelt egyszer lesz ellenőrizve.

Vektor alapú megvalósítások[szerkesztés]

Az Inkscape 0.46-os verziója tartalmaz egy "vödör" kitöltő eszközt, amely a szokásos bitmap műveletekhez hasonló kimenetet ad és valójában egy ilyen használatával: a vászon megjelenítésre kerül, az elárasztásos kitöltés művelet végrehajtódik a kiválasztott területen, és az eredmény visszavezethető egy útvonalra. A peremérték-probléma elgondolását használja.

Nagy méretű viselkedési forma[szerkesztés]

Négy irányú elárasztásos kitöltés, sort használva a tároláshoz.

Négy irányú elárasztásos kitöltés, vermet használva a tároláshoz.

Az elsődleges módszer az elárasztásos kitöltés vezérlésére adat- vagy folyamatközpontú. Az adatközpontú megközelítés vermet vagy sort is használhat arra, hogy számon tudja tartani a pixeleket melyeket szükséges ellenőrizni. A folyamatközpontú algoritmusnak vermet kell használnia.

A négyirányú elárasztásos kitöltés algoritmusa, amely szomszédsági technikát és sort használ az elemi pixelek tárolása, egy növekedő rombusz alakú kitöltést eredményez.

Hatékonyság : 4 pixel ellenőrzése történik minden kitöltött képpontnál (8 egy 8-irányú kitöltésnél).

Egy négyirányú elárasztásos kitöltés algoritmus, amely szomszédsági technikát és vermet használ, az elemi pixelek tárolására az lineáris kitöltést eredményez és ún. "később kitöltődő rés" viselkedéssel rendelkezik. Ez a megközelítés különösen a régebbi 8 bites számítógépes játékokban tapasztalhatóak, amelyeket például Grafikus Kalandkészítő (GAC) segítségével hoztak létre.

Hatékonyság : 4 pixel ellenőrzése történik minden kitöltött képpontnál (8 egy 8-irányú kitöltésnél).

Lásd még[szerkesztés]

Források[szerkesztés]

Scanline Polygon kitöltés – Javascript megvalósítások, Guilherme Polo
Minta implementációk rekurzív és nem rekurzív, klasszikus és vízszintes elárasztásos kitöltésről, Lode Vandevenne
Gyors elárasztásos kitöltés megvalósítások, Emanuele Feronato
QuickFill: Egy hatékony elárasztásos kitöltés algoritmus, John R. Shaw
FloodSpill: nyílt forráskódú elárasztásos kitöltés algoritmus C#-hoz, Paweł Ślusarczyk

Jegyzetek[szerkesztés]

↑ Torbert, Shane. Applied Computer Science, 2nd, Springer, 158. o.. DOI: 10.1007/978-3-319-30866-1 (2016). ISBN 978-3-319-30864-7

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Flood Fill című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

[1] Torbert, Shane. Applied Computer Science, 2nd, Springer, 158. o.. DOI: 10.1007/978-3-319-30866-1 (2016). ISBN 978-3-319-30864-7

[1]