9

给定一个二维坐标系，如何从给定点找到半径内具有整数坐标的所有点？我想要这些点作为 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 并不重要。换句话说，我不需要浮点精度。

4

4 回答 4

11

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

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));
}
于 2013-01-11T19:42:19.530 回答
4

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

于 2013-01-11T19:35:02.730 回答
2

您可以对中点圆算法进行小修改以获得实心圆。

首先生成坐标：

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

这节省了一些不会在圈内的工作访问点，但以牺牲一点预处理为代价。对于较小的圈子，它肯定无济于事，而对于较大的圈子，老实说，我不知道。您必须对其进行基准测试。

于 2013-01-11T21:14:22.660 回答
1

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

在一些小型 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));
    }
}
于 2013-01-11T22:48:06.730 回答