Overlapping circle

Question

You should write a program or function that given an N by N equally spaced square grid and a solid inscribed circle outputs or returns the number of grid squares which are overlapped partially or fully by the solid circle.

0-sized overlaps (i.e. when the circle only touches a line) are not counted. (These overlaps occur at e.g. N = 10.)

Example

N = 8 (64 squares), Slices = 60

Input

• An integer N > 0. (The grid wil have N * N squares.)

Output

• An integer, the number of solid circle slices.

Examples

(input-output pairs)

Inputs:  1 2 3  4  5  6  7  8  9 10  11  12  13  14  15
Outputs: 1 4 9 16 25 36 45 60 77 88 109 132 149 172 201

This is code-golf so shortest entry wins.

Answer 1

Python 2, 72

lambda n:sum(n>abs(z%-~n*2-n+(z/-~n*2-n)*1j)for z in range(~n*~n))+n+n-1

Ungolfed:

def f(n):
    s=0
    for x in range(n+1):
        for y in range(n+1):
            s+=(x-n/2)**2+(y-n/2)**2<(n/2)**2
    return s+n+n-1

The grid points for an (n+1)*(n+1) square. A cell overlaps the circle if its grid point nearest the center is inside the circle. So, we can count grid points, except this misses 2*n+1 grid points at axes (both for even and odd n), so we correct for that manually.

The code saves characters by using complex distances to calculate the distance to the center and a loop collapse to iterate over a single index.

Answer 2

CJam, 36 35 34 27 bytes

This turned out to be the same algorithm as xnor's, but I wonder if there is any better one.

rd:R,_m*{{2*R(-_g-}/mhR<},,

Code explanation:

rd:R                                "Read the input as double and store it in R";
    ,_                              "Get 0 to input - 1 array and take its copy";
      m*                            "Get Cartesian products";
                                    "Now we have coordinates of top left point of each";
                                    "of the square in the N by N grid";
        {               },,         "Filter the squares which are overlapped by the";
                                    "circle and count the number";
         {        }/                "Iterate over the x and y coordinate of the top left";
                                    "point of the square and unwrap them";
          2*                        "Scale the points to reflect a 2N grid square";
            R(-                     "Reduce radius - 1 to get center of the square";
               _g-                  "Here we are reducing or increasing the coordinate";
                                    "by 1 in order to get the coordinates of the vertex";
                                    "of the square closer to the center of the grid";
                    mhR<            "Get the distance of the point from center and check";
                                    "if its less than the radius of the circle";

UPDATE : Using the 2N trick from Jakube along with some other techniques to save 7 bytes!

Try it online here

Answer 3

Pyth, 27 26

-*QQ*4lfgsm^d2T*QQ^%2_UtQ2

Try it online: Pyth Compiler/Executor

I use a 2Nx2N grid and count overlapping 2x2 squares. That is a little bit shorter, since I already know the radius N.

And actually I don't count the overlapping squares. I count the non-overlapping squares of the second quadrant, multiply the number by 4 and subtract the result from N*N.

Explanation for the 27 solution:

-*QQ*4lfgsm^-Qd2T*QQ^t%2UQ2   implicit: Q = input()
                     t%2UQ    generates the list [2, 4, 6, ..., Q]
                    ^     2   Cartesian product: [(2, 2), (2, 4), ..., (Q, Q)]
                              These are the coordinates of the right-down corners
                              of the 2x2 squares in the 2nd quadrant. 
       f                      Filter the coordinates T, for which:
        gsm^-Qd2T*QQ             dist-to-center >= Q
                                 more detailed: 
          m     T                   map each coordinate d of T to:
           ^-Qd2                       (Q - d)^2
         s                          add these values
        g        *QQ                 ... >= Q*Q
    *4l                       take the length and multiply by 4
-*QQ                          Q*Q - ...

Explanation for the 26 solution:

I noticed that I use the coordinates only once and immediately subtract the coordinates from Q. Why not simply generate the values Q - coords directly?

This happens in %2_UtQ. Only one char larger than in the previous solution and saves 2 chars, because I don't have to substract -Q.

Answer 4

Pyth,  44  36

JcQ2L^-+b<bJJ2sm+>*JJ+y/dQy%dQqQ1*QQ

Trying to clean it a bit in case I could shave some bytes.

Explanation

                           Q = eval(input())    (implicit)
JcQ2                       calculate half of Q and store in J
L                          define function y(b) that returns
 ^-+b<bJJ2                 (b - J + (1 if b < J else 0)) ^ 2
s                          output sum of
 m                 *QQ      map d over integers 0..(Q*Q-1)
  +
   >*JJ                      J*J is greater than
       +y/dQy%dQ              sum of y(d / Q) and y(d % Q)
                qQ1          or Q is 1; see below

I have to explicitly check for n = 1, since my algorithm only checks the corner of the square nearest to the center (and none are covered in n = 1).

Answer 5

Octave (74) (66) (64)

Here the octave version. Basically finding all the vertices within the circle and then finding all the squares with one or more valid vertices via convolution. 64 Bytes:

x=ndgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

66 Bytes:

x=meshgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

74 Bytes:

n=input('');x=ones(n+1,1)*(-1:2/n:1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

Answer 6

R - 64

function(n)sum(rowSums(expand.grid(i<-0:n-n/2,i)^2)<n^2/4)+2*n-1