Midpoint Circle algorithm

Background - Midpoint Circle algorithm

This section of my code is based on the Midpoint Circle algorithm outlined on Wikipedia. This algorithm does not return points in the order of traversal, but instead returns points in the order of a constant offset against the midpoint in each cardinal direction for each iteration

كود:

---

public static IEnumerable<Point> rasterCircle(Point midpoint, int radius)
{
    Point returnPoint = new Point();
    int f = 1 - radius;
    int ddF_x = 1;
    int ddF_y = -2 * radius;
    int x = 0;
    int y = radius;

    returnPoint.X = midpoint.X;
    returnPoint.Y = midpoint.Y + radius;
    yield return returnPoint;
    returnPoint.Y = midpoint.Y - radius;
    yield return returnPoint;
    returnPoint.X = midpoint.X + radius;
    returnPoint.Y = midpoint.Y;
    yield return returnPoint;
    returnPoint.X = midpoint.X - radius;
    yield return returnPoint;

    while (x < y)
    {
        if (f >= 0)
        {
            y--;
            ddF_y += 2;
            f += ddF_y;
        }
        x++;
        ddF_x += 2;
        f += ddF_x;
        returnPoint.X = midpoint.X + x;
        returnPoint.Y = midpoint.Y + y;
        yield return returnPoint;
        returnPoint.X = midpoint.X - x;
        returnPoint.Y = midpoint.Y + y;
        yield return returnPoint;
        returnPoint.X = midpoint.X + x;
        returnPoint.Y = midpoint.Y - y;
        yield return returnPoint;
        returnPoint.X = midpoint.X - x;
        returnPoint.Y = midpoint.Y - y;
        yield return returnPoint;
        returnPoint.X = midpoint.X + y;
        returnPoint.Y = midpoint.Y + x;
        yield return returnPoint;
        returnPoint.X = midpoint.X - y;
        returnPoint.Y = midpoint.Y + x;
        yield return returnPoint;
        returnPoint.X = midpoint.X + y;
        returnPoint.Y = midpoint.Y - x;
        yield return returnPoint;
        returnPoint.X = midpoint.X - y;
        returnPoint.Y = midpoint.Y - x;
        yield return returnPoint;
    }
}

---

.


You will notice in the code above that we yield a new point each time after we perform some combination of addition and subtraction of the current offset against the midpoint--yielding a point along a different diagonal arc each time. This ordering was good enough for my purposes of detecting collisions/intersection between enumerations, but others may want to modify this to return points in the order you might traverse along the component arcs.
Using the code - LINQ examples

Within the source code, you will find several examples of how you can leverage LINQ and C# 3.0 to perform some complicated operations in a concise manner.

كود:

---

// Let's get the sum of all X values
int xAvg = circlePoints.Aggregate(0, (acc, pt) => acc += pt.X);
// ...and the sum of all Y values
int yAvg = circlePoints.Aggregate(0, (acc, pt) => acc += pt.Y);

// Print out the result averages
Console.WriteLine("Avg X: " + (xAvg / circlePoints.Count()).ToString());
Console.WriteLine("Avg Y: " + (yAvg / circlePoints.Count()).ToString());

// The average of all points along a well-formed circle should be the origin
Debug.Assert(xAvg == circleOrigin.X);
Debug.Assert(yAvg == circleOrigin.Y);

---

Then, in the following section, we will perform aggregation on the enumeration of circle points using an anonymous function, a helper function called within a lambda expression, and finally, a statement lambda expression with multiple operations and an explicit return.

كود:

---

// In the following section we will accumulate on X and Y at the
// same time using a few different methods
Point newPoint;

// Accumulate using an inline anonymous function:
//  Although the LINQ Aggregate wasn't yet available, we would've
//  been inclined to use a delegate like this back in C# v2.0...
newPoint = circlePoints.Aggregate(new Point(), delegate(Point point1, Point point2)
          { point1.X += point2.X; point1.Y += point2.Y; return point1; });
Console.WriteLine("anonymous function Aggregation result: " + newPoint.ToString());

//We could use an addPoint helper function
//if the operations are significantly complex
newPoint = circlePoints.Aggregate(new Point(), (acc, x) => addPoint(acc, x));
Console.WriteLine("addPoint Aggregation result: " + newPoint.ToString());

// Because the operation is trivial we can use this inlined
// 'statement lambda expression' with an explicit return
newPoint = circlePoints.Aggregate(new Point(),
    (acc, x) => { acc.X += x.X; acc.Y += x.Y; return acc; });
Console.WriteLine("statement lambda function Aggregation result: " +
                  newPoint.ToString());

// Now find the maximum combination of X and Y in the circle
Console.WriteLine("Max X+Y point: + " + circlePoints.Max(i => i.X + i.Y));

---

Points of interest

I would like to do some performance testing under various conditions to see how this approach differs with typical algorithms where you would allocate memory for each point along a line. Based on those results, it might be an interesting exercise to convert some other graphics processing algorithms such as these to a similar implementation. The latest download includes some work-in-progress on a Digital Differential Analyzer algorithm to perform interpolations.