在给定半径内找出所有整数坐标

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的点被添加或未添加，都没有关系。换句话说，我不需要浮点精度。

- danijar

---

谢谢指出。英语不是我的母语。我已经更新了问题的文本和标题。 - danijar

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

- Eric

---

此方法还会在四个外部点处创建一个轮辐：http://i.imgur.com/wirxfJP.jpg - jjxtra

@PsychoDad：与问题中的意思相同。此外，这些峰值是正确的行为。 - Eric

请注意，如果 point.x 或 point.y 不是整数，则代码需要进行一些调整。 - Pablo H

Answer 2

一个方法是在x轴上进行外层循环，从-R到+R，在内层循环中根据该x值处圆的y值进行循环（如果圆心在0,0，则从-sqrt(r^2 - x^2)到sqrt(r^2 - x^2)），如果圆心在X,Y处，则以与您示例相同的方式向所有循环范围添加X或Y。

- Ofir

Answer 3

你可以对中点圆算法进行小修改，以获得一个填充的圆。

首先生成坐标：

data = new int[radius];
int f = 1 - radius, ddF_x = 1;
int ddF_y = -2 * radius;
int x = 0, y = radius;
while (x < y)
{
    if (f >= 0)
    {
        y--;
        ddF_y += 2; f += ddF_y;
    }
    x++;
    ddF_x += 2; f += ddF_x;
    data[radius - y] = x; data[radius - x] = y;
}

接着访问所有内部点：

int x0 = center.X;
int y0 = center.Y - Radius;
int y1 = center.Y + Radius - 1;

for (int y = 0; y < data.Length; y++)
{
    for (int x = -data[y]; x < data[y]; x++)
    {
        doSomething(x + x0, y + y0);
        doSomething(x + x0, y1 - y);
    }
}

这样可以节省一些访问不在圆内的点的工作量，但需要进行一些预处理。对于较小的圆，这肯定没有帮助，至于对于更大的圆，我不确定。你需要进行基准测试。

- harold

Answer 4

以下代码只是沿着一个四分之一圆弧解析边界以确定内部区域。它不需要计算外部点或内部点的距离。（编辑：但最终，填充圆的所有点都会被添加）

在一些小型Java基准测试中，对于小半径（<10），它与解析完整正方形的简单方法速度相同。对于半径20-40，它大约快2倍，并且对于半径> 50，它实现了约4倍的加速。对于一些更大的半径（>200），加速比再次降低，因为对于任何方法，主导时间都需要用于创建和添加> 100k个点-无论它们如何确定。

// add the full length vertical center line once
for (int y = -radius + point.y; y <= radius + point.y; ++y)
    points.insert(Point(point.x, y));

int sqRadius = radius * radius;

// add the shorter vertical lines to the left and to the right
int h = radius;
for (int dx = 1; dx <= radius; ++dx) {
    // decrease h
    while (dx*dx + h*h > sqRadius && h > 0)
        h--;

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

- cubic lettuce

---

圆形是填充的，但它并不确定到内部点的距离，类似于哈罗德的中点算法。 - cubic lettuce

那我一定会试试看的。 - danijar

你为什么要先添加完整长度的垂直中心线呢？为什么不将其合并到后面的循环中呢？ - mattsap