1
$\begingroup$

We have an ellipse or a circle:

How many integer pair points (points with coordinate (x,y) where both x and y are integers) can be found inside this ellipse?

Example with a circle (special form of an ellipse):

R=1 points=1 (0,0)

R=2 points=5 (0,0) (1,0) (0,1) (-1,0) (0,-1)

R=3 points=9 ...

Would like to have a generic function with visualization which takes in variables for the Ellipse: (h,k) and radius r1, r2 and circle (h,k) and r.

I am getting 14 for the ellipse here:

Count[Flatten[Table[{x, y}, {x, 0, 4}, {y, 0, 5}], 
  1], {x_, y_} /; (1/3.5)*(x - 1.8)^2 + (1/6.1)*(y - 2.3)^2 < 1]

14

Although this goes up on the first quadrant, but the shape size and hence the points stay intact! Note the ranges used are maximum that surround the shape. In fact it will not matter the range used as the condition will sandwich it at the end with the same answer. As long as the range is greater than the shape edges.

Thanks

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ You've been a member for 5 years. What have you tried? $\endgroup$
    – JimB
    Commented Apr 4 at 0:44
  • 1
    $\begingroup$ The ellipsoid depend on four parameter {h,k},r1,r2. $\endgroup$
    – cvgmt
    Commented Apr 4 at 0:49
  • $\begingroup$ Agreed...updated to reflect $\endgroup$
    – Steve237
    Commented Apr 4 at 1:08
  • $\begingroup$ Gave it a shot @JimB Good point! $\endgroup$
    – Steve237
    Commented Apr 4 at 1:22
  • 1
    $\begingroup$ Try this Solve[(1/3.5)*(x - 1.8)^2 + (1/6.1)*(y - 2.3)^2 < 1 // Rationalize, {x, y}, Integers] // Length $\endgroup$
    – yarchik
    Commented Apr 4 at 5:25

2 Answers 2

Reset to default
4
$\begingroup$

Brute force.

create ellipse region:

ellipseRegion[pt : {x_, y_}, radii : {r1_, r2_}] := 
 ellipseRegion[pt, radii] = Region[Disk[pt, radii]]

function to count how many points in list are in region:

countPoints[center : {x_, y_}, radii : {r1_, r2_}][pointList_] := 
 Length[Select[#, 
     Function[{pt}, 
      RegionMember[ellipseRegion[center, radii], pt]]]] &[pointList]

Construct integer 2-tuples for bounding box and count:

latticePointsIn[center : {x_, y_}, radii : {r1_, r2_}] := 
 With[{tuples = 
    Tuples[Range @@ ({-1, 1} Max[Ceiling[radii]]), 2] + 
     Threaded[{x, y}]},
  countPoints[center, radii][tuples]

example

latticePointsIn[{5, 6}, {12, 18}] (*669*)
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ For your last example I get different results Count[Flatten[Table[{x, y}, {x, -30, 30}, {y, -30, 30}], 1], {x_, y_} /; (1/12)^2*(x - 5)^2 + (1/18)^2*(y - 6)^2 < 1] yields 665 and Solve[(1/12)^2*(x - 5)^2 + (1/18)^2*(y - 6)^2 < 1 // Rationalize, {x, y}, Integers] // Length likewise yields 665. $\endgroup$
    – yarchik
    Commented Apr 4 at 5:24
  • 1
    $\begingroup$ @yarchik, I think the difference is at the boundary. Try Graphics[ { Point[Tuples[Range[-12, 25], 2]], Circle[{5, 6}, {12, 18}], {Red, PointSize[0.02], Point[Select[Tuples[Range[-12, 25], 2], RegionMember[Disk[{5, 6}, {12, 18}], #] &]]}, {Blue, Circle[SolveValues[(1/12)^2*(x - 5)^2 + (1/18)^2*(y - 6)^2 < 1 // Rationalize, {x, y}, Integers], .3]} }, Frame -> True ] and then try switching the SolveValue's < to <= $\endgroup$
    – Craig Carter
    Commented Apr 4 at 10:15
  • $\begingroup$ Right. I do not know what the poster prefers, but they are using < in their code. Is it possible to exclude these point with your method? $\endgroup$
    – yarchik
    Commented Apr 4 at 10:19
  • $\begingroup$ Please, ignore my previous comment. This post will likely be closed because it is a duplicate. $\endgroup$
    – yarchik
    Commented Apr 4 at 10:23
  • 1
    $\begingroup$ Right. I suppose that one could substitute SignedRegionDistance to deal with the boundary. I prefer your Solve method to the brute force method for this case. If the region were more complex, then brute force may be the best route. But, moot point... $\endgroup$
    – Craig Carter
    Commented Apr 4 at 10:31
2
$\begingroup$

We can write the equation for an ellipse like {x,y}.metric.{x,y}, where metric={{1/r1^2,0},{0,1/r2^2}}.

Then a function that displays the ellipse and counts the integer points inside:

getPts[x0_, y0_, r10_, r20_] := 
 Module[{metric, x1 = Round[x0], y1 = Round[y0], r1 = Ceiling[r10], 
   r2 = Ceiling[r20], c, x, y},
  metric = {{1/r10^2, 0}, {0, 1/r20^2}};
  pts = Flatten[
    Table[{x, y}, {x, x1 - r1 - 1, x1 + r1 + 1}, {y, y1 - r2, y1 + r2}],
     1];
  ParametricPlot[{r10 Cos[ph], r20 Sin[ph]} + {x0, y0}, {ph, 0, 2 Pi},
     Epilog -> Point[pts]] / Print;
  c = CountsBy[pts, (# - {x0, y0}) . metric . (# - {x0, y0}) < 1 &][
    True];
  (*Select[pts,(#-{x0,y0}).metric.(#-{x0,y0})<1&];*)
  c
  ]

Now with this and the data from the question:

getPts[1.8, 2.3, Sqrt[3.5], Sqrt[6.1]]

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.