Line Rasterization / 4-connected Bresenham

5
votes

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?

2
javarasterrasterizingbresenham
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. – koan
See stackoverflow.com/questions/5186939/… for what looks like the same question. – koan
Out of interest: why do you need to rasterize a line for collision detection? Can't you just calculate intersections? – Axel
It's for (nearly) pixel exact 2d collision. – DiddiZ

2 Answers

3
votes

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 );
    }
};
1
votes

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;
}