Introducere în algoritmul de trasare a liniei

În acest articol, vom vedea o schiță pe Algoritmul desenului de linii. Trasarea pe linie a computerului înseamnă că ecranul computerului se împarte în două părți rânduri și coloane. Aceste rânduri și coloane sunt cunoscute și sub denumirea de Pixeli. În cazul în care trebuie să desenăm o linie pe computer, în primul rând, trebuie să știm pe ce pixeli ar trebui să fie pornit. O linie este o parte a unei drepte care se extinde pe direcția opusă la nesfârșit. Linia este definită de două puncte finale. Densitatea sa trebuie să fie separată de lungimea liniei.
Formula pentru interceptarea liniei a pantei: Y = mx + b
În această formulă, m este o linie a pantei și b este interceptarea lui y în linie. În pozițiile (x1, y1) și (x2, y2), două puncte finale sunt specificate pentru segmentul de linie.

Valoarea pantei m și b poate fi determinată în consecință
• m = y2 - y1 / x2 - x1
• adică M = Δy / Δx

Exemplu:

Obiectivele finale sunt (0, 0) și (4, 12). Diagramați rezultatul pentru a calcula fiecare valoare a y ca pașii x de la 0 la 4.

Soluţie:

Avem deci o formulă de ecuație a liniei: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
Intercepția y se găsește apoi legând y1 și x1 la formula y = 3 x + b, 0 = 3 (0) + b. Prin urmare, b = 0, deci formula de linie y = 3x.
Scopul este de a determina următoarea locație x, y cât mai rapid de cea anterioară.

Tipuri de algoritm de trasare a liniilor

Mai jos sunt prezentate tipurile algoritmului:

1. Algoritmul diferențial digital (DDA)

O metodă de conversie incrementală este un algoritm DDA și, de asemenea, am numit algoritmul diferențial digital (DDA). Această abordare se caracterizează prin utilizarea rezultatelor din etapa anterioară în fiecare calcul.

Să ne uităm la exemplele date mai jos:

Exemplul # 1

Linia punctului final este (x1, y1) și (x2, y2)

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

deci, acum vom determina lungimea liniei dacă abs (dx)> = abs (dy) atunci lungime = abs (dx) else lungime = abs (dy)

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

Setpixel (rotund (x), rotund (y));

  • i = 1

while (i <= lungime)

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

setpixel (rotund (x), rotund (y));
i = i + 1
sfârșește în timp ce

Exemplul # 2

O linie de puncte finale (5, 4) și (6, 9) pot fi convertite cu DDA.

Soluţie:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Ca, dx <dy atunci,
• lungime = y2 - y1 = 5
• dx = (x2 - x1) / lungime = 1/5 = 0, 2
• dy = (y2- y1) / lungime = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Rezultat:

X1

Y1

X2

Y2

L

dx

dy

eu

X

Y

Rezultat

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

Limitarea algoritmului DDA

  • Aritmetica pentru punctele de plutire și rotunjire sunt proceduri care necesită mult timp.
  • O eroare de rotunjire poate duce la o distanță de la calea adevărată a segmentului cu linii lungi de către locația măsurată a pixelilor.

2. Algoritmul liniei Bresenham

Algoritmul de conversie Scan este algoritmul Bresenham. Acest algoritm oferă avantajul principal al utilizării numai a calculelor întregi.

1. Punctele finale ale rândului și stocați finalul din stânga în (x1, y1)
2. Pentru parametrul decizional pentru a obține prima valoare Δx adică Dx, iey adică Dy, 2 Δy și 2 Δx.
3. Inițializează pornirea
4. Inițializează i = 1 ca contor,
În caz contrar, următorul punct al graficului este (xk + 1, yk + 1) și repetă pasul 4 (Δx - 1).
Ajustare
Pentru m> 1, putem spune dacă creștem x de fiecare dată când creștem y.
După ce variabila de decizie pk va fi rezolvată, formula este foarte similară, doar x și y în ecuație vor fi înlocuite.

Rezumatul algoritmului din linia Bresenham

Acestea sunt următoarele avantaje pentru algoritmul liniei Bresenham:
• Un algoritm incremental rapid.
• Aceasta folosește doar calcule întregi.
DDA are următoarele probleme în comparație cu algoritmul DDA:
• Linia pixelată poate fi departe de acumularea preconizată a erorilor rotunde.
• Timpul este necesar pentru operațiunile de rotunjire și aritmetica în puncte flotante.

Articole recomandate

Acesta a fost un ghid pentru Algoritmul desenului de linii. Aici vom discuta despre ce este algoritmul de trasare a liniilor împreună cu diferitele exemple. De asemenea, puteți arunca o privire asupra articolelor următoare pentru a afla mai multe -

  1. Algoritmi de învățare a mașinilor
  2. Algoritmul SVM
  3. Regresie liniară simplă
  4. Regresie multivariată
  5. Comparația de top a regresiei liniare față de regresia logistică

Categorie:

Date mare