Средний круг без дубликатов?

У меня есть код для генерации координат сетки (SDL_Point просто содержит два ints для 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?

Я хотел бы знать, каков наиболее эффективный способ сделать это. Я не нашел никакого ответа, я думаю, что это обычно не проблема при печати однотонных кружков.

РЕДАКТИРОВАТЬ: мне нужен вектор в качестве вывода.

Спасибо! 🙂

1

Решение

Если вы считаете, что делает ваш код, есть два случая, которые генерируют дубликаты: когда y 0 (по краям вашей диаграммы), и когда x == y (диагонали в круге). Вы можете добавить чек до соответствующего coord Расчеты по этим условиям исключают их.

Например, coord = { start.x + x, start.y + y }; а также coord = { start.x + x, start.y - y }; генерировать те же значения, когда y это ноль.

2

Другие решения

Вы можете использовать контейнер, который обеспечивает уникальность, например,

std::set<SDL_Point>

и затем используйте метод вставки вместо push_back.

3