## 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.

Pages: 1 2

added this to digg cerkiner.tk

A Python solution using curses library:

[…] Pages: 1 2 […]