Identifying lattice squares that are intersected by a closed curve

Question

Given a lattice of unit squares I would like to find the number of squares that a curve (in the example below the curve is a circle) passes through and the number of squares that totally reside inside the curve.

In the example the number of squares that the curve passes through is 60 and the number that are fully within the curve is 156. These are the two numbers I would like to generate.

I have created a graphic of the situation with the following code.

grid = Table[{x, y}, {x, -8, 8, 1}, {y, -8, 8, 1}];
centres = Table[{x, y}, {x, -7.5, 7.5, 1}, {y, -7.5, 7.5, 1}];
g1 = Graphics@Line[#] & /@ grid;
g2 = Graphics@Line[#] & /@ Transpose@grid;
g3 = Graphics[{Red, PointSize[0.005], Point /@ centres}];
g4 = Graphics[Circle[{0, 0}, Sqrt[59]]];
g5 = Graphics[{Black, PointSize[0.0075], Point@{0, 0}}];
Show[g1, g2, g3, g4, g5, Frame -> False, 
 PlotRange -> {{-9, 9}, {-9, 9}}, AspectRatio -> 1]

which produces:

I am not sure how to set such a thing up - I have looked in the documentation but I am not seeing something similar at all.

Any help would be much appreciated.

Answer 1

rectangles = Rectangle /@ Tuples[Range[-8, 7, 1], {2}]

Count[_?(Not @ RegionDisjoint[Circle[{0, 0}, Sqrt[59]], #] &)] @ rectangles

60

Count[_?(RegionWithin[Disk[{0, 0}, Sqrt[59]], #] &)] @ rectangles

156

Update: To exclude rectangles "just touching" the circle, we can use

Count[_?(FreeQ[_EmptyRegion | _Point]@
  RegionIntersection[Circle[{0, 0}, Sqrt[59]], #] &)] @ rectangles

60

Count[_?(FreeQ[_EmptyRegion | _Point]@
     RegionIntersection[Circle[{0, 0}, Sqrt[53]], #] &)] @ rectangles

52

Answer 2

Edit

For r=Sqrt[53], there are 148 squares in the curve, and there are 56 outside the curve, and 16*16-148-56=52 on the curve.

Clear["Global`*"];
lines0 = 
 Flatten[{Table[
    Line[{{i, j}, {i, j} + {1, 0}}], {i, -8, 7}, {j, -8, 8}], 
   Table[Line[{{i, j}, {i, j} + {0, 1}}], {i, -8, 8}, {j, -8, 7}]}];
p = {0, 0};
r = Sqrt[53];
range1 = Disk[p, r];
range2 = Annulus[p, {r, 4 r}];
intersec[range_] := Module[{lines, pts, edges, g, faces, squares},
   lines = 
    Cases[RegionIntersection[range, #] & /@ lines0, _Line, Infinity];
   pts = DeleteDuplicates[Flatten[lines[[;; , 1]], {2, 1}]];
   edges = 
    Table[UndirectedEdge @@ Flatten[FirstPosition[pts, #] & /@ d], {d,
       lines[[;; , 1]]}];
   g = Graph[edges, 
     VertexCoordinates -> Thread[Range@Length@pts -> pts]];
   faces = PlanarFaceList[g];
   squares = Select[faces, Length[#] == 4 &];
   {MeshRegion[pts, Polygon /@ squares], Length[squares]}];
Labeled[Graphics[{lines0, {FaceForm[], EdgeForm[Cyan], 
    range1}, {FaceForm[Yellow], EdgeForm[Red], 
    intersec[range2] // First}, {FaceForm[Green], EdgeForm[Red], 
    intersec[range1] // First}}], {Style[intersec[range1] // Last, 
   Green, 20], Style[intersec[range2] // Last, Darker@Yellow], 
  Style[2*8*2*8 - intersec[range1][[2]] - intersec[range2][[2]], 
   20]}]

Original

• Similar with https://mathematica.stackexchange.com/a/280656/72111, we list all of the segments, and intersection such lines with a region.
• Then we construct a Planar Graph and calculate all the 4-cycles.

lines0 = 
  Flatten[{Table[
     Line[{{i, j}, {i, j} + {1, 0}}], {i, -8, 7}, {j, -8, 8}], 
    Table[Line[{{i, j}, {i, j} + {0, 1}}], {i, -8, 8}, {j, -8, 7}]}];
Manipulate[Module[{range, lines, pts, edges, g, faces, squares},
  range = Disk[p, Sqrt[59]];
  (* range=Annulus[p,{3,Sqrt[59]}]; *)
  lines = 
   Cases[RegionIntersection[range, #] & /@ lines0, _Line, Infinity];
  pts = DeleteDuplicates[Flatten[lines[[;; , 1]], {2, 1}]];
  edges = 
   Table[UndirectedEdge @@ Flatten[FirstPosition[pts, #] & /@ d], {d, 
     lines[[;; , 1]]}];
  g = Graph[edges, 
    VertexCoordinates -> Thread[Range@Length@pts -> pts]];
  faces = PlanarFaceList[g];
  squares = Select[faces, Length[#] == 4 &];
  Labeled[
   Show[Graphics[lines0], 
    Graphics[{EdgeForm[Cyan], FaceForm[], range, EdgeForm[Red], 
      FaceForm[Green], MeshRegion[pts, Polygon /@ squares]}], 
    PlotRange -> 10], Framed@Length@squares]], {{p, {0, 0}}, Locator, 
  Appearance -> None}]