Bresenham's Line Algorithm
m (→JavaScript) |
|||
(24 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
− | '''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. | + | '''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 [http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html here]. |
In [[libtcod]] it is accessible using <code>line(x1, y1, x2, y2, callback)</code>. Below are several hand-coded implementations in various languages. | In [[libtcod]] it is accessible using <code>line(x1, y1, x2, y2, callback)</code>. Below are several hand-coded implementations in various languages. | ||
Line 90: | Line 90: | ||
while (x1 != x2) | while (x1 != x2) | ||
{ | { | ||
− | if ((error > | + | // reduce error, while taking into account the corner case of error == 0 |
+ | if ((error > 0) || (!error && (ix > 0))) | ||
{ | { | ||
error -= delta_x; | error -= delta_x; | ||
Line 110: | Line 111: | ||
while (y1 != y2) | while (y1 != y2) | ||
{ | { | ||
− | if ((error > | + | // reduce error, while taking into account the corner case of error == 0 |
+ | if ((error > 0) || (!error && (iy > 0))) | ||
{ | { | ||
error -= delta_y; | error -= delta_y; | ||
Line 126: | Line 128: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
− | A template metaprogram implementation (requires the Boost.MPL library) | + | A template metaprogram implementation (requires the Boost.MPL library): |
<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 "boost/mpl/bool.hpp" | ||
+ | #include "boost/mpl/char.hpp" | ||
#include "boost/mpl/for_each.hpp" | #include "boost/mpl/for_each.hpp" | ||
− | #include "boost/mpl/ | + | #include "boost/mpl/bitwise.hpp" |
− | #include "boost/mpl/ | + | #include "boost/mpl/shift_left.hpp" |
#include "boost/mpl/list.hpp" | #include "boost/mpl/list.hpp" | ||
Line 155: | Line 160: | ||
mpl::push_front<typename bresenham_line_pair<N - 1, | mpl::push_front<typename bresenham_line_pair<N - 1, | ||
typename mpl::plus<x1, ix>::type, | typename mpl::plus<x1, ix>::type, | ||
− | typename mpl::if_c<(error::value > | + | typename mpl::if_c<(error::value > 0) |
− | + | || (!error::value && (ix::value > 0)), | |
− | + | mpl::plus<y1, iy>, y1>::type, | |
− | + | ||
delta_x, delta_y, | delta_x, delta_y, | ||
ix, iy, | ix, iy, | ||
− | typename mpl::if_c<(error::value > | + | 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, | swap>::type, | ||
typename mpl::if_<swap, mpl::pair<y1, x1>, mpl::pair<x1, y1> >::type | typename mpl::if_<swap, mpl::pair<y1, x1>, mpl::pair<x1, y1> >::type | ||
Line 183: | Line 186: | ||
template <int x1, int y1, int x2, int y2> | 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_<x2>, mpl::int_<x1> >::type dx; | ||
typedef typename mpl::minus<mpl::int_<y2>, mpl::int_<y1> >::type dy; | typedef typename mpl::minus<mpl::int_<y2>, mpl::int_<y1> >::type dy; | ||
typedef typename mpl::if_<mpl::less<dx, mpl::int_<0> >, | typedef typename mpl::if_<mpl::less<dx, mpl::int_<0> >, | ||
− | mpl:: | + | mpl::char_<-1>, mpl::char_<1> >::type ix; |
typedef typename mpl::if_<mpl::less<dy, mpl::int_<0> >, | typedef typename mpl::if_<mpl::less<dy, mpl::int_<0> >, | ||
− | mpl:: | + | mpl::char_<-1>, mpl::char_<1> >::type iy; |
typedef typename mpl::max<dx, mpl::negate<dx> >::type abs_dx; | 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::max<dy, mpl::negate<dy> >::type abs_dy; | ||
− | typedef typename mpl:: | + | typedef typename mpl::shift_left<abs_dx, mpl::char_<1> >::type delta_x; |
− | typedef typename mpl:: | + | 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>, | typedef typename mpl::if_<mpl::less<delta_x, delta_y>, mpl::bool_<true>, | ||
mpl::bool_<false> >::type swap; | mpl::bool_<false> >::type swap; | ||
− | typedef typename mpl::if_<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::max<abs_dx, abs_dy>::type N; | ||
Line 227: | Line 228: | ||
int main(int, char*[]) | int main(int, char*[]) | ||
{ | { | ||
− | mpl::for_each<bresenham_line<0, 0, | + | mpl::for_each<bresenham_line<0, 0, 20, 10>::sequence_type>(plotter()); |
return 0; | return 0; | ||
} | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | == Lua == | ||
+ | Here's a Lua port: | ||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="lua"> | ||
+ | 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 | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
Line 240: | Line 288: | ||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
− | def get_line( | + | def get_line(start, end): |
− | + | """Bresenham's Line Algorithm | |
− | + | Produces a list of tuples from start and end | |
− | if | + | |
+ | >>> 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 | x1, y1 = y1, x1 | ||
x2, y2 = y2, x2 | x2, y2 = y2, x2 | ||
− | + | ||
+ | # Swap start and end points if necessary and store swap state | ||
+ | swapped = False | ||
if x1 > x2: | if x1 > x2: | ||
x1, x2 = x2, x1 | x1, x2 = x2, x1 | ||
y1, y2 = y2, y1 | y1, y2 = y2, y1 | ||
− | + | swapped = True | |
− | + | ||
− | + | # Recalculate differentials | |
− | error = int( | + | 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 | y = y1 | ||
− | + | points = [] | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
for x in range(x1, x2 + 1): | for x in range(x1, x2 + 1): | ||
− | + | coord = (y, x) if is_steep else (x, y) | |
− | + | points.append(coord) | |
− | + | error -= abs(dy) | |
− | + | ||
− | error -= | + | |
if error < 0: | if error < 0: | ||
y += ystep | y += ystep | ||
− | error += | + | error += dx |
− | # Reverse the list if the coordinates were | + | |
− | if | + | # Reverse the list if the coordinates were swapped |
+ | if swapped: | ||
points.reverse() | points.reverse() | ||
return points | return points | ||
Line 350: | Line 421: | ||
End If | End If | ||
Dim deltaX As Long = x2 - x1 | Dim deltaX As Long = x2 - x1 | ||
− | Dim deltaY As Long = y2 - y1 | + | Dim deltaY As Long = Math.Abs(y2 - y1) |
Dim err As Long = deltaX / 2 | Dim err As Long = deltaX / 2 | ||
Dim ystep As Long | Dim ystep As Long | ||
Line 413: | Line 484: | ||
</div> | </div> | ||
+ | == [[ActionScript]] == | ||
+ | |||
+ | Here's an ActionScript implementation that creates a Line object with an array of points. | ||
+ | |||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="actionscript"> | ||
+ | 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; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | |||
+ | == Go == | ||
+ | |||
+ | This is a translation for golang from the Python example above, it returns a slice to a struct that contains two ints. | ||
+ | |||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="cpp"> | ||
+ | |||
+ | 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 | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | |||
+ | == JavaScript == | ||
+ | |||
+ | Adapted from the C# example above, but improved so line is drawn in original direction. Demo here: [https://jsfiddle.net/vpkbunqt/10/]. | ||
+ | |||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="javascript"> | ||
+ | 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; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | |||
+ | == 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) | ||
+ | |||
+ | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
+ | <syntaxhighlight lang="c"> | ||
+ | #[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 | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
[[Category:Articles]] | [[Category:Articles]] |
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.
Contents |
[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 }