Skip to content

Instantly share code, notes, and snippets.

@japsuu
Created January 10, 2023 07:01
Show Gist options
  • Save japsuu/f0bee9fd8bd062a1444e0a8fd5b75834 to your computer and use it in GitHub Desktop.
Save japsuu/f0bee9fd8bd062a1444e0a8fd5b75834 to your computer and use it in GitHub Desktop.
C# comparison of two different implementations of the Bresenham's Line Algorithm.
// Compares the speed of two different implementations of Bresenham's Line Algorithm.
// Draws the resulting lines on a user defined canvas.
using System.Diagnostics;
// Size of the drawn canvas.
const int canvasWidth = 128;
const int canvasHeight = 128;
// First point.
const int x1 = 101;
const int y1 = 28;
// Second point.
const int x2 = 15;
const int y2 = 92;
// Initialize the canvas.
int[,] canvas = new int[canvasWidth, canvasHeight];
for (int y = 0; y < canvasHeight; y++)
{
for (int x = 0; x < canvasWidth; x++)
{
canvas[x, y] = 0;
}
}
Stopwatch sw = new();
// Run & time the first implementation.
sw.Start();
foreach ((int x, int y) in BresenhamLine1(x1, y1, x2, y2))
{
canvas[x, y] += 1;
}
sw.Stop();
long firstAlgorithmTime = sw.ElapsedMilliseconds;
sw.Reset();
// Run & time the second implementation.
sw.Start();
foreach ((int x, int y) in BresenhamLine2(x1, y1, x2, y2))
{
canvas[x, y] += 2;
}
sw.Stop();
long secondAlgorithmTime = sw.ElapsedMilliseconds;
// NOTE: The drawing could be way more efficient by drawing lines, not individual characters, but then we'd lose the coloring.
// NOTE: But who cares. This is just a test anyways :)
for (int y = 0; y < canvasHeight; y++)
{
for (int x = 0; x < canvasWidth; x++)
{
Console.BackgroundColor = canvas[x, y] switch
{
// Pixel not drawn
0 => ConsoleColor.Black,
// Pixel drawn by first algorithm
1 => ConsoleColor.Blue,
// Pixel drawn by second algorithm
2 => ConsoleColor.Red,
// Pixel drawn by both algorithms
3 => ConsoleColor.Green,
_ => throw new ArgumentOutOfRangeException()
};
Console.Write(canvas[x, y]);
}
Console.WriteLine();
}
Console.WriteLine($"First algorithm finished in {firstAlgorithmTime} ms.");
Console.WriteLine($"Second algorithm finished in {secondAlgorithmTime} ms.");
Console.ReadKey();
// Slower, but more accurate Bresenham's Line Algorithm.
// Modified from: https://stackoverflow.com/a/11683720
static IEnumerable<(int x, int y)> BresenhamLine1(int x1, int y1, int x2, int y2)
{
int w = x2 - x1;
int h = y2 - y1;
int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0;
dx1 = w switch
{
< 0 => -1,
> 0 => 1,
_ => dx1
};
dy1 = h switch
{
< 0 => -1,
> 0 => 1,
_ => dy1
};
dx2 = w switch
{
< 0 => -1,
> 0 => 1,
_ => dx2
};
int longest = Math.Abs(w);
int shortest = Math.Abs(h);
if (longest <= shortest)
{
longest = Math.Abs(h);
shortest = Math.Abs(w);
if (h < 0) dy2 = -1;
else if (h > 0) dy2 = 1;
dx2 = 0;
}
int numerator = longest >> 1;
for (int i = 0; i <= longest; i++)
{
yield return (x1, y1);
numerator += shortest;
if (numerator >= longest)
{
numerator -= longest;
x1 += dx1;
y1 += dy1;
}
else
{
x1 += dx2;
y1 += dy2;
}
}
}
// Faster, but less accurate Bresenham's Line Algorithm.
// Modified from: http://ericw.ca/notes/bresenhams-line-algorithm-in-csharp.html
static IEnumerable<(int x, int y)> BresenhamLine2(int x1, int y1, int x2, int y2)
{
bool steep = Math.Abs(y2 - y1) > Math.Abs(x2 - x1);
if (steep)
{
int t = x1;
x1 = y1;
y1 = t;
t = x2;
x2 = y2;
y2 = t;
}
if (x1 > x2)
{
int t = x1;
x1 = x2;
x2 = t;
t = y1;
y1 = y2;
y2 = t;
}
int dx = x2 - x1;
int dy = Math.Abs(y2 - y1);
int error = dx / 2;
int yStep = y1 < y2 ? 1 : -1;
int y = y1;
for (int x = x1; x <= x2; x++)
{
yield return (steep ? y : x, steep ? x : y);
error -= dy;
if (error >= 0) continue;
y += yStep;
error += dx;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment