Introduction
This article demonstrates the use of some of the new C# features in order to take an iterative approach to rendering a line using the classic Bresenham Line Algorithm and rendering a circle with the Midpoint Circle Algorithm.
Background - Bresenham Line algorithm
This code snippet is based on the most popular line rendering algorithm displayed , and exposes an IEnumerable<Point> that can be used for graphics or collision detection routines.
كود:public static class BresLine
{
/// <summary>
/// Creates a line from Begin to End starting at (x0,y0) and ending at (x1,y1)
/// * where x0 less than x1 and y0 less than y1
/// AND line is less steep than it is wide (dx less than dy)
/// </summary>
public static IEnumerable<Point> BresLineOrig(Point begin, Point end)
{
Point nextPoint = begin;
int deltax = end.X - begin.X;
int deltay = end.Y - begin.Y;
int error = deltax / 2;
int ystep = 1;
if (end.Y < begin.Y)
{
ystep = -1;
}
while (nextPoint.X < end.X)
{
if (nextPoint != begin) yield return nextPoint;
nextPoint.X++;
error -= deltay;
if (error < 0)
{
nextPoint.Y += ystep;
error += deltax;
}
}
}
}
One of the pitfalls of this routine is that it actually treats our line as a vector with an increasing x value. This means that the code snippet above is only valid for the simplest case of (x0 < x1 and dy < dx) as shown in the leftmost image below. If you read the Wikipedia article, you will find that there is an optimized algorithm at the bottom of the article that combines approaches for all possible vector quadrants that our line would be in.
This optimized algorithm seems like a great idea, but if you download the attached code file, you will find that I've actually implemented the algorithm in four different methods to address the different combinations.
http://www.codeproject.com/KB/graphi...normalLine.gif
http://www.codeproject.com/KB/graphi.../steepLine.gif
When comparing the iterative approach to the optimized algorithm at the bottom of the Wikipedia article, you should take a minute and consider the order of the points being rendered for all permutations of {steep, reverse-X, reverse-Y}. You may notice that as soon as the swap functions are called on x0, x1, y0, or y1, you change the start and end points, thereby altering the order of the output.
When you are simply drawing a line to the screen that will be displayed in one pass, you don't need to worry about whether your points start at A and end at B. However, I implemented this algorithm with the intent of using it in path finding algorithms with the purpose of navigating an entity from point A to B. In this case, it becomes important to iterate through the points in the proper order so that conditions can be properly evaluated along the path and any false paths can be culled as soon as possible.
Although it is certainly possible to combine the four methods I've written into a single one, it seems more beneficial to performance to perform comparisons in one place and dispatch the BresLine request to the appropriate routine. This is because the alternative involves performing additional checks on the vector characteristics during each iteration, instead of once at dispatch.
Using the code
Just copy the example static class into your project and enumerate over it like you would any other IEnumerable.
كود:Point myStart = new Point(1, 20);
Point myEnd = new Point(20, 35);
IEnumerable<Point> myLine = BresLine.RenderLine(myStart, myEnd);
foreach (Point myPoint in myLine)
{
Console.WriteLine(myPoint.ToString());
}
You might also want to perform some functions like I've shown in the snippet below:
كود:IEnumerable<Point> longLine; // Represent an enumerable line
// This is an example of why I am using the iterative approach
// We'll draw a line from 0,0 to 5000000,900000--
longLine = BresLine.RenderLine(new Point(0, 0), new Point(5000000, 900000));
// Now iterate over the line and perform some operation
foreach (Point myPoint in longLine)
{
double dummyVar = myPoint.X * Math.Sin(myPoint.X / 90);
// Eventually our X will exceed the boundary value of 12345 in some direction
if (Math.Abs(dummyVar) > 12345) break;
}
// Now output some strings
StringBuilder sb = new StringBuilder();
string totalString = longLine.Aggregate(sb, (acc, x) =>
sb.Append(x.ToString())).ToString();
// totalString is something like 98 million characters long at this point
if (totalString.Length < 1000)
{
// We could print the 98 million character string...
// but you could expect an OutOfMemoryException
Console.WriteLine(totalString);
}
// Accumulate the SIN of all y values for no reason in particular
Console.WriteLine("SIN(Y) aggregate: " +
longLine.Aggregate(0d, (acc, pointN) => acc += Math.Sin(pointN.Y)));
Breaking down the last line in the example above, you will see that we are performing a fairly complex calculation, even though it is represented in a very concise manner. The concise nature of this statement can be extremely confusing to users that aren't familiar with the use of aggregate functions and lambda expressions, but once you've seen the power of these ******** constructs, it becomes pretty hard to dismiss them.
