Trivial, DDA and Bresenham algorithm for a line in Java

Trivial, DDA and Bresenham algorithm for a line in Java

Drawing a line definitely belongs into basics of computer graphics. There are many algorithms for drawing a line. Some are more effective (Bresenham's), some are less (Trivial, DDA). Although you don't actually need to implement these algorithms yourself (you can you java.awt.Graphics), it's good to know that methods in this package actually do. I'll show you a java code for these 3 algorithms. Implementation in Java is very similar to C, so C# and other C's lover might look at it as well.


You can try my Functional java app that uses all these three algorithms below + some more additions :)

Sorry that the code uses some variables with Czech names and the same applies for the app, but it was just a school project.

Bresenham's line algorithm

Probably the most effective algorithm to draw a line by. It originates from the DD algorithm, but this variations uses only integers (int) - that's a huge advantage for Bresenham.

The code below is a code variation that covers all the situations that can occur during drawing a line - drawing properly in all halfquadrants according to the angle. It also draws perfectly when you start on the right side and end on the left or when the line is just 1 pixel long.

// Bresenham's algorithm

if ((x1 == x2) && (y1 == y2)) {           
    drawPixel(x1, y1, barva);

} else {              
    int dx = Math.abs(x2 - x1);
    int dy = Math.abs(y2 - y1);
    int rozdil = dx - dy;

    int posun_x, posun_y;

    if (x1 < x2) posun_x = 1; else posun_x = -1;
    if (y1 < y2) posun_y = 1; else posun_y = -1;

    while ((x1 != x2) || (y1 != y2)) {  

        int p = 2 * rozdil;

        if (p > -dy) {
            rozdil = rozdil - dy;
            x1 = x1 + posun_x;
        }
        if (p < dx) {
            rozdil = rozdil + dx;
            y1 = y1 + posun_y;
        }
        drawPixel(x1, y1, barva);
    }
} 

DDA line algorithm

A pattern for Bresenham's algorithm. The main difference is the date type of numbers - DDA uses real numbers, meaning float or double. But it seems to be a bit easier to understand.

The code below is a code variation that covers all the situations that can occur during drawing a line - drawing properly in all halfquadrants according to the angle. It also draws perfectly when you start on the right side and end on the left or when the line is just 1 pixel long.

// DDA algorithm

double dx = x2-x1;
double dy = y2-y1;

if (Math.abs(y2 - y1) <= Math.abs(x2 - x1)) {

    if ((x1 == x2) && (y1 == y2)) {
        drawPixel(x1, y1, barva);

    } else {
        if (x2 < x1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = (double)dy/dx; 
        int cele_y;           
        double y = (double)y1;

        for (int x = x1 ; x <= x2 ; x++) {
            cele_y = (int)Math.round(y);
            drawPixel(x, cele_y, barva);
            y += k;
        }
    }
} else {

        if (y2 < y1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = (double)dx/dy;
        int cele_x;
        double x = (double)x1;
        for (int y = y1; y <= y2; y++) {
            cele_x = (int)Math.round(x);
            drawPixel(cele_x, y, barva);
            x += k;
        }
}

Trivial line algorithm

The simplest algorithm for line drawing. Its logic is pretty straightforward - exactly as you would do it in math (analytic geometry, you remember, huh?). All these algorithms are mathematical, actually, but in this case, it's extremely clear.

The code below is a code variation that covers all the situations that can occur during drawing a line - drawing properly in all halfquadrants according to the angle. It also draws perfectly when you start on the right side and end on the left or when the line is just 1 pixel long.

// Trivial algorithm

    double dx = x2 - x1;
    double dy = y2 - y1;

    if (Math.abs(y2 - y1) >= Math.abs(x2 - x1)) {

    if ((x1 == x2) && (y1 == y2)) {
        drawPixel(x1, y1, barva);

    } else {
        if (y2 < y1) {
            int tmp = x2;
            x2 = x1;
            x1 = tmp;

            tmp = y2;
            y2 = y1;
            y1 = tmp;
        }

        double k = dx / (double) dy;
        double q = x1 - k * y1;

        for (int y = y1; y < y2; y++) {
            int x = (int) (k * y + q);
            drawPixel(x, y, barva);
        }
    }


} else {
    if (x2 < x1) {
        int tmp = x2;
        x2 = x1;
        x1 = tmp;

        tmp = y2;
        y2 = y1;
        y1 = tmp;
    }

    double k = dy / (double) dx;
    double q = y1 - k * x1;

    for (int x = x1; x < x2; x++) {
        int y = (int) (k * x + q);
        drawPixel(x, y, barva);
    }
}

<< Back to the previous page


Comments.
Ajay Kunnath
0

Thank you ! It works very well. Have you also tried XiaolinWu's algorithm for line drawing?

Published on 14.03.2019 08:07:22, from Mumbai, India
   Reply

Marek
0

Opravdu skvělý článek, s Bresenhamem jsem měl trochu problém s pochopením a prostě nikde na internetu jsem nenašel stručný kód, nyní si suprově rozumíme, moc díky :)

Published on 27.11.2016 21:44:14, from Czech Republic
JeffreyNib
0

which drug is used to treat chronic hepatitis b https://reifen-palacek.de/alvalin-kaufen.html drug test kits walgreens

Published on 02.02.2019 07:00:08, from Hagatna
Pepa
0

Pomohl byste i s bresenhamem na kružnici? Nikde na netu nemůžu najít algoritmus. Díky moc

Published on 26.10.2016 19:07:07, from CR
Pepa
0

nebo jakkoli vykreslit kružnici.. nepočítaje využití graphics :)

Published on 26.10.2016 19:09:51, from CR
rafa
0

Thank you so much! I understood Bresenham's algorithm easily.

Published on 12.10.2014 03:48:53, from Colombia
Tomáš Janeček
0

You're welcome :)

Published on 12.10.2014 12:22:40, from Řehoty, Czech Republic
me
0

What does it mean by barva?

Published on 09.06.2014 18:18:29, from Malaysia
Tomáš Janeček
+2

Sorry for not translating the variables - "barva" means "colour" :)

Published on 09.06.2014 21:08:47, from Řehoty, Czech Republic
Hakob_Jetzig
+1

helped me, thank you very much:)

Published on 09.06.2014 09:27:44, from Germany
Tomáš Janeček
+3

You're welcome :)

Published on 09.06.2014 21:09:23, from Řehoty, Czech Republic
Kevinclaip
0

doctorate in forensic psychology addus healthcare marion il requirements for pharmacy school

Published on 09.03.2019 15:22:34, from Havana
Anthonydar
0

who makes zeki tablets http://adipex.uniterre.com/ future pharmacy old bridge nj

Published on 12.04.2019 10:07:29, from Stung Treng
Anthonydar
0

how to pass a hair sample drug test http://buysaxenda.simplesite.com/ where to get free viagra samples

Published on 28.04.2019 17:55:19, from Stung Treng
Charleszes
0

best cold relief medicine http://provigil.cmonfofo.com/ best medicine for cat allergies

Published on 11.05.2019 04:40:59, from Nestor
aysujaroaoto
0

Buy Amoxicillin Online <a href="http://mewkid.net/buy-xalanta/">Amoxicillin 500mg</a> mdi.dzgz.tomasjanecek.cz.anv.dy http://mewkid.net/buy-xalanta/

Published on 07.10.2019 17:12:22, from Feldkirchen
Write a comment
 If you cann't see the verification code clearly.
Type the characters into the text field below(*)
 
This website uses cookies for ads, just like any other website. Further information