Алгоритам за исцртавање линија

Алгоритам за исцртавање линија је графички алгоритам за апроксимирање сегмента линије на графичким медијима. На дискретним медијима, као што су рачунарски дисплеји базирани на пикселима, и на рачунарским штампачима, исцртавање линија захтева апроксимацију (у нетривијалним случајевима).

На аналогним медијима алгоритам за исцртавање линија није потребан. На пример, осцилоскопи користе природне феномене за исцртавање линија и кривих.

Прост алгоритам за исцртавање линија

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

Овде је претпостављено да су тачке већ поређане тако да ${\displaystyle x_{2}>x_{1}}$. Овај алгоритам ради сасвим добро када ${\displaystyle dx>=dy}$, али је прилично спор на дигиталним рачунарима, јер захтева израчунавања на бројевима у покретном зарезу. Ако је ${\displaystyle dx<dy}$, линија постаје прилично разређена, а у граничном случају ${\displaystyle dx=0}$, се исцртава само једна тачка!

Списак алгоритама за исцртавање линија

Следи делимичан списак алгоритама за исцртавање линија:

• Брезенхамов линијски алгоритам — оптимизован да користи само сабирања (без дељења или множења); такође избегава израчунавања у покретном зарезу.
• Ксаолин Вуов линијски алгоритам — алгоритам за исцртавање уз антиалиасинг, нешто спорији од претходног.