Difference between revisions of "Bresenham's Line Algorithm"

From RogueBasin
Jump to navigation Jump to search
(use syntax highlighting for the code example)
Line 5: Line 5:
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
<syntaxhighlight lang="cpp">
<syntaxhighlight lang="cpp">
#include <cmath>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
void Bresenham(int x1,
Line 13: Line 11:
     int y2)
     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
     // if x1 == x2 or y1 == y2, then it does not matter what we set here
     signed char ix = x2 > x1?1:-1;
     signed char ix = x2 > x1?1:-1;
     signed char iy = y2 > y1?1:-1;
     signed char iy = y2 > y1?1:-1;
    int delta_x = ix > 0?x2 - x1:x1 - x2;
    int delta_y = iy > 0?y2 - y1:y1 - y2;
    delta_x <<= 1;
    delta_y <<= 1;


     plot(x1, y1);
     plot(x1, y1);

Revision as of 19:16, 26 April 2010

C++

Here's a C++ version; plot() draws a "dot" at (x, y):

////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
    int y1,
    int x2,
    int y2)
{
    // 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;

    int delta_x = ix > 0?x2 - x1:x1 - x2;
    int delta_y = iy > 0?y2 - y1:y1 - y2;

    delta_x <<= 1;
    delta_y <<= 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);
        }
    }
}


Ruby

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