[Algorithm] Given a point in a large number of grid points, draw a circle with radius R to obtain the coordinates of each grid point in the circle

  c++, question

As shown in the following figure, the center of the circle does not necessarily fall on the grid point (each grid point has coordinates). The amount of grid data is very large, so it is unlikely to use the stupidest global circle formula to compare with R to obtain the coordinates of each grid point in the circle. Do you, especially those who are engaged in computer graphics (CG), have any better algorithms that require higher efficiency? Get the relevant information that can be given, and I will look at it myself.


If I understand correctly, your problem is that grid points are fixed and large, and your circle is your input. Given a circle, find the grid points that fall inside.
You can first turn the problem into finding “those points that fall on the circumscribed rectangle of the circle.” This problem is relatively easy to do, such as indexing grid points, KD-Tree, quad-tree, etc. Then go through it again and use the equation of circle to screen out the unsatisfied points.