Breshenham’s Line-Drawing Algorithm
July 17, 2012
The program is easier to write than the description makes it sound. The trick is to parameterize all of the various combinations of plusses and minusses that appear in the different ways that a line can be oriented:
(define (line x0 y0 x1 y1)
(let* ((dx (abs (- x1 x0))) (sx (if (< x0 x1) 1 -1))
(dy (abs (- y1 y0))) (sy (if (< y0 y1) 1 -1))
(err (- dx dy)))
(let loop ((x0 x0) (y0 y0) (err err))
(set-pixel x0 y0)
(when (not (and (= x0 x1) (= y0 y1)))
(let* ((e2 (* err 2))
(err (if (> e2 (- dy)) (- err dy) err))
(x0 (if (> e2 (- dy)) (+ x0 sx) x0))
(err (if (< e2 dx) (+ err dx) err))
(y0 (if (< e2 dx) (+ y0 sy) y0)))
(loop x0 y0 err))))))
Here dx and dy are the total rise and run of the line, and sx and sy give the direction of increase; these parameters never change. Then err and e2 are the current error and twice the error (because it is easier to double the error than deal with fractions), and the loop resets x0 and/or y0 each time through. We demonstrate Breshenham’s algorithm with this function that draws an enclosed polygon:
(define (draw poly)
(cls)
(let ((start (car poly)))
(do ((poly poly (cdr poly)))
((null? (cdr poly))
(line (caar poly) (cadar poly)
(car start) (cadr start)))
(line (caar poly) (cadar poly)
(caadr poly) (cadadr poly))))
(read-char) (goto 0 0) (cls) (if #f #f))
Here’s an example:
> (draw '((19 0) (30 24) (5 8) (33 8) (8 24)))
*
* *
* *
* *
* *
* *
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * *
* * * *
* * * * * *
* * * * * *
* *
* * * * * *
* * * *
* * * * * *
* * *
* * * * * *
* * * *
* * * * * *
* * * * * *
* * * *
* * * * * *
* *
We used the ansi terminal escape sequences from a previous exercise. You can see the program at http://programmingpraxis.codepad.org/jr6LEI0M.
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 […]