Difference between revisions of "Bresenham's Line Algorithm"
Jump to navigation
Jump to search
(terser than ever) |
(Added Bresenhams in C# and VB.NET) |
||
Line 1: | Line 1: | ||
== 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"> | |||
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 = (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++ == | == C++ == | ||
Line 71: | Line 125: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
</div> | </div> | ||
== Ruby == | == 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"> | <div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em"> | ||
Line 115: | Line 168: | ||
return points | return points | ||
end | 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"> | |||
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 | |||
</syntaxhighlight> | </syntaxhighlight> |
Revision as of 03:37, 9 March 2011
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 = (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):
////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
int y1,
int x2,
int y2)
{
signed char ix;
signed char iy;
// if x1 == x2 or y1 == y2, then it does not matter what we set here
int delta_x = (x2 > x1?(ix = 1, x2 - x1):(ix = -1, x1 - x2)) << 1;
int delta_y = (y2 > y1?(iy = 1, y2 - y1):(iy = -1, y1 - y2)) << 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
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