Algoritm de rasterizare a liniei

Un algoritm de rasterizare a liniei este un algoritm grafic care se ocupă cu aproximarea unei linii sau a unui segment într-o reprezentare grafică discretă. Exemple de reprezentări grafice discrete pot fi monitorul, format din mii de pixeli , sau o imprimare, cu mii de puncte. Reprezentarea pe aceste „suprafețe” necesită o aproximare, desigur în cazuri non-banale.

În reprezentări nediscrete și, prin urmare, continue, această lucrare nu are loc. Exemple de reprezentări grafice continue sunt osciloscoapele tubului catodic .

Un exemplu al problemei poate fi văzut în figura 0:

Figura 0.

În fundal vedeți o grilă, care reprezintă pixelii unei imagini. Segmentul roșu (de la punctul p1 la punctul p2) este segmentul pe care am dori să-l rasterizăm. În partea dreaptă vedem un exemplu de rasterizare. Am evidențiat în negru pixelii care ar trebui să se aprindă pentru a vizualiza segmentul de la punctul p1 la punctul p2.

Un algoritm simplu de rasterizare a liniei

Având în vedere două puncte p1 și p2, cu coordonatele (x ₁ , y ₁ ) și (x ₂ , y ₂ ), putem folosi următorul algoritm:

 dx = x2 - x1
dy = y2 - y1
pentru x de la x1 la x2 {
	y = y1 + (y2 - y1) * (x - x1) / (x2 - x1)
	draw_point (x, y)
}

În cazul nostru, am simplificat operațiunea presupunând că punctele sunt ordonate, adică $x_{2}>x_{1}$ ${\ displaystyle x_ {2}> x_ {1}}$ ${\ displaystyle x_ {2}> x_ {1}}$ Și $y_{2}>y_{1}$ ${\ displaystyle y_ {2}> y_ {1}}$ ${\ displaystyle y_ {2}> y_ {1}}$ . Algoritmul funcționează bine cu $dx>=dy$ ${\ displaystyle dx> = dy}$ ${\ displaystyle dx> = dy}$ (figura 1.), dar devine destul de lent pe computere, datorită calculelor în virgulă mobilă.

Figura 1.

Daca avem $dx<dy$ ${\ displaystyle dx <dy}$ ${\ displaystyle dx <dy}$ , punctele liniei devin „împrăștiate”, așa cum se arată în figura 2.

Figura 2.

În cazul extrem al $dx=0$ ${\ displaystyle dx = 0}$ ${\ displaystyle dx = 0}$ se atrage un singur punct.

Lista algoritmilor de rasterizare a liniei

Lista nu trebuie să fie completă:

Algoritm DDA -
Algoritm de linie Bresenham - optimizat pentru a utiliza numai adăugiri și pentru a evita utilizarea calculelor în virgulă mobilă.
Algoritmul liniei Xiaolin Wu - poate realiza antialiasing

Rasterizarea poligonului

Algoritmul de rasterizare a poligonului este un algoritm de rasterizare care se ocupă cu convertirea unui poligon definit prin vârfurile sale într-o imagine raster (sau bitmap ).

Cea mai simplă problemă este de a converti un poligon gol, adică în care sunt definite doar laturile. În acest caz, se poate face o utilizare recursivă a unui algoritm de rasterizare a liniei pentru fiecare parte a poligonului.

Problema devine mai complicată în cazul poligoanelor umplute. În figura 1 putem vedea câteva exemple de poligon: