使用欧几里德距离在网格上查找圆的区域? [英] 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))

which in java at least is:

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;

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

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;

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

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屋！