Bresenham's Line Algorithm

Latest revision as of 16:59, 2 June 2018

Bresenham's Line Algorithm is a way of drawing a line segment onto a square grid. It is especially useful for roguelikes due to their cellular nature. A detailed explanation of the algorithm can be found here.

In libtcod it is accessible using line(x1, y1, x2, y2, callback). Below are several hand-coded implementations in various languages.

[edit] C#

Here is a simple way of using the algorithm in C# with delegates.

// Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)
using System;
 
namespace Bresenhams
{
    /// <summary>
    /// The Bresenham algorithm collection
    /// </summary>
    public static class Algorithms
    {
        private static void Swap<T>(ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; }
 
        /// <summary>
        /// The plot function delegate
        /// </summary>
        /// <param name="x">The x co-ord being plotted</param>
        /// <param name="y">The y co-ord being plotted</param>
        /// <returns>True to continue, false to stop the algorithm</returns>
        public delegate bool PlotFunction(int x, int y);
 
        /// <summary>
        /// Plot the line from (x0, y0) to (x1, y10
        /// </summary>
        /// <param name="x0">The start x</param>
        /// <param name="y0">The start y</param>
        /// <param name="x1">The end x</param>
        /// <param name="y1">The end y</param>
        /// <param name="plot">The plotting function (if this returns false, the algorithm stops early)</param>
        public static void Line(int x0, int y0, int x1, int y1, PlotFunction plot)
        {
            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
            if (steep) { Swap<int>(ref x0, ref y0); Swap<int>(ref x1, ref y1); }
            if (x0 > x1) { Swap<int>(ref x0, ref x1); Swap<int>(ref y0, ref y1); }
            int dX = (x1 - x0), dY = Math.Abs(y1 - y0), err = (dX / 2), ystep = (y0 < y1 ? 1 : -1), y = y0;
 
            for (int x = x0; x <= x1; ++x)
            {
                if (!(steep ? plot(y, x) : plot(x, y))) return;
                err = err - dY;
                if (err < 0) { y += ystep;  err += dX; }
            }
        }
    }
}

[edit] C++

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

#include <cstdlib>
 
////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
    int y1,
    int const x2,
    int const y2)
{
    int delta_x(x2 - x1);
    // if x1 == x2, then it does not matter what we set here
    signed char const ix((delta_x > 0) - (delta_x < 0));
    delta_x = std::abs(delta_x) << 1;
 
    int delta_y(y2 - y1);
    // if y1 == y2, then it does not matter what we set here
    signed char const iy((delta_y > 0) - (delta_y < 0));
    delta_y = std::abs(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)
        {
            // reduce error, while taking into account the corner case of error == 0
            if ((error > 0) || (!error && (ix > 0)))
            {
                error -= delta_x;
                y1 += iy;
            }
            // else do nothing
 
            error += delta_y;
            x1 += ix;
 
            plot(x1, y1);
        }
    }
    else
    {
        // error may go below zero
        int error(delta_x - (delta_y >> 1));
 
        while (y1 != y2)
        {
            // reduce error, while taking into account the corner case of error == 0
            if ((error > 0) || (!error && (iy > 0)))
            {
                error -= delta_y;
                x1 += ix;
            }
            // else do nothing
 
            error += delta_x;
            y1 += iy;
 
            plot(x1, y1);
        }
    }
}

A template metaprogram implementation (requires the Boost.MPL library):

#include "boost/mpl/bool.hpp"
#include "boost/mpl/char.hpp"
 
#include "boost/mpl/for_each.hpp"
 
#include "boost/mpl/bitwise.hpp"
#include "boost/mpl/shift_left.hpp"
 
#include "boost/mpl/list.hpp"
#include "boost/mpl/push_front.hpp"
 
#include "boost/mpl/max.hpp"
 
#include "boost/mpl/minus.hpp"
#include "boost/mpl/arithmetic.hpp"
 
#include "boost/mpl/pair.hpp"
 
namespace mpl = boost::mpl;
 
template <std::size_t N,
  typename x1, typename y1,
  typename delta_x, typename delta_y,
  typename ix, typename iy,
  typename error, typename swap>
struct bresenham_line_pair :
  mpl::push_front<typename bresenham_line_pair<N - 1,
    typename mpl::plus<x1, ix>::type,
    typename mpl::if_c<(error::value > 0)
      || (!error::value && (ix::value > 0)),
      mpl::plus<y1, iy>, y1>::type,
    delta_x, delta_y,
    ix, iy,
    typename mpl::if_c<(error::value > 0)
      || (!error::value && (ix::value > 0)),
      mpl::minus<mpl::plus<error, delta_y>, delta_x>,
      mpl::plus<error, delta_y> >::type,
    swap>::type,
    typename mpl::if_<swap, mpl::pair<y1, x1>, mpl::pair<x1, y1> >::type
  >
{
};
 
template <typename x1, typename y1,
  typename delta_x, typename delta_y,
  typename ix, typename iy,
  typename error, typename swap>
struct bresenham_line_pair<0, x1, y1, delta_x, delta_y, ix, iy, error, swap> :
  mpl::list<typename mpl::if_<swap, mpl::pair<y1, x1>,
    mpl::pair<x1, y1> >::type>
{
};
 
template <int x1, int y1, int x2, int y2>
struct bresenham_line
{
  typedef typename mpl::minus<mpl::int_<x2>, mpl::int_<x1> >::type dx;
  typedef typename mpl::minus<mpl::int_<y2>, mpl::int_<y1> >::type dy;
 
  typedef typename mpl::if_<mpl::less<dx, mpl::int_<0> >,
    mpl::char_<-1>, mpl::char_<1> >::type ix;
  typedef typename mpl::if_<mpl::less<dy, mpl::int_<0> >,
    mpl::char_<-1>, mpl::char_<1> >::type iy;
 
  typedef typename mpl::max<dx, mpl::negate<dx> >::type abs_dx;
  typedef typename mpl::max<dy, mpl::negate<dy> >::type abs_dy;
 
  typedef typename mpl::shift_left<abs_dx, mpl::char_<1> >::type delta_x;
  typedef typename mpl::shift_left<abs_dy, mpl::char_<1> >::type delta_y;
 
  typedef typename mpl::if_<mpl::less<delta_x, delta_y>, mpl::bool_<true>,
    mpl::bool_<false> >::type swap;
 
  typedef typename mpl::if_<swap, mpl::minus<delta_x, abs_dy>,
    mpl::minus<delta_y, abs_dx> >::type error;
 
  typedef typename mpl::max<abs_dx, abs_dy>::type N;
 
  typedef typename mpl::if_<swap,
    bresenham_line_pair<N::value, mpl::int_<y1>, mpl::int_<x1>,
      delta_y, delta_x, iy, ix, error, swap>,
    bresenham_line_pair<N::value, mpl::int_<x1>, mpl::int_<y1>,
      delta_x, delta_y, ix, iy, error, swap> >::type::type sequence_type;
};
 
struct plotter
{
  template<typename T>
  inline void operator()(T)
  {
    plot(T::first::type::value, T::second::type::value);
  }
};
 
int main(int, char*[])
{
  mpl::for_each<bresenham_line<0, 0, 20, 10>::sequence_type>(plotter());
 
  return 0;
}

[edit] Lua

Here's a Lua port:

function bresenham(x1, y1, x2, y2)
  delta_x = x2 - x1
  ix = delta_x > 0 and 1 or -1
  delta_x = 2 * math.abs(delta_x)
 
  delta_y = y2 - y1
  iy = delta_y > 0 and 1 or -1
  delta_y = 2 * math.abs(delta_y)
 
  plot(x1, y1)
 
  if delta_x >= delta_y then
    error = delta_y - delta_x / 2
 
    while x1 ~= x2 do
      if (error > 0) or ((error == 0) and (ix > 0)) then
        error = error - delta_x
        y1 = y1 + iy
      end
 
      error = error + delta_y
      x1 = x1 + ix
 
      plot(x1, y1)
    end
  else
    error = delta_x - delta_y / 2
 
    while y1 ~= y2 do
      if (error > 0) or ((error == 0) and (iy > 0)) then
        error = error - delta_y
        x1 = x1 + ix
      end
 
      error = error + delta_x
      y1 = y1 + iy
 
      plot(x1, y1)
    end
  end
end

[edit] Python

This Python version returns a list of (x, y) tuples. It was converted from the Ruby version below, but also reverses the list to begin with the first coordinates.

def get_line(start, end):
    """Bresenham's Line Algorithm
    Produces a list of tuples from start and end
 
    >>> points1 = get_line((0, 0), (3, 4))
    >>> points2 = get_line((3, 4), (0, 0))
    >>> assert(set(points1) == set(points2))
    >>> print points1
    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
    >>> print points2
    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
    """
    # Setup initial conditions
    x1, y1 = start
    x2, y2 = end
    dx = x2 - x1
    dy = y2 - y1
 
    # Determine how steep the line is
    is_steep = abs(dy) > abs(dx)
 
    # Rotate line
    if is_steep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2
 
    # Swap start and end points if necessary and store swap state
    swapped = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        swapped = True
 
    # Recalculate differentials
    dx = x2 - x1
    dy = y2 - y1
 
    # Calculate error
    error = int(dx / 2.0)
    ystep = 1 if y1 < y2 else -1
 
    # Iterate over bounding box generating points between start and end
    y = y1
    points = []
    for x in range(x1, x2 + 1):
        coord = (y, x) if is_steep else (x, y)
        points.append(coord)
        error -= abs(dy)
        if error < 0:
            y += ystep
            error += dx
 
    # Reverse the list if the coordinates were swapped
    if swapped:
        points.reverse()
    return points

[edit] Ruby

Here's a Ruby version, it returns an array of points, each being a 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

[edit] VB.NET

Here is a generic way of using the algorithm in VB.NET using delegates.

' Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)
 
Module BresenhamsLineAlgorithm
    Sub Swap(ByRef X As Long, ByRef Y As Long)
        Dim t As Long = X
        X = Y
        Y = t
    End Sub
    ' If the plot function returns true, the bresenham's line algorithm continues.
    ' if the plot function returns false, the algorithm stops
    Delegate Function PlotFunction(ByVal x As Long, ByVal y As Long) As Boolean
    Sub Bresenham(ByVal x1 As Long, ByVal y1 As Long, ByVal x2 As Long, ByVal y2 As Long, ByVal plot As PlotFunction)
        Dim steep As Boolean = (Math.Abs(y2 - y1) > Math.Abs(x2 - x1))
        If (steep) Then
            Swap(x1, y1)
            Swap(x2, y2)
        End If
        If (x1 > x2) Then
            Swap(x1, x2)
            Swap(y1, y2)
        End If
        Dim deltaX As Long = x2 - x1
        Dim deltaY As Long = Math.Abs(y2 - y1)
        Dim err As Long = deltaX / 2
        Dim ystep As Long
        Dim y As Long = y1
        If (y1 < y2) Then
            ystep = 1
        Else
            ystep = -1
       End If
       For x As Long = x1 To x2
            Dim result As Boolean
            If (steep) Then result = plot(y, x) Else result = plot(x, y)
            If (Not result) Then Exit Sub
            err = err - deltaY
            If (err < 0) Then
                y = y + ystep
                err = err + deltaX
            End If
       Next
    End Sub
    Function plot(ByVal x As Long, ByVal y As Long) As Boolean
        Console.WriteLine(x.ToString() + " " + y.ToString())
        Return True 'This just prints each co-ord
    End Function
    Sub Main()
        ' example
        Bresenham(1, 1, 10, 15, New PlotFunction(AddressOf plot))
        Console.ReadLine()
    End Sub
End Module

[edit] Haskell

A slightly verbose version in Haskell. See the discussion page for a variant one line shorter, but IMHO less readable. I bet other version, more readable and more succinct, can be written.

-- | See <http://roguebasin.roguelikedevelopment.org/index.php/Digital_lines>.
balancedWord :: Int -> Int -> Int -> [Int]
balancedWord p q eps | eps + p < q = 0 : balancedWord p q (eps + p)
balancedWord p q eps               = 1 : balancedWord p q (eps + p - q)
 
-- | Bresenham's line algorithm.
-- Includes the first point and goes through the second to infinity.
bla :: (Int, Int) -> (Int, Int) -> [(Int, Int)]
bla (x0, y0) (x1, y1) =
  let (dx, dy) = (x1 - x0, y1 - y0)
      xyStep b (x, y) = (x + signum dx,     y + signum dy * b)
      yxStep b (x, y) = (x + signum dx * b, y + signum dy)
      (p, q, step) | abs dx > abs dy = (abs dy, abs dx, xyStep)
                   | otherwise       = (abs dx, abs dy, yxStep)
      walk w xy = xy : walk (tail w) (step (head w) xy)
  in  walk (balancedWord p q 0) (x0, y0)

[edit] ActionScript

Here's an ActionScript implementation that creates a Line object with an array of points.

package  
{
        import flash.geom.Point;
 
	public class Line 
	{
		public var points:Array = [];
 
		public function Line(x0:int, y0:int, x1:int, y1:int) {
			calculate(x0, y0, x1, y1);
		}
 
		private function calculate(x0:int, y0:int, x1:int, y1:int):void {
			var dx:int = Math.abs(x1 - x0);
			var dy:int = Math.abs(y1 - y0);
			var sx:int = x0 < x1 ? 1 : -1;
			var sy:int = y0 < y1 ? 1 : -1;
			var err:int = dx - dy;
 
			while (true){
				points.push(new Point(x0, y0));
 
				if (x0==x1 && y0==y1)
					break;
 
				var e2:int = err * 2;
				if (e2 > -dx) {
					err -= dy;
					x0 += sx;
				}
				if (e2 < dx){
					err += dx;
					y0 += sy;
				}
			}
		}
	}
}

[edit] Go

This is a translation for golang from the Python example above, it returns a slice to a struct that contains two ints.

type Vector2i struct {
	X, Y int
}
 
func getLine(pos1, pos2 Vector2i) (points []Vector2i) {
	x1, y1 := pos1.X, pos1.Y
	x2, y2 := pos2.X, pos2.Y
 
	isSteep := abs(y2-y1) > abs(x2-x1)
	if isSteep {
		x1, y1 = y1, x1
		x2, y2 = y2, x2
	}
 
	reversed := false
	if x1 > x2 {
		x1, x2 = x2, x1
		y1, y2 = y2, y1
		reversed = true
	}
 
	deltaX := x2 - x1
	deltaY := abs(y2 - y1)
	err := deltaX / 2
	y := y1
	var ystep int
 
	if y1 < y2 {
		ystep = 1
	} else {
		ystep = -1
	}
 
	for x := x1; x < x2+1; x++ {
		if isSteep {
			points = append(points, Vector2i{y, x})
		} else {
			points = append(points, Vector2i{x, y})
		}
		err -= deltaY
		if err < 0 {
			y += ystep
			err += deltaX
		}
	}
 
	if reversed {
		//Reverse the slice
		for i, j := 0, len(points)-1; i < j; i, j = i+1, j-1 {
			points[i], points[j] = points[j], points[i]
		}
	}
 
	return
}
 
func abs(x int) int {
	switch {
	case x < 0:
		return -x
	case x == 0:
		return 0
	}
	return x
}

[edit] JavaScript

Adapted from the C# example above, but improved so line is drawn in original direction. Demo here: [1].

function drawline(x0,y0,x1,y1){
  var tmp;
  var steep = Math.abs(y1-y0) > Math.abs(x1-x0);
  if(steep){
    //swap x0,y0
    tmp=x0; x0=y0; y0=tmp;
 
    //swap x1,y1
    tmp=x1; x1=y1; y1=tmp;
  }
 
  var sign = 1;
  if(x0>x1){
    sign = -1;
    x0 *= -1;
    x1 *= -1;
  }
  var dx = x1-x0;
  var dy = Math.abs(y1-y0);
  var err = ((dx/2));
  var ystep = y0 < y1 ? 1:-1;
  var y = y0;
 
  for(var x=x0;x<=x1;x++){
    if(!(steep ? plot(y,sign*x) : plot(sign*x,y))) return;
    err = (err - dy);
    if(err < 0){
      y+=ystep;
      err+=dx;
    }
  }
}

[edit] Rust

This is a translation for Rust from the Go example above, it returns a Vec of structs that contains two ints. (tested rustc ver 1.14.0)

#[derive(Copy, Clone, Debug)]
struct Point2d{
    pub x: u32,
    pub y: u32
}
fn get_line(a: Point2d, b: Point2d) -> Vec<Point2d> {
    let mut points = Vec::<Point2d>::new();
    let mut x1 = a.x as i32;
    let mut y1 = a.y as i32;
    let mut x2 = b.x as i32;
    let mut y2 = b.y as i32;
    let is_steep = (y2-y1).abs() > (x2-x1).abs();
    if is_steep {
        std::mem::swap(&mut x1, &mut y1);
        std::mem::swap(&mut x2, &mut y2);
    }
    let mut reversed = false;
    if x1 > x2 {
        std::mem::swap(&mut x1, &mut x2);
        std::mem::swap(&mut y1, &mut y2);   
        reversed = true;
    }
    let dx = x2 - x1;
    let dy = (y2 - y1).abs();
    let mut err = dx / 2;
    let mut y = y1;
    let ystep: i32;
    if y1 < y2 {
        ystep = 1;
    } else {
        ystep = -1;
    }
    for x in x1..(x2+1) {
        if is_steep {
            points.push(Point2d{x:y as u32, y:x as u32});
        } else {
            points.push(Point2d{x:x as u32, y:y as u32});
        }
        err -= dy;
        if err < 0 {
            y += ystep;
            err += dx;
        }
    }
 
    if reversed {
        for i in 0..(points.len()/2) {
            let end = points.len()-1;
            points.swap(i, end-i);
        }
    }
    points
}

Bresenham's Line Algorithm

Latest revision as of 16:59, 2 June 2018

Contents

[edit] C#

[edit] C++

[edit] Lua

[edit] Python

[edit] Ruby

[edit] VB.NET

[edit] Haskell

[edit] ActionScript

[edit] Go

[edit] JavaScript

[edit] Rust

Views

Personal tools

Navigation

Search

Tools