Line of sight
Jump to navigation
Jump to search
Taken from wikipedia: (they will delete this code soon, I thought it might find a welcome home here)
An implementation of Bresenham's line algorithm in C follows. The plot() function is not shown and is assumed to render a single point of the line in the chosen color. This variation produces solid lines of a uniform color.
void drawline2d(int x0, int y0, int x1, int y1, int color) { int i; int steep = 1; int sx, sy; /* step positive or negative (1 or -1) */ int dx, dy; /* delta (difference in X and Y between points) */ int e; /* * inline swap. On some architectures, the XOR trick may be faster */ int tmpswap; #define SWAP(a,b) tmpswap = a; a = b; b = tmpswap; /* * optimize for vertical and horizontal lines here */ dx = abs(x1 - x0); sx = ((x1 - x0) > 0) ? 1 : -1; dy = abs(y1 - y0); sy = ((y1 - y0) > 0) ? 1 : -1; if (dy > dx) { steep = 0; SWAP(x0, y0); SWAP(dx, dy); SWAP(sx, sy); } e = (dy << 1) - dx; for (i = 0; i < dx; i++) { if (steep) { plot(x0,y0,color); } else { plot(y0,x0,color); } while (e >= 0) { y0 += sy; e -= (dx << 1); } x0 += sx; e += (dy << 1); } }
A slightly more optimized version of the above (might be a bit harder to read, though):
void drawline2d(int x0, int y0, int x1, int y1, int color) { int i; int sx, sy; /* step positive or negative (1 or -1) */ int dx, dy; /* delta (difference in X and Y between points) */ int dx2, dy2; int e; int temp; dx = x1 - x0; sx = (dx > 0) ? 1 : -1; if (dx < 0) dx = -dx; dy = y1 - y0; sy = (dy > 0) ? 1 : -1; if (dy < 0) dy = -dy; dx2 = dx << 1; /* dx2 = 2 * dx */ dy2 = dy << 1; /* dy2 = 2 * dy */ if (dy <= dx) { /* steep */ e = dy2 - dx; for (i = 0; i <= dx; ++i) { plot(x0, y0, color); while (e >= 0) { y0 += sy; e -= dx2; } x0 += sx; e += dy2; } } else { /* swap x0 <-> y0 */ temp = x0; x0 = y0; y0 = temp; /* swap dx <-> dy */ temp = dx; dx = dy; dy = temp; /* swap dx2 <-> dy2 */ temp = dx2; dx2 = dy2; dy2 = temp; /* swap sx <-> sy */ temp = sx; sx = sy; sy = temp; e = dy2 - dx; for (i = 0; i <= dx; ++i) { plot(y0, x0, color); while (e >= 0) { y0 += sy; e -= dx2; } x0 += sx; e += dy2; } } }