1

我想要一个函数，我可以输入一个半径值，并说函数吐出那个大小圆的区域。问题是我希望它只对基于整数的坐标这样做。

我在别处被告知要查看高斯的圆问题，这看起来正是我感兴趣的问题，但我并不真正理解它背后的数学（假设它在计算我想要的东西时实际上是准确的）。

作为旁注，我目前使用修改后的圆形绘图算法，它确实产生了我想要的结果，但它似乎非常低效（算法和我使用它来获取区域的方式）。

因此，对我来说，可能的答案是这样的函数的实际代码或伪代码，如果存在这样的事情，或者像对高斯圆问题的彻底解释以及为什么它是/不是我正在寻找的那样。

我希望该功能会产生的结果：

Input: Output
0: 1
1: 5
2: 13
3: 29
4: 49
5: 81
6: 113
7: 149
8: 197
9: 253
4

2 回答 2

2

我最近也不得不解决这个问题，我最初的方法是 Numeron 的方法 - 从中​​心向外在 x 轴上迭代并计算右上四分之一内的点，然后将它们翻两番。

然后我将算法改进了大约 3.4 倍。我现在所做的只是计算该圆内的内接正方形内有多少个点，以及该正方形和圆的边缘之间有什么（实际上以相反的顺序）。这样，我实际上计算了圆边缘、x 轴和正方形右边缘之间的点的八分之一。这是代码：

public static int gaussCircleProblem(int radius) {
    int allPoints=0; //holds the sum of points
    double y=0; //will hold the precise y coordinate of a point on the circle edge for a given x coordinate.
    long inscribedSquare=(long) Math.sqrt(radius*radius/2); //the length of the side of an inscribed square in the upper right quarter of the circle
    int x=(int)inscribedSquare; //will hold x coordinate - starts on the edge of the inscribed square
    while(x<=radius){
        allPoints+=(long) y; //returns floor of y, which is initially 0
        x++; //because we need to start behind the inscribed square and move outwards from there
        y=Math.sqrt(radius*radius-x*x); // Pythagorean equation - returns how many points there are vertically between the X axis and the edge of the circle for given x
    }
    allPoints*=8; //because we were counting points in the right half of the upper right corner of that circle, so we had just one-eightth
    allPoints+=(4*inscribedSquare*inscribedSquare); //how many points there are in the inscribed square
    allPoints+=(4*radius+1); //the loop and the inscribed square calculations did not touch the points on the axis and in the center
    return allPoints;
}

这是一张图片来说明这一点：

我的高斯圆问题算法图解

  1. 在圆的右上四分之一处向下取整内切正方形（粉红色）的边长。
  2. 转到内接正方形后面的下一个 x 坐标并开始计算橙色点，直到到达边缘。
  3. 将橙色点乘以八。这会给你黄色的。
  4. 将粉红色点平方。这会给你深蓝色的。然后乘以四，这将得到绿色的。
  5. 添加轴上的点和中心的点。这给了你浅蓝色的和红色的。
于 2017-02-21T16:57:30.403 回答
1

这是一个老问题，但我最近也在做同样的事情。正如你所说，你正在尝试做的就是高斯圆问题，这里有点描述

虽然我也很难理解这一切背后的严肃数学，但当不使用奇怪的外星符号时，它或多或少会变成这样：

1 + 4 * sum(i=0, r^2/4, r^2/(4*i+1) - r^2/(4*i+3))

在java中至少是：

int sum = 0;
for(int i = 0; i <= (radius*radius)/4; i++)
  sum += (radius*radius)/(4*i+1) - (radius*radius)/(4*i+3);
sum = sum * 4 + 1;

我不知道为什么或如何工作，老实说我有点沮丧，我必须使用循环而不是单行来解决这个问题，因为这意味着性能是 O(r^2/4) 而不是 O (1)。

由于数学向导似乎不能比循环做得更好，我决定看看我是否可以将它降低到 O(r + 1) 的性能，我做到了。所以不要使用上面的，使用下面的。O(r^2/4) 很糟糕，即使我使用平方根也会变慢。

int sum = 0;
for(int x = 0; x <= radius; x++)
  sum += Math.sqrt(radius * radius - x * x);
sum = sum * 4 + 1;

这段代码的作用是从中心向外沿一条正交线循环到边缘，并在每个点沿垂直方向添加从线到边缘的距离。最后它会有一个四分之一的点数，所以它将结果翻了两番并加了一个，因为还有中心点。我觉得 wolfram 方程做了类似的事情，因为它也乘以 4 并加一，但是 IDK 为什么它循环 r^2/4。

老实说，这些不是很好的解决方案，但它似乎是最好的解决方案。如果您正在调用一个定期执行此操作的函数，那么当新半径出现时，将结果保存在查找表中，而不是每次都进行完整计算。

它不是您问题的一部分，但它可能与某人有关，所以无论如何我都会添加它。我个人正在努力寻找一个圆圈内的所有点，其单元格定义为：

(centreX - cellX)^2 + (centreY - cellY)^2 <= radius^2 + radius

这使整个事情变得混乱，因为额外的+半径使这不完全符合勾股定理。额外的一点使圆圈在网格上看起来更具视觉吸引力，因为它们在正交边缘上没有那些小疙瘩。事实证明，是的，我的形状仍然是一个圆形，但是它使用 sqrt(r^2+r) 作为半径而不是 r，这显然有效，但不要问我如何。无论如何，这意味着对我来说，我的代码略有不同，看起来更像这样：

int sum = 0;
int compactR = ((radius * radius) + radius) //Small performance boost I suppose
for(int j = 0; j <= compactR  / 4; j++)
  sum += compactR / (4 * j + 1) - compactR / (4 * j + 3);
sum = sum * 4 + 1;
于 2013-09-05T02:36:53.890 回答