使用欧几里得距离查找网格上的圆的面积? [英] Find area of circle on a grid using euclidean distance?

问题描述

我想拥有一个可以输入半径值并让该函数吐出该尺寸圆的区域的函数.问题是我希望它仅对基于整数的坐标执行此操作.

I would like to have a function where I can input a radius value and have said function spit out the area for that size circle. The catch is I want it to do so for integer based coordinates only.

有人告诉我要研究高斯的圆问题，这似乎正是我感兴趣的问题，但是我并不真正理解其背后的数学原理(假设它实际上是准确的)计算我想要的东西.

I was told elsewhere to look at Gauss's circle problem, which looks to be exactly what I'm interested in, but I don't really understand the math behind it (assuming it is actually accurate in calculating what I'm wanting).

作为一个旁注，我目前使用的确是修改后的圆图绘制算法，确实可以产生所需的结果，但是效率似乎非常低(无论是算法还是我使用它的方法来获取面积) ).

As a side note, I currently use a modified circle drawing algorithm which does indeed produce the results I desire, but it just seems so incredibly inefficient (both the algorithm and the way in which I'm using it to get the area).

所以，如果存在这样的问题，或者像是对高斯圆问题的详尽解释以及为什么它不是我要寻找的东西，那么对我来说，可能的答案是该函数的实际代码或伪代码

So, possible answers for this to me would be actual code or pseudocode for such a function if such a thing exists or something like a thorough explanation of Gauss's circle problem and why it is/isn't what I'm looking for.

我希望函数会产生的结果:

The results I would hope the function would produce:

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

推荐答案

这是一个老问题，但我最近正在做同样的事情.正如您所说的，您要做的是高斯的圆弧问题，在此处

This is an old question but I was recently working on the same thing. What you are trying to do is as you said, Gauss's circle problem, which is sort of described here

虽然我也很难理解所有内容背后的严肃数学，但是当不使用奇怪的外来符号时，它或多或少会产生以下结果:

While I too have difficulty understaning the serious maths behind it all, what it more or less pans out to when not using wierd alien symbols is this:

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).

I have no idea why or how this works and to be honest Im a bit bummed I have to use a loop to get this out rather than a single line, as it means the performance is O(r^2/4) rather than O(1).

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

Since the math wizards can't seem to do better than a loop, I decided to see whether I could get it down to O(r + 1) performance, which I did. So don't use the above, use the below. O(r^2/4) is terrible and will be slower even despite mine using square roots.

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

此代码的作用是沿着一条正交线从中心向外到边缘进行循环，并在每个点上沿垂直方向增加从线到边缘的距离.最后，它将在四分之一中具有点数，因此它将结果翻四倍并加一，因为也有中心点.我觉得Wolfram方程做了类似的事情，因为它也乘以4并加1，但是IDK为什么循环r ^ 2/4.

What this code does is loop from centre out to the edge along an orthogonal line, and at each point adding the distance from line to edge in a perpendicualr direction. At the end it will have the number of points in a quater, so it quadruples the result and adds one because there is also central point. I feel like the wolfram equation does something similar, since it also multiplies by 4 and adds one, but IDK why it loops r^2/4.

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

Honestly these aren't great solution, but it seems to be the best there is. If you are calling a function which does this regularly then as new radii come up save the results in a look-up table rather than doing a full calc each time.

这不是您问题的一部分，但可能与某人有关，所以无论如何我都会添加它.我个人一直在用一个单元格来查找一个圆内的所有点:

Its not a part of your question, but it may be relevant to someone maybe so I'll add it in anyway. I was personally working on finding all the points within a circle with cells defined by:

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

这使整个事情变得不合时宜，因为额外的+半径使得这不完全是毕达哥拉斯定理.多余的一点使圆在网格上看起来更具视觉吸引力，因为它们在正交边缘上没有那些小的丘疹.事实证明，是的，我的形状仍然是一个圆形，但是它使用sqrt(r ^ 2 + r)作为半径而不是r，这显然可行，但不问我如何.无论如何，对我而言，这意味着我的代码略有不同，看起来更像这样:

Which puts the whole thing out of whack because the extra +radius makes this not exactly the pythagorean theorem. That extra bit makes the circles look a whole lot more visually appealing on a grid though, as they don't have those little pimples on the orthogonal edges. It turns out that, yes my shape is still a circle, but its using sqrt(r^2+r) as radius instead of r, which apparently works but dont ask me how. Anyway that means that for me, my code is slightly different and looks more like this:

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;

这篇关于使用欧几里得距离查找网格上的圆的面积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！