找到给定半径内的所有整数坐标

Question

给定一个二维坐标系,如何在给定点的半径范围内找到所有具有整数坐标的点？我想将点作为x坐标和y坐标值.

在给定点周围的正方形中找到点很容易,可以这样做:

for(int x = -radius + point.x; x < radius + point.x; ++x)
for(int y = -radius + point.y; y < radius + point.y; ++y)
{
    points.insert(point(x, y));
}

但是如何在给定点周围找到圆圈中的点？该算法与性能相关,但与精度无关.因此,如果一个点接近半径而不是1,则无关紧要.换句话说,我不需要浮点精度.

Answer 1

最简单的解决方案:取一个正方形并过滤它:

Point point(100, 100);
for(int x = -radius; x <= radius; ++x)
for(int y = -radius; y <= radius; ++y)
if(x*x + y*y <= radius* radius)   {
    points.insert(Point(x + point.x, y + point.y));
}

Answer 2

一种方法是在 x 上进行从 -R 到 +R 的外循环，并根据该 x 值处圆的 y 值（从 -sqrt(r^2 - x^2) 到 sqrt(r^) 在 y 上进行内循环2 - x^2) 如果中心位于 0,0)，如果中心位于 X,Y - 只需按照与示例中相同的方式将 X 或 Y 添加到所有循环范围