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[uredi | uredi izvor]
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 .
Ovaj algoritam radi sasvim dobro kada , ali je prilično spor na digitalnim računarima, jer zahteva izračunavanja na brojevima u pokretnom zarezu. Ako je , linija postaje prilično razređena, a u graničnom slučaju , se iscrtava samo jedna tačka!
Spisak algoritama za iscrtavanje linija[uredi | uredi izvor]
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.