Uvod u algoritam crtanja linija

U ovom ćemo članku vidjeti strukturu algoritma crtanja linija. Crtanje linija na računalu znači da se ekran računala dijeli na dva dijela redaka i stupaca. Ti se redovi i stupci nazivaju i pikseli. U slučaju da moramo na računalu nacrtati crtu, prvo moramo znati na kojim se pikselima trebaju nalaziti. Crta je dio ravne linije koja se proteže u suprotnom smjeru u nedogled. Linija je definirana s dvije Krajnje točke. Njegova gustoća treba biti odvojena od duljine crte.
Formula za presijecanje linija nagiba: Y = mx + b
U ovoj je formuli m linija nagiba, a b presjek y u liniji. U pozicijama (x1, y1) i (x2, y2) dvije su krajnje točke određene za linijski segment.

Vrijednost nagiba m i b može se odrediti u skladu s tim
• m = y2 - y1 / x2 - x1
• tj. M = Δy / Δx

Primjer:

Krajnje krajnje točke su (0, 0) i (4, 12). Nacrtajte rezultat za izračunavanje svake vrijednosti y kao x koraka od 0 do 4.

Riješenje:

Dakle, imamo formulu jednadžbe pravca: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
Y presretanje b se zatim pronalazi povezivanjem y1 i x1 s y = 3 x + b formulom, 0 = 3 (0) + b. Stoga je b = 0, pa je y = 3x linija.
Cilj je odrediti sljedeću lokaciju x, y što je brže moguće od prethodne.

Vrste algoritama crtanja linija

Ispod su navedene vrste algoritma:

1. Digitalni diferencijalni algoritam (DDA)

Metoda inkrementalne pretvorbe je algoritam DDA, a također smo je nazvali i digitalni diferencijalni algoritam (DDA). Ovaj pristup karakterizira upotreba rezultata iz prethodne faze u svakom proračunu.

Pogledajmo primjere dane u nastavku:

Primjer 1

Linije krajnje točke su (x1, y1) i (x2, y2)

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

Dakle, sada ćemo odrediti duljinu retka ako je abs (dx)> = abs (dy), a zatim duljina = abs (dx), inače, dužina = abs (dy)

  • Δx = dx / dužina
  • Δy = dy / duljina
  • X = x1
  • Y = y1

Setpixel (okrugli (x), okrugli (y));

  • i = 1

dok je (i <= dužina)

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

setpixel (okrugli (x), okrugli (y));
i = i + 1
kraj dok

Primjer 2

Linija krajnjih točaka (5, 4) i (6, 9) može se pretvoriti pomoću DDA.

Riješenje:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Kao, dx <dy tada,
• duljina = y2 - y1 = 5
• dx = (x2 - x1) / dužina = 1/5 = 0, 2
• dy = (y2-y1) / dužina = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Proizlaziti:

X1

Y1

X2

Y2

L

Dx

dy

ja

x

Y

Proizlaziti

3

2

4

7

5

0, 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

Ograničenje algoritma DDA

  • Aritmetika za plutajuće i zaokružujuće točke zahtijeva mnogo vremena.
  • Pogreška zaokruživanja može dovesti do udaljenosti od stvarne putanje segmenta duge linije prema mjestu izmjerenih piksela.

2. Algoritam Bresenhamove linije

Algoritam za konverziju Skeniranja je Bresenham-algoritam. Ovaj algoritam nudi glavnu prednost upotrebe samo cjelobrojnih izračuna.

1. Krajnje točke retka i pohranite lijevu krajnju točku u (x1, y1)
2. Da bi parametar odluke dobio prvu vrijednost Δx, tj. Dx, Δy tj. Dy, 2 Δy i 2 Δx.
3. Inicijalizirajte početak
4. Inicijalizirajte i = 1 kao brojač,
U suprotnom, sljedeća točka za crtanje je (xk + 1, yk + 1) i ponovite korak 4 (Δx - 1) puta.
Podešavanje
Za m> 1, možemo reći ako povećavamo x svaki put kad povećamo y.
Nakon što se riješi varijabla pk, formula je vrlo slična, zamijenit će se samo x i y u jednadžbi.

Bresenham Line Algorithm Sažetak

Ovo su sljedeće prednosti algoritma Bresenham linije:
• Brzi inkrementalni algoritam.
• Ovo koristi samo cijele izračune.
DDA ima sljedeće probleme u usporedbi s algoritmom DDA:
• Pikselirana linija može biti udaljena od očekivanog gomile zaokruženih pogrešaka.
• Vrijeme je potrebno za operacije zaokruživanja i aritmetiku s pomičnim točkama.

Preporučeni članci

Ovo je vodič za algoritam crtanja crta. Ovdje ćemo raspravljati o algoritmu crtanja linija uz različite primjere. Možete također pogledati sljedeće članke da biste saznali više -

  1. Algoritmi strojnog učenja
  2. SVM algoritam
  3. Jednostavna linearna regresija
  4. Multivarijantna regresija
  5. Vrhunska usporedba linearne regresije i logističke regresije

Kategorija:

Veliki podaci