Bresenham Line Algorithm

Question

Good day all,

I am struggling to complete an algorithm for bresenham line equation.

The output I get is the output in black and the output expected is in white. The bresenham algorithm is used to print the two diagonal lines in the middle of the rectangle. Can someone please correct me on my code in order to fix it.

Note:

bx is equivalent to x2 and super.x x1 similarly for y.

image of Output

public void draw( char [][] matrix ) {
    yCoord = super.y;
    xCoord = super.x;
    deltaX = Math.abs(bx - xCoord);
    deltaY = Math.abs(by - yCoord);
    int sx = xCoord < bx ? 1 : -1;
    int sy = yCoord < by ? 1 : -1;
    delta = deltaX - deltaY;
    int err2;

    while (true) {
        matrix[xCoord][yCoord] = '*';
        if (xCoord == bx || yCoord == by) {
            break;
        }
        err2 = 2*delta;
        if (err2 > -deltaY) {
            delta -= deltaY;
            xCoord += sx;
        } else if (err2 < deltaX) {
            delta += deltaX;
            yCoord += sy;
        }

    }

}

I am not sure how as we are using a terminal instead of an IDE for this specific output and have no prior knowledge to using terminals or debugging with them — Senyo, Aug 26 '16 at 12:30
Are you serious ? You are setting the pixels wih asterisks, which have no reason to appear white on black. Fil the image with asterisks and draw with spaces. — , Aug 26 '16 at 12:30
Part of the specificatons of my project. Not much I can do @YvesDaoust — Senyo, Aug 26 '16 at 12:46
@SenyoSenchoraSimpson: no I mean are you serious to be surprised by this behavior which you implemented ? — , Aug 26 '16 at 13:34
You can also debug your code by simply printing values, e.g. using `System.out.println(…)` and then check every value if they are valid and make sense. — Martin Nyolt, Aug 26 '16 at 14:31
You should code/debug on environment capable of it and only then submit code for testing. Your equations/algorithm are wrong ,.. also major_axis/quadrant separation is suspicious as it should not change during line rasterisation (err2) instead it should be dependent only on `if (deltaX>=deltaY)` before the iteration it self ... See https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm for the equations. You should have 2 separate loops one for x-major lines and one for y-major lines .... as you already implement the steps `sx,sy` you do not need to separate to octants — Spektre, Aug 26 '16 at 14:32
If you are lost you might start to code DDA instead Bresenham and when working change to Bresenham as DDA is more simple to understand... see [my integer DDA C++ implementation](http://stackoverflow.com/a/24682318/2521214) it is targeted for special sub-pixel thickening but you will at least have something to compare to (just ignore the subpixel calls) ... how the code could look like — Spektre, Aug 26 '16 at 14:38

score 0 · Answer 1 · answered Aug 26 '16 at 15:29

I found this here and test in java:

static char[][] h(char [][] matrix,int x1,int y1, int x2,int y2){
        int dx  = x2 - x1;
        int dy  = y2 - y1;
        int y   = y1;
        int eps = 0;
        for (int x = x1; x <= x2; x++ )  {
            matrix[y][x]='*';
            eps += dy;
            if ( (eps << 1) >= dx )  {
                y++;
                eps -= dx;
            }
        }
        return matrix;
    }

this

public static void main(String[] args) {
        char[][] input = {
                {' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' '}
        };
        char[][] matrix = h(input,0,0,4,5);
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                System.out.print(matrix[i][j]);
            }
            System.out.println();
        }
    }

gives

this doesn't seem to give the overlap that the other was giving

Bresenham Line Algorithm

1 Answers1