Created
January 10, 2023 07:01
-
-
Save japsuu/f0bee9fd8bd062a1444e0a8fd5b75834 to your computer and use it in GitHub Desktop.
C# comparison of two different implementations of the Bresenham's Line Algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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