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

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

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

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

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

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

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

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

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