c++algorithmbresenham

Midpoint circle without duplicates?


I have some code to generate grid coordinates (SDL_Point just contains two ints for x and y) with a circle shape:

std::vector<SDL_Point> circle(const SDL_Point & start, const int radius)
{
    int x{ radius }, y{ 0 };
    int xChange{ 1 - 2 * radius };
    int yChange{ 1 };
    int rError{ 0 };

    std::vector<SDL_Point> circle;
    SDL_Point coord;

    while (x >= y)
    {
        /*  Due to circle's symmetry, we need only to calculate
            points in the first 45º of the circle.
        */

        coord = { start.x + x, start.y + y }; // Octant 1.
        circle.push_back(coord);
        coord = { start.x - x, start.y + y }; // Octant 4.
        circle.push_back(coord);
        coord = { start.x - x, start.y - y }; // Octant 5.
        circle.push_back(coord);
        coord = { start.x + x, start.y - y }; // Octant 8.
        circle.push_back(coord);
        coord = { start.x + y, start.y + x }; // Octant 2.
        circle.push_back(coord);
        coord = { start.x - y, start.y + x }; // Octant 3.
        circle.push_back(coord);
        coord = { start.x - y, start.y - x }; // Octant 6.
        circle.push_back(coord);
        coord = { start.x + y, start.y - x }; // Octant 7.
        circle.push_back(coord);

        ++y;
        rError += yChange;
        yChange += 2;

        if (2 * rError + xChange > 0)
        {
            --x;
            rError += xChange;
            xChange += 2;
        }
    }

    return circle;
}

This works ok, but I noticed some coordinates are added twice when copying from one octant to another (clearer gray in the picture):

midpoint circle

Is there a known way to avoid having those duplicates or should I just check before adding them to the vector?

I would like to know what is the most efficient way to do it. I haven't found any answer, I guess it's not usually a concern when printing plain color circles.

EDIT: I need the vector as output.

Thanks! :)


Solution

  • If you consider what your code is doing, there are two cases that generate duplicates: when y is 0 (along the edges of your diagram), and when x == y (the diagonals in the circle). You can add a check before the appropriate coord calculations for these conditions to exclude them.

    For example, coord = { start.x + x, start.y + y }; and coord = { start.x + x, start.y - y }; generate the same values when y is zero.