Algoritam za iscrtavanje linija

Algoritam za iscrtavanje linija je grafički algoritam za aproksimiranje segmenta linije na grafičkim medijima. Na diskretnim medijima, kao što su računarski displeji bazirani na pikselima, i na računarskim štampačima, iscrtavanje linija zahteva aproksimaciju (u netrivijalnim slučajevima).

Na analognim medijima algoritam za iscrtavanje linija nije potreban. Na primer, osciloskopi koriste prirodne fenomene za iscrtavanje linija i krivih.

Prost algoritam za iscrtavanje linija

dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
	y = y1 + (dy) * (x - x1)/(dx)
	plot(x, y)
}

Ovde je pretpostavljeno da su tačke već poređane tako da $x_{2}>x_{1}$. Ovaj algoritam radi sasvim dobro kada $dx>=dy$, ali je prilično spor na digitalnim računarima, jer zahteva izračunavanja na brojevima u pokretnom zarezu. Ako je $dx<dy$, linija postaje prilično razređena, a u graničnom slučaju $dx=0$, se iscrtava samo jedna tačka!

Spisak algoritama za iscrtavanje linija

Sledi delimičan spisak algoritama za iscrtavanje linija:

• Brezenhamov linijski algoritam — optimizovan da koristi samo sabiranja (bez deljenja ili množenja); takođe izbegava izračunavanja u pokretnom zarezu.
• Ksaolin Vuov linijski algoritam — algoritam za iscrtavanje uz antialiasing, nešto sporiji od prethodnog.