Algoritmo di generazione di linee

Una linea collega due punti. È un elemento di base nella grafica. Per disegnare una linea, hai bisogno di due punti tra i quali puoi disegnare una linea. Nei seguenti tre algoritmi, ci riferiamo a un punto della linea $ X_ {0}, Y_ {0} $ e al secondo punto della linea $ X_ {1}, Y_ {1} $.

Algoritmo DDA

L'algoritmo Digital Differential Analyzer (DDA) è il semplice algoritmo di generazione di linee che viene spiegato passo dopo passo qui.

Step 1 - Ottieni l'input di due punti finali $ (X_ {0}, Y_ {0}) $ e $ (X_ {1}, Y_ {1}) $.

Step 2 - Calcola la differenza tra due punti finali.

dx = X1 - X0
dy = Y1 - Y0

Step 3- In base alla differenza calcolata nel passaggio 2, è necessario identificare il numero di passaggi per inserire pixel. Se dx> dy, allora hai bisogno di più passaggi in coordinata x; altrimenti in coordinata y.

if (absolute(dx) > absolute(dy))
   Steps = absolute(dx);
else
   Steps = absolute(dy);

Step 4 - Calcola l'incremento in coordinata x e coordinata y.

Xincrement = dx / (float) steps;
Yincrement = dy / (float) steps;

Step 5 - Metti il ​​pixel incrementando di conseguenza le coordinate xey e completa il disegno della linea.

for(int v=0; v < Steps; v++)
{
   x = x + Xincrement;
   y = y + Yincrement;
   putpixel(Round(x), Round(y));
}

Generazione di linee di Bresenham

L'algoritmo di Bresenham è un altro algoritmo di conversione della scansione incrementale. Il grande vantaggio di questo algoritmo è che utilizza solo calcoli interi. Spostandoti sull'asse x in intervalli di unità e ad ogni passaggio scegli tra due diverse coordinate y.

Ad esempio, come mostrato nell'illustrazione seguente, dalla posizione (2, 3) è necessario scegliere tra (3, 3) e (3, 4). Vorresti il ​​punto più vicino alla linea originale.

Nella posizione campione $ X_ {k} + 1, $ le separazioni verticali dalla linea matematica sono etichettate come $ d_ {upper} $ e $ d_ {lower} $.

Dall'illustrazione sopra, la coordinata y sulla linea matematica a $ x_ {k} + 1 $ è -

Y = m ($ X_ {k} $ + 1) + b

Quindi, $ d_ {upper} $ e $ d_ {lower} $ sono dati come segue:

$$ d_ {lower} = y-y_ {k} $$

$$ = m (X_ {k} + 1) + b - Y_ {k} $$

e

$$ d_ {upper} = (y_ {k} + 1) - y $$

$ = Y_ {k} + 1 - m (X_ {k} + 1) - b $

Puoi usarli per prendere una decisione semplice su quale pixel è più vicino alla linea matematica. Questa semplice decisione si basa sulla differenza tra le due posizioni dei pixel.

$$ d_ {lower} - d_ {upper} = 2 m (x_ {k} + 1) - 2y_ {k} + 2b - 1 $$

Sostituiamo m con dy / dx dove dx e dy sono le differenze tra i punti finali.

$$ dx (d_ {lower} - d_ {upper}) = dx (2 \ frac {\ mathrm {d} y} {\ mathrm {d} x} (x_ {k} + 1) - 2y_ {k} + 2b - 1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + 2dy + 2dx (2b-1) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Quindi, un parametro di decisione $ P_ {k} $ per il k- esimo passo lungo una linea è dato da -

$$ p_ {k} = dx (d_ {lower} - d_ {upper}) $$

$$ = 2dy.x_ {k} - 2dx.y_ {k} + C $$

Il segno del parametro di decisione $ P_ {k} $ è uguale a quello di $ d_ {lower} - d_ {upper} $.

Se $ p_ {k} $ è negativo, scegli il pixel inferiore, altrimenti scegli il pixel superiore.

Ricorda, le modifiche alle coordinate avvengono lungo l'asse x in incrementi di unità, quindi puoi fare tutto con calcoli interi. Al passo k + 1, il parametro di decisione è dato come -

$$ p_ {k +1} = 2dy.x_ {k + 1} - 2dx.y_ {k + 1} + C $$

Sottraendo $ p_ {k} $ da questo otteniamo -

$$ p_ {k + 1} - p_ {k} = 2dy (x_ {k + 1} - x_ {k}) - 2dx (y_ {k + 1} - y_ {k}) $$

Ma $ x_ {k + 1} $ è uguale a $ (xk) + 1 $. Quindi ...

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx (y_ {k + 1} - y_ {k}) $$

Dove, $ Y_ {k + 1} - Y_ {k} $ è 0 o 1 a seconda del segno di $ P_ {k} $.

Il primo parametro decisionale $ p_ {0} $ è valutato a $ (x_ {0}, y_ {0}) $ è dato come -

$$ p_ {0} = 2dy - dx $$

Ora, tenendo presente tutti i punti e i calcoli di cui sopra, ecco l'algoritmo di Bresenham per la pendenza m <1 -

Step 1 - Immettere i due punti finali della linea, memorizzando il punto finale sinistro in $ (x_ {0}, y_ {0}) $.

Step 2 - Traccia il punto $ (x_ {0}, y_ {0}) $.

Step 3 - Calcola le costanti dx, dy, 2dy e (2dy - 2dx) e ottieni il primo valore per il parametro decisionale come -

$$ p_ {0} = 2dy - dx $$

Step 4 - Ad ogni $ X_ {k} $ lungo la linea, a partire da k = 0, eseguire il seguente test:

Se $ p_ {k} $ <0, il punto successivo da tracciare è $ (x_ {k} +1, y_ {k}) $ e

$$ p_ {k + 1} = p_ {k} + 2dy $$ Altrimenti,

$$ (x_ {k}, y_ {k} +1) $$

$$ p_ {k + 1} = p_ {k} + 2dy - 2dx $$

Step 5 - Ripetere il passaggio 4 (dx - 1) volte.

Per m> 1, scopri se devi incrementare x incrementando y ogni volta.

Dopo la risoluzione, l'equazione per il parametro decisionale $ P_ {k} $ sarà molto simile, vengono scambiati solo xey nell'equazione.

Algoritmo del punto medio

L'algoritmo del punto medio è dovuto a Bresenham che è stato modificato da Pitteway e Van Aken. Supponiamo di aver già inserito il punto P alla coordinata (x, y) e che la pendenza della linea sia 0 ≤ k ≤ 1 come mostrato nell'illustrazione seguente.

Ora devi decidere se mettere il punto successivo in E o N. Questo può essere scelto identificando il punto di intersezione Q più vicino al punto N o E. Se il punto di intersezione Q è più vicino al punto N allora N è considerato come il punto successivo; altrimenti E.

Per determinarlo, calcolare prima il punto medio M (x + 1, y + ½). Se il punto di intersezione Q della linea con la linea verticale che collega E e N è sotto M, allora prendi E come punto successivo; altrimenti prendi N come punto successivo.

Per verificarlo, dobbiamo considerare l'equazione implicita:

F (x, y) = mx + b - y

Per m positivo in un dato X,

  • Se y è sulla riga, allora F (x, y) = 0
  • Se y è sopra la linea, allora F (x, y) <0
  • Se y è sotto la linea, allora F (x, y)> 0