Bresenham's Line Algorithm
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Here's a C++ version; as in the previous article plot() draws a "dot" at (x, y):
#include <cmath>
////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
int y1,
int x2,
int y2)
{
unsigned delta_x = std::abs(x2 - x1) << 1;
unsigned delta_y = std::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);
}
}
}