Difference between revisions of "Bresenham's Line Algorithm"
HexDecimal (talk | contribs) (Fix small regression in Python example, error should be an int type) |
|||
(66 intermediate revisions by 19 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. A detailed explanation of the algorithm can be found [http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html here] or [https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm on Wikipedia] | |||
#include < | Below are several hand-coded implementations in various languages. | ||
== C# == | |||
Here is a simple way of using the algorithm in C# with delegates. | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="csharp"> | |||
// 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; } | |||
} | |||
} | |||
} | |||
} | |||
</syntaxhighlight> | |||
</div> | |||
== C++ == | |||
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 <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); | |||
} | |||
} | |||
} | |||
</syntaxhighlight> | |||
</div> | |||
A template metaprogram implementation (requires the Boost.MPL library): | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="cpp"> | |||
#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; | |||
} | |||
</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> | |||
</div> | |||
== 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. | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="python"> | |||
def bresenham_line(start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]]: | |||
"""Return a list of coordinates from `start` to `end` including both endpoints. | |||
This implementation is symmetrical. It uses the same set of coordinates in either direction. | |||
>>> bresenham_line((0, 0), (3, 4)) | |||
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)] | |||
>>> bresenham_line((3, 4), (0, 0)) | |||
[(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 = dx // 2 | |||
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 | |||
</syntaxhighlight> | |||
</div> | |||
== Ruby == | |||
Here's a Ruby version, it returns an array of points, each being a hash with 2 elements (x and y). | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="ruby"> | |||
def get_line(x0,x1,y0,y1) | 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 | ||
points << {:x => y, :y => x} | |||
else | else | ||
points << {:x => x, :y => y} | |||
end | end | ||
error -= deltay | |||
if error < 0 | |||
y += ystep | |||
error += deltax | |||
end | end | ||
end | end | ||
return points | |||
end | |||
</syntaxhighlight> | |||
</div> | |||
== VB.NET == | |||
Here is a generic way of using the algorithm in VB.NET using delegates. | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="vbnet"> | |||
' 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 | |||
</syntaxhighlight> | |||
</div> | |||
== [[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. | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="haskell"> | |||
-- | 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) | |||
</syntaxhighlight> | |||
</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> | |||
== GDScript == | |||
Adapted from python example above, it returns an Array of Vector2i. | |||
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | |||
<syntaxhighlight lang="gdscript"> | |||
# Bresenham's Line Algorithm | |||
func get_line(start:Vector2i, end:Vector2i)->Array[Vector2i]: | |||
# Setup initial conditions | |||
var x1: float = start.x | |||
var y1: float = start.y | |||
var x2: float = end.x | |||
var y2: float = end.y | |||
var dx: float = x2 - x1 | |||
var dy: float = y2 - y1 | |||
# Determine how steep the line is | |||
var is_steep = abs(dy) > abs(dx) | |||
var swap_var = 0.0 | |||
# Rotate line | |||
if is_steep: | |||
swap_var = x1 | |||
x1 = y1 | |||
y1 = swap_var | |||
swap_var = x2 | |||
x2 = y2 | |||
y2 = swap_var | |||
# Swap start and end points if necessary and store swap state | |||
var swapped := false | |||
if x1 > x2: | |||
swap_var = x1 | |||
x1 = x2 | |||
x2 = swap_var | |||
swap_var = y1 | |||
y1 = y2 | |||
y2 = swap_var | |||
swapped = true | |||
# Recalculate differentials | |||
dx = x2 - x1 | |||
dy = y2 - y1 | |||
# Calculate error | |||
var error: float = floor(dx / 2.0) # Try int | |||
var ystep = 1 if y1 < y2 else -1 | |||
# Iterate over bounding box generating points between start and end | |||
var y = y1 | |||
var points: Array[Vector2i] = [] | |||
for x in range(x1, x2 + 1): | |||
var coord = Vector2i(y, x) if is_steep else Vector2i(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 | |||
</syntaxhighlight> | |||
</div> | |||
[[Category:Articles]] | [[Category:Articles]] |
Latest revision as of 02:44, 7 August 2023
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 or on Wikipedia
Below are several hand-coded implementations in various languages.
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; }
}
}
}
}
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;
}
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
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 bresenham_line(start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]]:
"""Return a list of coordinates from `start` to `end` including both endpoints.
This implementation is symmetrical. It uses the same set of coordinates in either direction.
>>> bresenham_line((0, 0), (3, 4))
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
>>> bresenham_line((3, 4), (0, 0))
[(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 = dx // 2
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
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
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
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)
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;
}
}
}
}
}
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
}
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;
}
}
}
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
}
GDScript
Adapted from python example above, it returns an Array of Vector2i.
# Bresenham's Line Algorithm
func get_line(start:Vector2i, end:Vector2i)->Array[Vector2i]:
# Setup initial conditions
var x1: float = start.x
var y1: float = start.y
var x2: float = end.x
var y2: float = end.y
var dx: float = x2 - x1
var dy: float = y2 - y1
# Determine how steep the line is
var is_steep = abs(dy) > abs(dx)
var swap_var = 0.0
# Rotate line
if is_steep:
swap_var = x1
x1 = y1
y1 = swap_var
swap_var = x2
x2 = y2
y2 = swap_var
# Swap start and end points if necessary and store swap state
var swapped := false
if x1 > x2:
swap_var = x1
x1 = x2
x2 = swap_var
swap_var = y1
y1 = y2
y2 = swap_var
swapped = true
# Recalculate differentials
dx = x2 - x1
dy = y2 - y1
# Calculate error
var error: float = floor(dx / 2.0) # Try int
var ystep = 1 if y1 < y2 else -1
# Iterate over bounding box generating points between start and end
var y = y1
var points: Array[Vector2i] = []
for x in range(x1, x2 + 1):
var coord = Vector2i(y, x) if is_steep else Vector2i(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