Crtanje linije

Za crtanje linije koristi se Bresenham-ov postupak. Algoritam je slijedeći :
  1. Učitati x i y koordinate početne i završne točke, (x1,y1) (x2, y2).
  2. Izračunati udaljenost (razliku) x i y koordinata, tj. x0 = |x2-x1|, te y0 = |y2-y1|.
  3. Odrediti u kojem kvadrantu se nalazi završna točka i prema tome odrediti za x i y faktor povećanja
    • I.   kvadrant: za x  1, y  1
    • II.  kvadrant: za x -1, y  1
    • III. kvadrant: za x -1, y -1
    • IV.  kvadrant: za x  1, y -1
  4. Odabrati koordinate čija je udaljenost veća (u daljnjem tekstu prva koordinata).
  5. Izračunati omjer k =veća razlika/manja razlika, te postaviti D na vrijednost k.
  6. Postaviti vrijednost prva na početnu vrijednost prve koordinate, druga na početnu vrijednost druge koordinate
  7. Za i=0, dok je i manji od udaljenosti prve koordinate raditi slijedeće :
    1. Osvijetli točku sa korespodentnim točkama x i y koordinata (prva/druga)
    2. Provjeriti da li je D>0.5. Ako je povećati druga ovisno o tome koju koordinatu predstavlja i ovisno o koraku 3, te smanjiti D za 1.
    3. Povečati prva ovisno o tome koju koordinatu predstavlja i ovisno o koraku 3
    4. Povečati i za 1, te D za k

Ostvarenje gore opisanog algoritama je slijedeće:
        POSTAVI X UDALJENOST prva0  NA EndX - StartX + 1
        POSTAVI Y UDALJENOST druga0 NA EndY - StartY + 1
        AKO prva0 < 0 ONDA
            POSTAVI prva_plus  = -1
        INAČE
            POSTAVI prva_plus  =  1
        AKO druga0 < 0 ONDA
            POSTAVI druga_plus = -1;
        INAČE
            POSTAVI druga_plus =  1;
        POSTAVI prva0  = |prva0|, druga0 = |druga0|
        AKO prva0 >= druga0 ONDA
            POSTAVI KOEFICIJENT SMJERA : D,k = 1 * druga0 / prva0
            POSTAVI prva = StartX, druga = StartY
            POSTAVI prva_kraj = prva0
        KRAJ
        INAČE
            POSTAVI KOEFICIJENT SMJERA : D,k = 1 * prva0 / druga0
            POSTAVI prva = StartY, druga = StartX
            POSTAVI prva_kraj = druga0
            ZAMIJENI prva_plus ZA druga_plus POŠTO JE Y KOORDINATA VEĆA OD X KOORDINATE
        KRAJ
        AKO prva0 >= druga0 ONDA
            ZA i=0, prva_kraj RADI
                OSVIJETLI TOČKU (StartX, StartY)
                AKO D > 0.5 ONDA
                    UVEČAJ druga ZA druga_plus
                    UMANJI D ZA 1
                KRAJ
                UVEČAJ prva ZA prva_plus I D ZA k
            KRAJ
        KRAJ
        INAČE
            ZA i=0, prva_kraj
                OSVIJETLI TOČKU (StartX, StartY)
                AKO D > 0.5 ONDA
                    UVEČAJ druga ZA druga_plus
                    UMANJI D ZA 1
                KRAJ
                UVEČAJ prva ZA prva_plus I D ZA k
            KRAJ
        KRAJ
           
Gore opisani algoritam može se modificirati tako da se koriste samo cjelobrojne vrijednosti na sljedeći način (imena varijabli se NE poklapaju sa gornjim primjerom):

        AKO StartX < EndX ONDA
            POSTAVI plusX= 1;
        INAČE
            POSTAVI plusX=-1;
        AKO StartY < EndY ONDA
            POSTAVI plusY= 1;
        INAČE
            POSTAVI plusY=-1;
        POSTAVI x0 = |EndX-StartX+1|, y0 = |EndY-StartY+1|
        AKO JE "KUT" IZMEĐU 315 i 45 ili 135 i 255 STUPNJEVA (TJ. x0 > y0 ) ONDA
            ZA i,j=0 DOK JE i < x0 RADI
                OSVIJETLI TOČKU (StartX, StartY)
                UVEČAJ j ZA y0
                AKO "KUT" PREĐE 45 STUPNJEVA (TJ. j >= x0 ) ONDA
                    UMANJI j ZA x0
                    UVEČAJ StartY ZA plusY
                KRAJ
                UVEČAJ StartX za plusX
            KRAJ PETLJE
        KRAJ
        INAČE, "KUT" JE IZMEĐU 45 i 135 ili 225 i 315 STUPNJEVA
            ZA i,j=0 DOK JE i < y0
                OSVIJETLI TOČKU (StartX, StartY)
                UVEČAJ j ZA x0
                AKO "KUT" PREĐE 45 STUPNJEVA (TJ. j >= y0 ) ONDA
                    UMANJI j ZA y0
                    UVEČAJ StartX ZA plusX
                KRAJ
                UVEČAJ StartY ZA plusY
            KRAJ
        KRAJ

Demonstracija

Gore navedeni algoritmi su implementirani u programskom jeziku JAVA i mogu se testirati pomoću slijedećeg appleta.
Klikom bilo gdje na površini appleta odabire se početna točka linije. Pomakom miša i trenutnom lokacijom odabire se završna točka linije za iscrtavanje te se ona iscrtava nanovo pri svakom pomaku miša. Zelena linija predstavlja liniju koja spaja malo prije opisane točke spojene inicijalnim Bresenham-ovim algoritmom,  dok crvena predstavlja liniju crtanu modificiranim algoritmom (koji koristi samo cjelobrojne vrijednosti)  pomaknutu za -20 pixel-a u y smjeru u odnosu na zelenu liniju. Plava linija se iscrtava pomoću metode ugrađene u programski jezik JAVA i pomaknuta je za +20 pixela u y smjeru u odnosu na zelenu liniju.


Napisao Andro Galinović