Line Rasterization / 4-connected Bresenham

Question

For collision testing I need to raster a line. The bresenham algorithm works almost as desired, but has the flaw that is produces a line like:

And I need:

My current implementation (based on http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplification):

public boolean isInsideLine(int x1, int y1, int x2, int y2) {
    final int dx = abs(x2 - x1), dy = abs(y2 - y1);
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1;
    int err = dx - dy;

    while (true) {
        if (isInside(x1, y1)) //Lookup in pixel array
            return true;
        if (x1 == x2 && y1 == y2)
            break;
        final int e2 = err << 1;
        if (e2 > -dy) {
            err -= dy;
            x1 += sx;
        }
        if (e2 < dx) {
            err += dx;
            y1 += sy;
        }
    }
    return false;
}

Is there an other line rasterization algorithm I could use, or does anyone know how modify the bresenham?

Airlia

It seems to me that the raw output of Bresenham is 8-connected but you require 4-connected. You could do a post processing of the raw output to detect a diagonal link and then decide which pixel the line is closest to. – Pond

See #5187439 for what looks like the same question. – Pond

Out of interest: why do you need to rasterize a line for collision detection? Can't you just calculate intersections? – Bandurria

It's for (nearly) pixel exact 2d collision. – Airlia

Answer 1

Thanks koan, sometimes you just lack the keywords to search for, Algorithm for drawing a 4-connected line seems to solve it:

public boolean isInsideLine(int x1, int y1, int x2, int y2) {
    final int dx = abs(x2 - x1), dy = abs(y2 - y1);
    final int sx = x1 < x2 ? 1 : -1, sy = y1 < y2 ? 1 : -1;
    int err = dx - dy;

    while (true) {
        if (isInside(x1, y1)) //Lookup in pixel array
            return true;
        if (x1 == x2 && y1 == y2)
            break;
        final int e2 = err << 1;
        if (e2 > -dy) {
            err -= dy;
            x1 += sx;
        } else if (e2 < dx) { // else if instead of if
            err += dx;
            y1 += sy;
        }
    }
    return false;
}

Airlia

Answer 2

Maybe it will be usefull, there is my version for non-integer end points. It is a method of GridMap class which I use for spacial indexing of geometric shapes in order to accelerate collision detection in 2D map.

int GridMap::insertLine( int lineId, double ax, double ay, double bx, double by ){
    // get index of endpoints in GridMap
    int ix    = getIx( ax ); 
    int iy    = getIy( ay );
    int ixb   = getIx( bx );
    int iyb   = getIy( by );
    // insert endpoints to GridMap
    insert( lineId, ix, iy   ); 
    insert( lineId, ixb, iyb );
    // raster central part of the line
    double dx = fabs( bx - ax );
    double dy = fabs( by - ay );
    int dix = ( ax < bx ) ? 1 : -1;
    int diy = ( ay < by ) ? 1 : -1;
    double x=0, y=0;
    while ( ( ix != ixb ) && ( iy != iyb  ) ) {
        if ( x < y ) {
            x  += dy;
            ix += dix;
        } else {
            y  += dx;
            iy += diy;
        }
        insert( lineId, ix, iy );
    }
};

Terracotta

Does not work. For starters, if the starting point and ending point fall in the same grid square, the line will be added twice to the same grid square. Secondly, it does not work for horizontal/vertical lines: For an horizontal line, iy will be equal to iyb. The content of the while loop will never be executed: because iy != iyb will never be true. In fact it's worse than just horizontal/vertical lines not working. That piece of code simply does not correctly draw the ending of any line that is not a diagonal. The closer to horizontal/vertical, the more pixels it will be missing. – Altar