Prednáška 1718

Vyfarbovanie súvislých oblastí

• Uvažujme obrázok pozostávajúci z m krát n štvorčekov (pixelov).
• Farbu každého pixelu zapíšeme do jedného políčka dvojrozmerného poľa s m riadkami a n stĺpcami.
• V našom jednoduchom príklade budeme pracovať iba s piatimi farbami, ktoré budeme reprezentovať číslami 0,...,4 podľa nasledujúceho poľa (napríklad číslo 0 teda reprezentuje bielu farbu):

const char *farby[5] = {"white", "blue", "black", "yellow", "red"};

Napríklad obrázok

tak môže byť reprezentovaný nasledujúcim textovým súborom obsahujúcim najprv rozmery matice (čísla m a n) a za nimi samotné prvky matice:

11 17
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
 0 0 0 1 0 0 0 0 0 2 2 1 2 2 2 2 0
 0 0 0 1 0 0 0 0 0 2 0 1 0 0 0 2 0
 0 2 2 2 2 2 2 2 0 2 2 1 2 2 2 2 0
 0 2 0 1 0 0 0 2 0 0 0 1 0 0 0 0 0
 0 2 0 1 0 0 0 2 0 0 0 1 0 1 1 1 1
 0 2 0 1 1 1 1 2 1 1 1 1 0 1 0 0 1
 0 2 0 0 0 0 0 2 0 0 0 0 0 1 1 1 1
 0 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0

Zameriame sa teraz na nasledujúci problém: používateľ zvolí (zadá na konzolu) súradnice niektorého štvorčeka a cieľom je ofarbiť nejakou farbou (napríklad červenou) celú súvislú oblasť rovnakej farby obsahujúcu daný štvorček. Napríklad pre obrazec vyššie a vstupné súradnice (2,1) (teda štvorček v treťom riadku a druhom stĺpci, keďže matica sa bude indexovať od nuly) by mal byť výstupom nasledujúci obrazec:

Podobný problém je napríklad často potrebné riešiť v rôznych nástrojoch na prácu s grafikou a podobne.

• Jednoduché útvary, napr. obdĺžnik, by sa dali vyfarbiť jednoduchými cyklami, naša súvislá oblasť ale môže mať veľmi zložitý tvar, s mnohými zákrutami, vetveniami, dierami a podobne.
• Pre každé políčko, ktoré prefarbíme, nesmieme zabudnúť skontrolovať všetkých jeho susedov a ak majú rovnakú farbu ako malo pôvodné políčko, tak prefarbiť aj ich, ich susedov, susedov ich susedov atď.
• Toto vieme ľahko zapísať rekurzívne: zafarbíme jedno políčko a potom rekurzívne zafarbujeme celú dosiahnuteľnú oblasť pre každého suseda rovnakej farby, akú malo pôvodne prefarbené políčko.
• Táto podúloha je menšia, lebo aspoň jedno políčko z nej ubudlo prvým prefarbením.

Vyfarbovanie pomocou rekurzívnej funkcie

Nasledujúca rekurzívna funkcia vyfarbi prefarbí políčko so súradnicami (riadok, stlpec) na cieľovú farbu farba a následne sa rekurzívne zavolá pre všetkých susedov tohto políčka, ktoré sú zafarbené pôvodnou farbou prefarbovanej oblasti.

/* Prefarbi súvislú jednofarebnú oblasť obsahujúcu 
 * pozíciu (riadok,stlpec) na farbu s číslom farba. */
void vyfarbi(int **a, int m, int n, 
             int riadok, int stlpec, int farba) {
    int staraFarba = a[riadok][stlpec];
    if (staraFarba == farba) {
        return;
    }
    a[riadok][stlpec] = farba;
    if (riadok - 1 >= 0 
        && a[riadok - 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok - 1, stlpec, farba);
    }
    if (riadok + 1 < m 
        && a[riadok + 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok + 1, stlpec, farba);
    }
    if (stlpec - 1 >= 0 
        && a[riadok][stlpec - 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec - 1, farba);
    }
    if (stlpec + 1 < n 
        && a[riadok][stlpec + 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec + 1, farba);
    }
}

Proces vyfarbovania môžeme animovať pomocou našej knižnice SVGdraw

• Výsledná animácia

V animácii okrem zmeny farby štvorčeka meníme aj farbu jeho rámčeka: pri zavolaní rekurzie sa zmení na hnedú a po skončení spracovania štvorčeka aj jeho susedov sa zmení na sivú. Hnedé sú teda vždy rámčeky štvorčekov uložené na zásobníku volaní.

Program s animáciou

• Program na vyfarbovanie súvislých oblastí obsahuje funkcie na inicializáciu matice, jej načítanie zo súboru, vykresľovanie jednotlivých štvorčekov a celej matice, ako aj uvoľnenie pamäte. Všetky tieto funkcie pracujú podobne ako pri príklade s výškovou mapou z prednášky 13.
• Funkcia main načíta maticu zo súboru vstup.txt a animáciu uloží do súboru matica.svg.
• Do rekurzívnej funkcie pridáme volania funkcie vykresliStvorcek, ktoré aktuálny štvorček v obrázku prekreslia novou farbou a menia aj farbu rámčeka. Za ňou vždy zavoláme funkciu drawing.wait, ktorá animáciu pozdrží, aby sme zmeny stihli na obrázku sledovať.

#include "SVGdraw.h"
#include <cstdio>
#include <cassert>

const char *farby[5] = {"white", "blue", "black", "yellow", "red"}; 

const int stvorcek = 40;    // velkost stvorceka v pixeloch
const int hrubkaCiary = 2;  // hrubka ciary v pixeloch
const double pauza = 0.3;   // pauza po kazdom kroku vyfarbovania v sekundach

/* Vytvori maticu s n riadkami a m stlpcami. */
int **vytvorMaticu(int m, int n) {
    int **a;
    a = new int *[m];
    for (int i = 0; i < m; i++) {
        a[i] = new int[n];
    }
    return a;
}

/* Uvolni pamat matice a s n riadkami a m stlpcami. */
void zmazMaticu(int **a, int m) {
    for (int i = 0; i < m; i++) {
        delete[] a[i];
    }
    delete[] a;
}

/* Vykresli stvorcek v riadku i a stlpci j 
   s farbou vyplne farba a farbou ciary farbaCiary. */
void vykresliStvorcek(int i, int j, 
                      const char * farba, 
                      const char * farbaCiary, 
                      SVGdraw &drawing) {
    drawing.setLineColor(farbaCiary);
    drawing.setLineWidth(hrubkaCiary);
    drawing.setFillColor(farba);
    drawing.drawRectangle(j * stvorcek, i * stvorcek, 
                          stvorcek, stvorcek);
}

/* Vykresli maticu a s n riadkami a m stlpcami. */
void vykresliMaticu(int **a, int m, int n, SVGdraw &drawing) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            vykresliStvorcek(i, j, farby[a[i][j]], "lightgray", drawing);
        }
    }
}

/* Nacita z textoveho suboru, na ktory ukazuje fr, 
   prvky matice a s n riadkami a m stlpcami. */
void nacitajMaticu(FILE *fr, int **a, int m, int n) {
    assert(fr != NULL);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            fscanf(fr, "%d", &a[i][j]);
        }
    }
}

/* Prefarbi suvislu jednofarebnu oblast obsahujucu 
 * poziciu (riadok,stlpec) na farbu s cislom farba. */
void vyfarbi(int **a, int m, int n, 
             int riadok, int stlpec, int farba,
             SVGdraw &drawing) {
    int staraFarba = a[riadok][stlpec];
    if (staraFarba == farba) {
        return;
    }
    a[riadok][stlpec] = farba;
    vykresliStvorcek(riadok, stlpec, farby[farba], 
                     "brown", drawing);
    drawing.wait(pauza);
    if (riadok - 1 >= 0 && a[riadok - 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok - 1, stlpec, farba, drawing);
    }
    if (riadok + 1 < m && a[riadok + 1][stlpec] == staraFarba) {
        vyfarbi(a, m, n, riadok + 1, stlpec, farba, drawing);
    }
    if (stlpec - 1 >= 0 && a[riadok][stlpec - 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec - 1, farba, drawing);
    }
    if (stlpec + 1 < n && a[riadok][stlpec + 1] == staraFarba) {
        vyfarbi(a, m, n, riadok, stlpec + 1, farba, drawing);
    }
    vykresliStvorcek(riadok, stlpec, farby[farba], 
                     "lightgray", drawing);
    drawing.wait(pauza);
} 

int main() {
    FILE *fr = fopen("vstup.txt", "r");
    assert(fr != NULL);

    // nacitanie rozmerov matice
    int m, n;
    fscanf(fr, "%d %d", &m, &n);  
    // vytvorenie matice a nacitanie jej prvkov  
    int **a = vytvorMaticu(m, n);
    nacitajMaticu(fr, a, m, n);         
    fclose(fr);
        
    SVGdraw drawing(n * stvorcek, m * stvorcek, "matica.svg");
    vykresliMaticu(a, m, n, drawing);

    // nacitanie suradnic pociatocneho stvorceka 
    int riadok, stlpec;
    scanf("%d", &riadok);
    scanf("%d", &stlpec);

    vyfarbi(a, m, n, riadok, stlpec, 4, drawing);

    drawing.finish();
    zmazMaticu(a, m);
}