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.

About these ads

Pages: 1 2

4 Responses to “Breshenham’s Line-Drawing Algorithm”

  1. madscifi said
    #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;
    }
    
  2. added this to digg cerkiner.tk

  3. 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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: