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 13: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
Retrieved from "http://roguebasin.roguelikedevelopment.org/index.php?title=Bresenham%27s_Line_Algorithm&oldid=20712"
Personal tools