Newsgroup: it.comp.lang.c++
Titolo: Riempimento triangoli 2

Scusate, non sono stato preciso in "Riempimento triangoli", lo sarò ora. Il
sistema operativo è il DOS, e il compilatore il Turbo C++ 3.0, ma nel mio
caso non sono fondamentali perchè mi sono creato una modesta libreria
grafica personale, dove per ora figurano solo (oltre alle funzioni di
inizializzazione e page-swapping) la funzione line(x1, y1, x2, y2, colore) e
point(x, y, colore). Tramite queste vorrei riempire un triangolo (anzi: per
chi avesse tempo da perdere e conoscenze in materia, mi farebbe comodo
riempire anche poligoni in generale, convessi e non).
                                                                Grazie di
nuovo
Gorcamorca

Se il tuo problema e' piu' generale, e cioe' vuoi fare un "fill" di un'area
chiusa gia' disegnata sullo schermo, hai bisogno di una funzione che legga
il colore di un pixel perche' devi lavorare direttamente sulla pagina
grafica.
Se invece vuoi riempire un triangolo di cui conosci i 3 vertici ma che non
vuoi prima disegnare e poi riempire allora puoi cercare una soluzione
diciamo piu' matematica.
Nel primo caso dato un punto inteno al triangolo puoi colorare un punto alla
volta a destra e a sinistra fino a quando incontri un punto gia' colorato.
Quindi scendi di un punto in basso e se il punto non e' gia' colorato fai la
stessa cosa. Idem verso l'alto.
Nel secondo caso, invece, partendo dal vertice piu' alto (ad esempio) tracci
il segmento orizzontale che unisce le 2 intersezioni di cui fa parte il
segmento con i lati del triangolo che partono dal vertice. Quindi ti sposti
verso il basso di un pixel fino a raggiungere l'altezza del vertice piu'
basso. Se il triangolo ha 2 vertici piu' alti (cioe' un lato orizzontale
piu' alto) puoi sempre partire da uno dei 2 vertici ma non devi considerare
il lato orizzontale per l'intersezione, bensi' l'altro lato.
Per quanto riguarda i poligoni convessi essi si possono facilmente scomporre
in triangoli unendo un vertice con gli altri e trattarli separatamente.
Per quanto riguarda i poligoni concavi la cosa e' piu' complicata. Feci
qualcosa molto tempo fa che non ricordo bene. Mi sembra che la logica fosse
quella di scomporre il poligono in uno o piu' poligoni concavi tracciando
(opportunamente) uno o piu' lati tra vertici opposti. Il problema sta
nell'individuare i vertici che possono essere uniti senza uscire dal
poligono. Se non sbaglio bisogna verificare le intersezioni con gli altri
lati ma considerare anche gli angoli per evitare di unire vertici
dall'esterno.
Ciao.
Antonio Donatiello.

riempire anche poligoni in generale, convessi e non).
L'approccio generale puo` essere:
1. identificare la "bounding box", cioe` il minimo rettangolo che
    racchiude il poligono; questo e` semplice, facendo una
    passata sull'elenco dei vertici -- basta prendere il min e il max
    di tutte le x e di tutte le y che si trovano sull'elenco, questi
    quattro valori definiscono il rettangolo "bounding box"; per
    coprirsi contro anomalie dovute a lati orizzontali o verticali
    puo` convenire "star larghi" di un pixel in ogni direzione.
2. per ogni riga orizzontale del bounding box trovare tutte le
    intersezioni con lati del poligono; conviene ignorare a
    questo fine i lati perfettamente orizzontali.  Sono "dentro"
    al poligono (convesso, concavo, intrecciato, o che altro)
    i punti di ciascuna linea orizzontale per cui, procedendo
    ad es. da sinistra a destra sulla riga, si sono sinora
    incontrate un numero dispari di intersezioni; quindi,
    bisognera` tracciare i relativi segmenti orizzontali.
3. l'importante e` evitare le anomalie: ad esempio, bisogna
    accertarsi che quando una linea tocca esattamente un
    vertice questo sia contato come DUE intersezioni (una
    per ciascuno dei due lati che arrivano a quel vertice) e
    quindi non cambi lo "stato di riempimento", mentre se la
    riga "taglia" un vertice invece di "toccarlo", questo deve
    contare come una sola intersezione; ad esempio questo
    si puo` ottenere considerando che ciascun lato "includa"
    (dal punto di vista del determinare le intersezioni) il proprio
    vertice piu` alto ma "escluda" quello piu` basso (o si puo`,
    ovviamente, fare anche il contrario, l'importante e` usare
    coerentemente la stessa convenzione per tutto il poligono).
4. sono possibili molte ottimizzazioni, ad esempio basate
    sul fatto che nella maggior parte dei casi il cambiamento
    fra righe orizzontali adiacenti e` "piccolo" (le intersezioni
    col poligono di una certa riga differiscono "poco" da quelle
    della precedente, e da esse possono essere ricalcolate
    incrementalmente, eccetto che per le righe corrispondenti
    esattamente alle coordinate y dei vertici).
    In particolare, l'algoritmo si basa sul tracciamento di sole
    linee orizzontali anche perche` questo caso particolare
    puo` normalmente essere ottimizzato in modo spinto (e`
    frequente che l'hardware abbia supporto speciale per le
    righe orizzontali, che pixel orizzontalmente adiacenti si
    trovino adiacenti in memoria, ecc, e comunque, se non
    altro, si semplificano molto i calcoli rispetto al generico
    tracciamento di linee di qualsivoglia inclinazione).
Esaminando il caso particolare del triangolo, notiamo che
ogni linea orizzontale del bounding box avra` esattamente 2
intersezioni con lati del triangolo (ignorando i lati orizzontali,
e con la convenzione di cui dicevamo al punto 3); quindi,
per il riempimento, bastera` tracciare il segmento fra questi
due punti di intersezione, per ciascuna linea orizzontale fra
la massima e la minima y in gioco.
Alex