Bresenham's Line Algorithm
(→C#: Fat-fingered the last edit summary which fixed missing call to Math.Abs() for dY in C# version.) |
|||
Line 278: | Line 278: | ||
End Sub | End Sub | ||
End Module | 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> | </syntaxhighlight> |
Revision as of 06:05, 22 February 2012
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.
In libtcod it is accessible using line(x1, y1, x2, y2, callback)
. Below are several hand-coded implementations in various languages.
Contents |
C#
Here is a simple way of using the algorithm in C# with delegates.
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 x2, int y2) { // if x1 == x2 or y1 == y2, then it does not matter what we set here int delta_x(x2 - x1); signed char ix((delta_x > 0) - (delta_x < 0)); delta_x = std::abs(delta_x) << 1; int delta_y(y2 - y1); signed char 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) { 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); } } }
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(x1, y1, x2, y2): points = [] issteep = abs(y2-y1) > abs(x2-x1) if issteep: x1, y1 = y1, x1 x2, y2 = y2, x2 rev = False if x1 > x2: x1, x2 = x2, x1 y1, y2 = y2, y1 rev = True deltax = x2 - x1 deltay = abs(y2-y1) error = int(deltax / 2) y = y1 ystep = None if y1 < y2: ystep = 1 else: ystep = -1 for x in range(x1, x2 + 1): if issteep: points.append((y, x)) else: points.append((x, y)) error -= deltay if error < 0: y += ystep error += deltax # Reverse the list if the coordinates were reversed if rev: 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.
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 = 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)