没有重复的中点圆？

Question

我有一些代码可以生成圆形的网格坐标（SDL_Point 只包含两个 int 用于 x 和 y）：

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;
}

这工作正常，但我注意到当从一个八分圆复制到另一个八分圆时，一些坐标被添加了两次（图片中更清晰的灰色）：

是否有已知的方法来避免这些重复，或者我应该在将它们添加到 vector 之前检查一下？

我想知道最有效的方法是什么。我还没有找到任何答案，我想这在打印纯色圆圈时通常不是问题。

编辑：我需要向量作为输出。

谢谢！ :)

Answer 1

您可以使用强制唯一性的容器，例如

std::set<SDL_Point>

然后使用插入方法代替push_back。

Answer 2

如果您考虑您的代码在做什么，有两种情况会生成重复项：当 y 为 0 时（沿着图表的边缘），当 x == y 时（沿着图表的对角线）圈）。您可以在对这些条件进行适当的 coord 计算之前添加检查以排除它们。

例如，当 y 为零时，coord = { start.x + x, start.y + y }; 和 coord = { start.x + x, start.y - y }; 生成相同的值。

Answer 3

实现 1201ProgramAlarm 的答案是这样的：

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])
  }
}

没有重复的中点圆？

Midpoint circle without duplicates?

c++

algorithm

bresenham