Bresenham's Line Algorithm

From RogueBasin
Revision as of 15:30, 24 March 2009 by Bolthar (Talk | contribs)

Jump to: navigation, search

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
Personal tools