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) { int delta_x = std::abs(x2 - x1) << 1; int delta_y = std::abs(y2 - y1) << 1; // if x1 == x2 or y1 == y2, then it does not matter what we set here signed char ix = x2 > x1?1:-1; signed 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); } } }
And here 's a Ruby version, it returns an array of points, each being an hash with 2 elements (x and y)
def get_line(x0,x1,y0,y1) points = [] steep = ((y1-y0).abs) > ((x1-x0).abs) if steep x0,y0 = y0,x0 x1,y1 = y1,x1 end if x0 > x1 x0,x1 = x1,x0 y0,y1 = y1,y0 end deltax = x1-x0 deltay = (y1-y0).abs error = (deltax / 2).to_i y = y0 ystep = nil if y0 < y1 ystep = 1 else ystep = -1 end for x in x0..x1 if steep points << {:x => y, :y => x} else points << {:x => x, :y => y} end error -= deltay if error < 0 y += ystep error += deltax end end return points end