geometry - Find area of circle on a grid using euclidean distance?

Question

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

Answer 1

I too had to solve this problem recently and my initial approach was that of Numeron's - iterate on x axis from the center outwards and count the points within the upper right quarter, then quadruple them.

I then improved the algorithm around 3.4 times. What I do now is just calculating how many points there are within an inscribed square inside that circle, and what's between that square and the edge of the circle (actually in the opposite order). This way I actually count one-eighth of the points between the edge of the circle, the x axis and the right edge of the square. Here's the code:

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

Here's a picture to illustrate that:

1. Round down the length of the side of an inscribed square (pink) in the upper right quarter of the circle.
2. Go to next x coordinate behind the inscribed square and start counting orange points until you reach the edge.
3. Multiply the orange points by eight. This will give you the yellow ones.
4. Square the pink points. This will give you the dark-blue ones. Then multiply by four, this will get you the green ones.
5. Add the points on the axis and the one in the center. This gives you the light-blue ones and the red one.