algoritmo di disegno di una linea

l'immagine è una matrice di punti

esempio: immagine 11x11

una linea nell'immagine

esempio: linea da 0,0 a 10,3

disegnare = cambiare il colore di alcuni punti

quali punti vanno cambiati?

la coordinata y cresce in proporzione con la x

proporzione

la coordinata y cresce in proporzione con la x

linea da 0,0 a 10,3
x va da 0 a 10
y va da 0 a 3

proporzione 10 a 3

x / y = 10 / 3

valore di y:

y = x × 3 / 10

moltiplicazioni e divisioni

meno rapide di somme e spostamenti

le linee vengono disegnate molte volte

progressione

per ogni x c'è un solo punto

ciclo di x da 0 a 10
disegno di un punto per volta

ciclo di disegno

x da 0 a 10

un solo punto per ogni x

inizia ad altezza 0
al passo successivo, resta all'altezza precedente
o sale di una posizione

chi decide se resta o sale?

• y = x × 3 / 10
• si arrotonda all'intero più vicino
• uguale a precedente y ⇒ resta
  maggiore ⇒ sale

cosa serve

y = x × 3 / 10

non serve il valore esatto di y
nemmeno sapere l'intero più vicino
basta sapere se l'intero più vicino è lo stesso di prima

x=0

x = 0

y = x × 3 / 10 = 0 × 3 / 10 = 0
punto 0,0

x=1

x = 0

y = 0

x = 1

y = x × 3 / 10 = 3 / 10

è più vicino a 0 oppure a 1?
y < 0.5 → 0
y ≥ 0.5 → 1

manipolazioni numeriche

x = 0

y = 0

x = 1

y = x × 3 / 10

resta a zero se y < 0.5

manipolo la disuguaglianza:
x × 3 / 10 < 0.5
x × 3 / 10 < 1 / 2
2 × x × 3 < 1 × 10
2 × 1 × 3 < 1 × 10
6 < 10

moltiplicazione 2 × … = shift di due bit

il punto resta ad altezza zero

x=2

…

x = 1

y = 0

x = 2

y = x × 3 / 10

y < 0.5?

stessa manipolazione:
x × 3 / 10 < 0.5
x × 3 / 10 < 1 / 2
2 × x × 3 < 10
2 × 2 × 3 < 10
12 < 10

moltiplicazioni 2 × … = shift di una posizione

sale a y=1

x=3

…

x = 2

y = 1

x = 3

y = x × 2 / 10

questa volta y era 1 invece di 0
sale ancora se la nuova y è maggiore o uguale di 1.5
in generale: confronto con y + 0.5 per la y precedente

manipolazione:
x × 3 / 10 < y + 0.5
x × 3 / 10 < (2 × y + 1) / 2
2 × x × 3 < (2 × y + 1) × 10
2 × 3 × 3 < (2 × 1 + 1) × 10
2 × 3 × 3 < 3 × 10
18 < 30

3 × 3 non è uno shift!
3 × 10 nemmeno!

servono moltiplicazioni vere?

prima moltiplicazione

…

x = 2

…
2 × x × 3 < …
2 × 2 × 3 < …
…

x = 3

…
2 × x × 3 < …
2 × ((x-1) + 1) × 3 < …
(2 × (x-1) × 3) + (2 × 1 × 3) < …
(2 × 2 × 3) + (2 × 1 × 3) < …
…

primo addendo 2 × 2 × 3 calcolato per la x precedente
secondo addendo 2 × 1 × 3 è uno shift
si sommano

valore calcolato prima, shift, somma: facili

passo qualsiasi

…

x = v-1

…
2 × x × 3 < …
2 × (v-1) × 3 < …
…

x = v

…
2 × x × 3 < …
2 × v × 3 < …
2 × (v-1) × 3 + (2 × 1 × 3) < …
…

2 × (v-1) × 3: calcolato prima

2 × 1 × 3: shift

somma

valore calcolato prima, shift, somma: facili

seconda moltiplicazione

…

x = v-1

…
… < (2 × y + 1) × 10
…

x = v

…
… < (2 × y + 1) × 10

…

se y non cambia: stesso valore calcolato prima

se y aumenta di uno:

… < (2 × y + 1) × 10
… < (2 × ((y-1) + 1) + 1) × 10
… < ((2 × (y-1) + 2 × 1) + 1) × 10
… < (2 × (y-1) + 2 × 1 + 1) × 10
… < (2 × (y-1) + 1 + 2 × 1) × 10
… < ((2 × (y-1) + 1) + (2 × 1)) × 10
… < (2 × (y-1) + 1) × 10 + (2 × 1) × 10

(2 × (y-1) + 1) × 10: calcolato prima

(2 × 1) × 10: shift

somma

valore calcolato prima, shift, somma: facili

da dove vengono 3 e 10?

coordinate del punto finale
in generale: xe, ye

cosa serve calcolare

xe al posto di 10
ye al posto di 3

x = v-1

…
2 × x × ye < (2 × y + 1) × xe
…

x = v

…
2 × x × ye < (2 × y + 1) × xe
…

cosa serve memorizzare

x = v-1

…
2 × x × ye < (2 × y + 1) × xe
…

x = v

…
2 × x × ye < (2 × y + 1) × xe
…

2 × x × ye uguale al valore precedente più 2 × ye

(2 × y + 1) × xe uguale al valore precedente
oppure al valore precedente più 2 × xe

variabili yt e xt per i valori precedenti

esempio di implementazione

variabili xt e yt per i valori memorizzati
quelli che vengono confrontati per decidere se salire o no

moltiplicazione per due = shift di una posizione a sinistra

	xt = xe;
	yt = 0;
	y = 0;
	for (x = 0; x <= xe; x++) {
		plane[x][y] = 'X';
		yt = yt + (ye << 1);		// yt = yt + 2 * ye;
		if (yt < xt) 
			y = y;			// y non cambia
			xt = xt;
		}
		else {
			y = y + 1;		// y aumento di uno
			xt = xt + (xe << 1);	// xt = xt + 2 * xe;
		}
	}

linea.c

maggiore pendenza? altri quadranti?

linea da 0,0 a 3,10

stesso sistema scambiando x e y

altri quadranti: scambio x con -x, etc.