Breshenham’s Line-Drawing Algorithm
July 17, 2012
The algorithm that raster graphics devices use to draw straight lines was invented by Jack Breshenham of IBM in 1962. The algorithm is favored because it uses only simple arithmetic, addition and subtraction and multiplication by 2, making it suitable both for software (graphics libraries, or languages such as PostScript) and for hardware (graphics cards, video displays, plotters).
Assume coordinates with point (0,0) at the top left, increasing down and right, where the first coordinate is the column and the second coordinate is the row, that all pixels have integer coordinates, and the task is to draw a line from (x0, y0) to (x1, y1). Assume for the moment a line that slopes downward from left to right (so both x and y are increasing) at less than a 45 degree angle (so y increases faster than x). For each x from x0 to x1, the algorithm chooses the y between y0 and y1 that is closest to the ideal y for the corresponding x. But instead of computing fractional y, the algorithm keeps track of the error between the current value of y and its idealized value. At each increase in x, the error is increased by the slope of the line, and if the error exceeds half a pixel, y increases by 1 and the error decreases by 1. Similar calculations can be made for other orientations of the line.
Your task is to write a function that implements Breshenham’s line-drawing algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
#include <iostream> #include <cstdlib> #include <functional> void DrawLine( int x0, int y0, int x1, int y1, std::function<void(int,int)> setpixel ) { int absDx = abs(x1 - x0); int absDy = abs(y1 - y0 ); bool xySwapped = false; if( absDy > absDx ) { xySwapped = true; std::swap( x0, y0 ); std::swap( x1, y1 ); std::swap( absDx, absDy ); } int xStep = ( x0 > x1 ) ? -1 : 1; int yStep = ( y0 > y1 ) ? -1 : 1; int err = absDx / 2; for(;;) { if( xySwapped ) setpixel(y0,x0); else setpixel(x0,y0); if( x0 == x1 ) break; err -= absDy; if( err < 0 ) { y0 += yStep; err += absDx; } x0 += xStep; } } int main( int argc, char**argv ) { std::cout << "DrawLine(0,0,10,12)" << std::endl; DrawLine(0,0,10,12,[](int x, int y){ std::cout << x << " " << y << std::endl; } ); std::cout << std::endl; return 0; }added this to digg cerkiner.tk
A Python solution using curses library:
import curses def breshenham(x0, y0, x1, y1, fn): dx = abs(x1 - x0) dy = abs(y1 - y0) sx = 1 if x0 < x1 else -1 sy = 1 if y0 < y1 else -1 err = dx - dy while x0 != x1 and y0 != y1: fn(x0, y0) err2 = err * 2 if err2 > -dy: err -= dy x0 += sx if err2 < dx: err += dx y0 += sy def draw_line(screen, x0, y0, x1, y1): def putpixel(x, y): screen.addch(y, x, '*') screen.border() breshenham(x0, y0, x1, y1, putpixel) screen.getch() curses.wrapper(draw_line, 5, 5, 20, 20)[…] Pages: 1 2 […]