Bresenham's Line Algorithm

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(use syntax highlighting for the code example)
Line 1: Line 1:
Here's a C++ version; as in the previous article plot() draws a "dot" at (x, y):
+
== C++ ==
  
#include <cmath>
+
Here's a C++ version; plot() draws a "dot" at (x, y):
 +
 
 +
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
 +
<syntaxhighlight lang="cpp">
 +
#include <cmath>
 
   
 
   
////////////////////////////////////////////////////////////////////////////////
+
////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
+
void Bresenham(int x1,
    int y1,
+
    int y1,
    int x2,
+
    int x2,
    int y2)
+
    int y2)
{
+
{
    int delta_x = std::abs(x2 - x1) << 1;
+
    int delta_x = std::abs(x2 - x1) << 1;
    int delta_y = std::abs(y2 - y1) << 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);
 
   
 
   
    // if x1 == x2 or y1 == y2, then it does not matter what we set here
+
        while (x1 != x2)
    signed char ix = x2 > x1?1:-1;
+
        {
    signed char iy = y2 > y1?1:-1;
+
            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);
+
            plot(x1, y1);
+
        }
    if (delta_x >= delta_y)
+
    }
    {
+
}
        // error may go below zero
+
</syntaxhighlight>
        int error = delta_y - (delta_x >> 1);
+
</div>
+
        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)
 
  
 +
== Ruby ==
  
  def get_line(x0,x1,y0,y1)
+
And here 's a Ruby version, it returns an array of points, each being an hash with 2 elements (x and y).
    points = []
+
 
    steep = ((y1-y0).abs) > ((x1-x0).abs)
+
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
 +
<syntaxhighlight lang="ruby">
 +
 
 +
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
 
     if steep
       x0,y0 = y0,x0
+
       points << {:x => y, :y => x}
      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
 
     else
       ystep = -1
+
       points << {:x => x, :y => y}
 
     end
 
     end
     for x in x0..x1
+
     error -= deltay
      if steep
+
    if error < 0
        points << {:x => y, :y => x}
+
      y += ystep
      else
+
      error += deltax
        points << {:x => x, :y => y}
+
      end
+
      error -= deltay
+
      if error < 0
+
        y += ystep
+
        error += deltax
+
      end
+
 
     end
 
     end
    return points
 
 
   end
 
   end
 +
  return points
 +
end
 +
 +
</syntaxhighlight>
 +
</div>
  
 
[[Category:Articles]]
 
[[Category:Articles]]

Revision as of 14:09, 5 April 2010

C++

Here's a C++ version; 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);
        }
    }
}


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