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 arrayreturn 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?

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

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

Top