Homework06 - program03

program03.py

'''Scrivere una funzione fill(img_in, boundaries, pp_cc, img_out) che prende
in input i seguenti argomenti:
- img_in: file che contiene un'immagine in formato PNG, leggibile con la
  funzione load() del modulo image.
- boundaries: un insieme di tipo set di pixel dell'immagine, ognuno specificato
  da una coppia di coordinate (x, y). Come al solito le coordinate crescono
  verso destra e verso il basso e il pixel nell'angolo in alto a sinistra ha
  coordinate (0, 0).
- pp_cc: una lista di coppie (p, c) dove p e' un pixel (cioe' una coppia di
  coordinate) e c e' un colore espresso come tripla (r,g,b).
- img_out: il nome di un file in cui salvare l'immagine risultato.
La funzione per ogni elemento (p, c) della lista pp_cc deve colorare con il
colore c tutti i pixel che sono connessi al pixel p nel grafo di pixel
dell'immagine letta dal file img_in senza pero' attraversare i pixel in
boundaries. Ad esempio, se boundaries consiste di tutti i pixel del contorno
di un cerchio e p e' un pixel all'interno del cerchio, allora la funzione
ricolora con colore c tutti i pixel all'interno del cerchio (esclusi quelli in
boundaries). Infine la funzione salva sul file img_out (tramite la funzione
save() del modulo image) l'immagine modificata.
Per gli esempi vedere grade03.py, i file di input img03_01_in.png,
img03_02_in.png e quelli di output img03_01_check.png, img03_02_check.png,
img03_03_check.png, img03_04_check.png, img03_05_check.png.

AVVERTENZE: non usare caratteri non ASCII, come le lettere accentate;
non usare moduli che non sono nella libreria standard o non sono forniti
nella cartella dell'homework o non sono esplicitamente autorizzati.
'''

import image

ADJACENTS = ((-1,0),(0,1),(1,0),(0,-1))


def color_path(img, start, color, boundaries):
    w, h = len(img[0]), len(img)     # Dimensioni dell'immagine
    sx, sy = start                   # Coordinate del pixel di partenza
    img[sy][sx] = color              # Colora il pixel di partenza con il colore indicato
    visited = set([start])           # Insieme dei pixel visitati (solo quello di partenza all'inizio)
    active = set([start])            # Insieme dei pixel da visitare (si parte dal pixel di partenza ovviamente)
    while active:   # Visita BFS: finche' ci sono pixel "attivi", cioe' i pixel i cui vicini devono essere visitati, la ricerca prosegue
        newactive = set()
        while active:
            x, y = active.pop()
            for dx, dy in ADJACENTS:     # Esamina i 4 pixel adiacenti
                ax, ay = x + dx, y + dy  # Coordinate del pixel adiacente
                if ax < 0 or ax >= w or ay < 0 or ay >= h: continue  # il pixel eccede le dimensioni dell'immagine (cioe' non esiste)
                a = (ax, ay)  # il pixel `a` e' uno dei pixel adiacenti
                if a in visited or a in boundaries: continue  # il pixel e' gia' stato visitato oppure non si puo' attraversare
                visited.add(a)  # il pixel `a` e' stato vistato con successo
                newactive.add(a)  # il pixel `a` viene aggiunto ai pixel "attivi" e i suoi vicini saranno visitati
                img[ay][ax] = color  # colora il pixel del colore specificato
        active = newactive


def fill(img_in, boundaries, pp_cc, img_out):
    img = image.load(img_in)
    for pixel, color in pp_cc:
        # partendo dal pixel `pixel`, colora tutti i pixel adiacenti con il colore `cc`
        # `boundaries` e' un insieme di punti che non si possono attraversare, e che compongono
        # una sorta di "confine"
        color_path(img, pixel, color, boundaries)
    image.save(img_out, img)