Algoritmo di riempimento del poligono
Polygon è un elenco ordinato di vertici come mostrato nella figura seguente. Per riempire poligoni con colori particolari, è necessario determinare i pixel che cadono sul bordo del poligono e quelli che cadono all'interno del poligono. In questo capitolo vedremo come riempire i poligoni usando tecniche differenti.
Algoritmo della linea di scansione
Questo algoritmo funziona intersecando la linea di scansione con i bordi del poligono e riempie il poligono tra coppie di intersezioni. I passaggi seguenti illustrano come funziona questo algoritmo.
Step 1 - Trova Ymin e Ymax dal poligono dato.
Step 2- ScanLine si interseca con ogni bordo del poligono da Ymin a Ymax. Assegna un nome a ciascun punto di intersezione del poligono. Secondo la figura mostrata sopra, sono denominati p0, p1, p2, p3.
Step 3 - Ordina il punto di intersezione nell'ordine crescente della coordinata X cioè (p0, p1), (p1, p2) e (p2, p3).
Step 4 - Riempi tutte quelle coppie di coordinate che si trovano all'interno di poligoni e ignora le coppie alternative.
Algoritmo Flood Fill
A volte ci imbattiamo in un oggetto in cui vogliamo riempire l'area e il suo confine con colori diversi. Possiamo dipingere tali oggetti con un colore interno specificato invece di cercare un colore di contorno particolare come nell'algoritmo di riempimento del contorno.
Invece di fare affidamento sul contorno dell'oggetto, si basa sul colore di riempimento. In altre parole, sostituisce il colore interno dell'oggetto con il colore di riempimento. Quando non esistono più pixel del colore interno originale, l'algoritmo è completato.
Ancora una volta, questo algoritmo si basa sul metodo Four-connect o Eight-connect per riempire i pixel. Ma invece di cercare il colore del contorno, cerca tutti i pixel adiacenti che fanno parte dell'interno.
Algoritmo di riempimento del confine
L'algoritmo di riempimento del confine funziona come il suo nome. Questo algoritmo seleziona un punto all'interno di un oggetto e inizia a riempirsi fino a quando non raggiunge il confine dell'oggetto. Il colore del contorno e il colore che riempiamo dovrebbero essere diversi affinché questo algoritmo funzioni.
In questo algoritmo, assumiamo che il colore del contorno sia lo stesso per l'intero oggetto. L'algoritmo di riempimento del contorno può essere implementato da 4 pixel collegati o 8 pixel collegati.
4-Connected Polygon
In questa tecnica vengono utilizzati 4 pixel collegati come mostrato in figura. Mettiamo i pixel sopra, sotto, a destra e a sinistra dei pixel attuali e questo processo continuerà fino a quando non troviamo un bordo con un colore diverso.
Algoritmo
Step 1 - Inizializza il valore di seed point (seedx, seedy), fcolor e dcol.
Step 2 - Definisci i valori limite del poligono.
Step 3 - Controlla se il punto di partenza corrente è del colore predefinito, quindi ripeti i passaggi 4 e 5 fino a raggiungere i pixel di confine.
If getpixel(x, y) = dcol then repeat step 4 and 5Step 4 - Cambia il colore predefinito con il colore di riempimento nel punto di partenza.
setPixel(seedx, seedy, fcol)Step 5 - Seguire ricorsivamente la procedura con quattro punti di vicinato.
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)Step 6 - Esci
C'è un problema con questa tecnica. Considera il caso come mostrato di seguito in cui abbiamo cercato di riempire l'intera regione. L'immagine è riempita solo parzialmente. In questi casi, non è possibile utilizzare la tecnica dei 4 pixel collegati.
8-Connected Polygon
In questa tecnica vengono utilizzati 8 pixel collegati come mostrato in figura. Stiamo mettendo i pixel sopra, sotto, sul lato destro e sinistro dei pixel attuali come stavamo facendo nella tecnica a 4 connessioni.
Oltre a questo, stiamo anche mettendo i pixel in diagonale in modo che l'intera area del pixel corrente sia coperta. Questo processo continuerà fino a quando non troviamo un confine con un colore diverso.
Algoritmo
Step 1 - Inizializza il valore di seed point (seedx, seedy), fcolor e dcol.
Step 2 - Definisci i valori limite del poligono.
Step 3 - Controlla se il punto di partenza corrente è del colore predefinito, quindi ripeti i passaggi 4 e 5 fino a raggiungere i pixel di confine
If getpixel(x,y) = dcol then repeat step 4 and 5Step 4 - Cambia il colore predefinito con il colore di riempimento nel punto di partenza.
setPixel(seedx, seedy, fcol)Step 5 - Seguire ricorsivamente la procedura con quattro punti di vicinato
FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)Step 6 - Esci
La tecnica dei pixel collegati a 4 non è riuscita a riempire l'area come indicato nella figura seguente, cosa che non avverrà con la tecnica dei pixel collegati a 8.
Test interno-esterno
Questo metodo è noto anche come counting number method. Durante il riempimento di un oggetto, spesso abbiamo bisogno di identificare se un punto particolare si trova all'interno o all'esterno dell'oggetto. Ci sono due metodi con cui possiamo identificare se un punto particolare è all'interno di un oggetto o all'esterno.
- Regola dispari-pari
- Regola del numero di avvolgimento diverso da zero
Regola dispari-pari
In questa tecnica, conteremo il bordo che attraversa la linea da qualsiasi punto (x, y) all'infinito. Se il numero di interazioni è dispari, il punto (x, y) è un punto interno; e se il numero di interazioni è pari, il punto (x, y) è un punto esterno. L'esempio seguente illustra questo concetto.
Dalla figura sopra, possiamo vedere che dal punto (x, y), il numero di punti di interazione sul lato sinistro è 5 e sul lato destro è 3. Da entrambe le estremità, il numero di punti di interazione è dispari, quindi il punto è considerato all'interno dell'oggetto.
Regola del numero di avvolgimento diverso da zero
Questo metodo viene utilizzato anche con i poligoni semplici per verificare che il punto specificato sia interno o meno. Può essere capito semplicemente con l'aiuto di uno spillo e un elastico. Fissare il perno su uno dei bordi del poligono e legare l'elastico in esso, quindi allungare l'elastico lungo i bordi del poligono.
Quando tutti i bordi del poligono sono coperti dall'elastico, controlla il perno che è stato fissato nel punto da testare. Se troviamo almeno un vento nel punto consideralo all'interno del poligono, altrimenti possiamo dire che il punto non è all'interno del poligono.
In un altro metodo alternativo, date le direzioni a tutti i bordi del poligono. Disegna una linea di scansione dal punto da testare verso l'estrema sinistra della direzione X.
Assegna il valore 1 a tutti i bordi che stanno andando verso l'alto e tutti gli altri -1 come valori di direzione.
Verificare i valori della direzione del bordo da cui passa la linea di scansione e sommarli.
Se la somma totale di questo valore di direzione è diversa da zero, questo punto da verificare è un interior point, altrimenti è un file exterior point.
Nella figura sopra, sommiamo i valori di direzione da cui passa la linea di scansione, quindi il totale è 1 - 1 + 1 = 1; che è diverso da zero. Quindi si dice che il punto sia un punto interiore.