# Bresenham's Line Algorithm

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