Introduzione all'algoritmo di disegno al tratto

In questo articolo, vedremo uno schema dell'algoritmo di disegno al tratto. Il disegno al tratto sul computer indica che lo schermo del computer si divide in due parti di righe e colonne. Quelle righe e colonne sono anche conosciute come Pixel. Nel caso in cui dobbiamo disegnare una linea sul computer, prima di tutto, dobbiamo sapere quali pixel dovrebbero essere attivi. Una linea fa parte di una linea retta che si estende indefinitamente nella direzione opposta. La linea è definita da due endpoint. La sua densità dovrebbe essere separata dalla lunghezza della linea.
La formula per un'intercettazione di linea della pendenza: Y = mx + b
In questa formula, m è una linea della pendenza e b è l'intercetta di y nella linea. Nelle posizioni (x1, y1) e (x2, y2), vengono specificati due punti finali per il segmento di linea.

Il valore della pendenza m e b può essere determinato di conseguenza
• m = y2 - y1 / x2 - x1
• ie M = Δy / Δx

Esempio:

Gli endpoint di linea sono (0, 0) e (4, 12). Traccia il risultato per calcolare ogni valore di y come i passaggi x da 0 a 4.

Soluzione:

Quindi abbiamo una formula di equazione di linea: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
L'intercetta y si trova quindi collegando y1 e x1 alla formula y = 3 x + b, 0 = 3 (0) + b. Pertanto, b = 0, quindi la formula di linea y = 3x.
L'obiettivo è determinare la prossima posizione x, y il più rapidamente possibile dalla precedente.

Tipi di algoritmo di disegno al tratto

Di seguito sono riportati i tipi di algoritmo:

1. Algoritmo differenziale digitale (DDA)

Un metodo di conversione incrementale è un algoritmo DDA e abbiamo anche chiamato algoritmo differenziale digitale (DDA). Questo approccio è caratterizzato dall'uso dei risultati della fase precedente in ogni calcolo.

Diamo un'occhiata agli esempi riportati di seguito:

Esempio 1

Le linee del punto finale sono (x1, y1) e (x2, y2)

  • dx = x2 - x1
  • dy = y2 - y1

quindi, ora determineremo la lunghezza della linea se abs (dx)> = abs (dy) quindi length = abs (dx) else length = abs (dy)

  • Δx = dx / lunghezza
  • Δy = dy / lunghezza
  • X = x1
  • Y = y1

Setpixel (rotondo (x), rotondo (y));

  • i = 1

while (i <= lunghezza)

  • x = x + Δx;
  • y = y + Δy;

setpixel (rotondo (x), rotondo (y));
i = i + 1
fine mentre

Esempio n. 2

Una linea di punti finali (5, 4) e (6, 9) può essere convertita con il DDA.

Soluzione:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Come, dx <dy quindi,
• lunghezza = y2 - y1 = 5
• dx = (x2 - x1) / lunghezza = 1/5 = 0, 2
• dy = (y2- y1) / lunghezza = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Risultato:

X1

Y1

X2

Y2

L

Dx

dy

io

X

Y

Risultato

3

2

4

7

5

.2

1

0

3.5

5.5

3.5, 5.5

1

3.9

1.5

3.9, 1.5

2

4.9

3.5

4.9, 3.5

3

5.1

7.5

5.1, 7.5

4

3.7

4.5

3.7, 4.5

5

4.5

7.5

4.5, 7.5

Limitazione dell'algoritmo DDA

  • L'aritmetica per i punti flottanti e arrotondati è una procedura che richiede tempo.
  • Un errore di arrotondamento può portare a una distanza dal percorso del segmento di linea lunga reale in base alla posizione del pixel misurato.

2. L'algoritmo della linea di Bresenham

L'algoritmo di conversione Scan è l'algoritmo di Bresenham. Questo algoritmo offre il vantaggio principale di utilizzare solo calcoli di numeri interi.

1. Endpoint della riga e memorizzare l'endpoint sinistro in (x1, y1)
2. Affinché il parametro di decisione ottenga il primo valore Δx cioè Dx, Δy cioè Dy, 2 Δy e 2 Δx.
3. Inizializza l'avvio
4. Inizializza i = 1 come contatore,
In caso contrario, il punto successivo da tracciare è (xk + 1, yk + 1) e ripetere il passaggio 4 (Δx - 1) volte.
registrazione
Per m> 1, possiamo dire se aumentiamo x ogni volta che aumentiamo y.
Dopo che la variabile di decisione pk sarà risolta, la formula è molto simile, verranno sostituiti solo xey nell'equazione.

Riepilogo algoritmo della linea di Bresenham

Questi sono i seguenti vantaggi dell'algoritmo di linea Bresenham:
• Un algoritmo incrementale veloce.
• Questo utilizza solo calcoli di numeri interi.
DDA presenta i seguenti problemi rispetto all'algoritmo DDA:
• La linea pixelata può essere distante dall'accumulo previsto di errori di arrotondamento.
• Il tempo è necessario per le operazioni di arrotondamento e l'aritmetica in virgola mobile.

Articoli consigliati

Questa è stata una guida per l'algoritmo di disegno al tratto. Qui discutiamo cos'è l'algoritmo di disegno al tratto insieme ai vari esempi. Puoi anche dare un'occhiata ai seguenti articoli per saperne di più–

  1. Algoritmi di apprendimento automatico
  2. Algoritmo SVM
  3. Regressione lineare semplice
  4. Regressione multivariata
  5. Migliore confronto tra regressione lineare e regressione logistica

Categoria:

Big Data