title: Algoritmo scan line
text: # Algoritmo scan line
  
  Scan Line è un algoritmo per la rasterizzazione efficiente di poligoni.
  
  Dato un poligono, espresso sotto forma di segmenti $(x_{min},y_{min},x_{max},Y_{max})$ , è possibile determinare i punti interni del poligono tracciando delle linee parallele all'asse x e calcolando le intersezioni con i segmenti del poligono. Ogni volta che una linea di scansione interseca un segmento del poligono, possiamo considerare i punti successivi, fino alla prossima intersezione, come interni. Tali gruppi di punti sono chiamati span, e rappresentano i pixel da colorare all'interno dell'immagine.
  
  I passi del processo per determinare gli span sono tre:
  
  * Determinare le intersezioni tra la scan-line e i poligoni
  * Ordinare tali intersezioni secondo l'asse x
  * Determinare i punti interni sfruttando le intersezioni sulla linea calcolate precedentemente
  
  ## L'algoritmo
  
  Prima di iniziare, dobbiamo creare una tabella per salvare i punti di intersezione tra i segmenti del poligono. Tale tabella è chiamata ET (Edge Table), è formata da $(y_{max}$ - $y_{min})$ righe e contiene, ad ogni riga, una lista di segmenti che hanno come $y_{min}$ il valore y della scan-line. Un segmento all'interno della lista è rappresentato con la coordinata $y_{max}$ del segmento (l'estremo con y più grande), la coordinata $x_{min}$ del segmento e l'inverso della pendenza.
  
  Ora siamo pronti a determinare gli span per ogni scan-line: Si inizializza un'altra lista vuota, chiamata AET (Active Edge Table) per rappresentare gli spigoli attivi ad ogni scan-line.
  
  Partendo dalla prima riga della lista ET, si aggiunge alla AET tale riga, calcolando gli span tramite la regola even-odd. La regola consiste in suddividere i punti della scan-line in interni ed esterni: all'inizio i punti sono esterni e, ad ogni intersezione con i lati del poligono, cambiano in interni (o viceversa, cambiando da interni a esterni). Non vanno considerati nella regola i lati parallele alla scan-line, ne il vertice più piccolo o più grande del poligono rispetto alla coordinata y.
  
  Successivamente si aggiorna la tabella AET sommando l'inverso della pendenza alla coordinata x del segmento, per ottenere la giusta posizione x per la scan-line successiva.
  
  Una nota la merita la scelta dell'arrotondamento dei punti da considerare come interni: nella AET i punti x, ottenuti come somma di $x_{min}$ con l'inverso della pendenza, non assumeranno valori interi. Per applicare la regola even-odd, dunque, è necessario arrotondare i punti x delle intersezioni della scan-line con i segmenti del poligono. In particolare, se si passa da punti interni ad esterni, si arrotonda la coordinata x del punto all'intero più grande, mentre se si passa da punti interni a punti esterni, si arrotonda all'intero più piccolo.
  
  La colorazione prosegue finché ET è vuota
  
  