Difference between revisions of "Bresenham's Line Algorithm"
Jump to navigation
Jump to search
Line 1: | Line 1: | ||
Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y): | Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y): | ||
#ifndef ABS | #ifndef ABS | ||
# define ABS(x) ((x)>0?(x):-(x)) | # define ABS(x) ((x)>0?(x):-(x)) | ||
#endif | #endif | ||
//////////////////////////////////////////////////////////////////////////////// | //////////////////////////////////////////////////////////////////////////////// | ||
void Bresenham(unsigned x1, | void Bresenham(unsigned x1, | ||
unsigned y1, | |||
unsigned x2, | |||
unsigned y2) | |||
{ | { | ||
unsigned delta_x = ABS(x2 - x1) << 1; | |||
unsigned delta_y = ABS(y2 - y1) << 1; | |||
// if x1 == x2 or y1 == y2, then it does not matter what we set here | |||
char ix = x2 > x1?1:-1; | |||
char iy = y2 > y1?1:-1; | |||
plot(x1, y1); | |||
if (delta_x >= delta_y) | |||
{ | |||
// error may go below zero | |||
int error = delta_y - (delta_x >> 1); | |||
while (x1 != x2) | |||
{ | |||
if (error >= 0) | |||
{ | |||
if (error || (ix > 0)) | |||
{ | |||
y1 += iy; | |||
error -= delta_x; | |||
} | |||
// else do nothing | |||
} | |||
// else do nothing | |||
x1 += ix; | |||
error += delta_y; | |||
plot(x1, y1); | |||
} | |||
} | |||
else | |||
{ | |||
// error may go below zero | |||
int error = delta_x - (delta_y >> 1); | |||
while (y1 != y2) | |||
{ | |||
if (error >= 0) | |||
{ | |||
if (error || (iy > 0)) | |||
{ | |||
x1 += ix; | |||
error -= delta_y; | |||
} | |||
// else do nothing | |||
} | |||
// else do nothing | |||
y1 += iy; | |||
error += delta_x; | |||
plot(x1, y1); | |||
} | |||
} | |||
} | } | ||
[[Category:Algorithms]] | [[Category:Algorithms]] |
Revision as of 12:09, 3 March 2007
Previous article deleted due to crappiness. Here's an improved C++ version (as in the previous article plot() draws a pixel at (x, y):
#ifndef ABS # define ABS(x) ((x)>0?(x):-(x)) #endif //////////////////////////////////////////////////////////////////////////////// void Bresenham(unsigned x1, unsigned y1, unsigned x2, unsigned y2) { unsigned delta_x = ABS(x2 - x1) << 1; unsigned delta_y = ABS(y2 - y1) << 1; // if x1 == x2 or y1 == y2, then it does not matter what we set here char ix = x2 > x1?1:-1; char iy = y2 > y1?1:-1; plot(x1, y1); if (delta_x >= delta_y) { // error may go below zero int error = delta_y - (delta_x >> 1); while (x1 != x2) { if (error >= 0) { if (error || (ix > 0)) { y1 += iy; error -= delta_x; } // else do nothing } // else do nothing x1 += ix; error += delta_y; plot(x1, y1); } } else { // error may go below zero int error = delta_x - (delta_y >> 1); while (y1 != y2) { if (error >= 0) { if (error || (iy > 0)) { x1 += ix; error -= delta_y; } // else do nothing } // else do nothing y1 += iy; error += delta_x; plot(x1, y1); } } }