CODEWITHSUNDEEP
c++algorithmbresenham
JoePerkins
JoePerkins

Reputation: 975

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! :)

Upvotes: 2

Views: 355

Answers (3)

Ben West
Ben West

Reputation: 4596

Implementing 1201ProgramAlarm's answer goes like this:

push([x, y])
if (x != 0) push([-x, y])
if (y != 0) {
  push([x, -y])
  if (x != 0) push([-x, -y])
}
if (x != y) {
  push([y, x])
  if (x != 0) push([y, -x])
  if (y != 0) {
    push([-y, x])
    if (x != 0) push([-y, -x])
  }
}

Upvotes: 0

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

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.

Upvotes: 4

L. Scott Johnson
L. Scott Johnson

Reputation: 4382

You could use a container that enforces uniqueness, like 

std::set<SDL_Point>

and then use the insert method instead of push_back.

Upvotes: 3

Related Questions