4
$\begingroup$

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:

lattice

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.

$\endgroup$
2
  • 1
    $\begingroup$ Just to make it clear: Intersection is valid only if the curve passes through the square (therefore it has two intersections with squares' boundary), not if it only touches the square in one point, right? $\endgroup$
    – Domen
    Mar 17, 2023 at 12:34
  • 1
    $\begingroup$ @Domen Yes that is correct - just touching doesn't count. Which is why I made the radius of the circle in the example the square root of a prime of the form 4k+3 so it wasn't the sum of two squares. $\endgroup$
    – 1729taxi
    Mar 17, 2023 at 12:42

2 Answers 2

10
$\begingroup$
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
$\endgroup$
4
  • $\begingroup$ Thank you for that - nice and brief. But I do have a question - if I choose a radius of root 53 there are eight points (-7,-2),(-7,2),(7,-2),(7,2), (-2,-7),(-2,7),(2,-7) and (2,7) where the circle touches those points - but then the first count is 68 and not 52. It is counting the two squares that touch each of those points and thus adding 16 to the total. How can I reject those situations and just count the squares where the curve actually crosses into a square? $\endgroup$
    – 1729taxi
    Mar 17, 2023 at 15:20
  • $\begingroup$ @1729taxi, please see the update. $\endgroup$
    – kglr
    Mar 18, 2023 at 1:48
  • $\begingroup$ Fantastic. This is the sort of thing I have never done in Mathematica - your help is much appreciated. I shall accept this answer. $\endgroup$
    – 1729taxi
    Mar 18, 2023 at 7:44
  • $\begingroup$ If I make my square a curve (of side length 7) then the second returned number should be zero - _Point does not work then - I tried replacing with _Line and it just gives the result of 4 - do you know how to detect this situation but return the correct number of zero? $\endgroup$
    – 1729taxi
    Mar 19, 2023 at 11:46
5
$\begingroup$

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

enter image description here

Original

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

enter image description here

$\endgroup$
1
  • $\begingroup$ Excellent - I'll look through this in more detail later - family wedding this weekend is taking up my time. I do appreciate this. I went ahead and accepted kglr's answer primarily through brevity but, again, thanks for your food for thought. $\endgroup$
    – 1729taxi
    Mar 18, 2023 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.