c++ - 【算法】大量格点数中给定一个点，画半径为R的圆，得到圆中各个格点的坐标

Question

如下图所示：圆心不一定会落在格点（每个格点都有坐标）上。格点的数据量很大，不太可能用最笨的全局利用圆公式进行与R比较得出圆内的各个格点的坐标。各位特别是搞计算机图形学（CG）的朋友，有没有比较好的算法，需要效率比较高。获取可以给出相关资料，我自己去看。

Answer 1

If I understand correctly, your problem is that the grid points are fixed and very large, and your circle is your input. Given a circle, find the grid points that fall within it.
You can first transform the problem into finding "those points that fall on the circumscribed rectangle of the circle". This problem is relatively easy to solve, such as indexing grid points, KD-Tree, quad-tree and so on. Then traverse it again and use the equation of the circle to filter out unsatisfied points.

Answer 2

There are many ways to build a spatial index, such as geohash

Answer 3

Let me give you an idea. Assume that the input data is three floating point numbers X, Y, R representing the center coordinates and radius of the circle. Then the X' coordinate of the integer point within the circle is in [X-R, X+R]. For For each X', bisect the minimum ordinate Y' and the maximum ordinate Y'' that meet the conditions. Then for the same X', all Ys between Y' and Y'' satisfy the conditions.

Answer 4

I don’t know what field your algorithm will be used in?
In fact, in computer graphics, this kind of problem is usually solved using the stupidest method of brute force calculation using R, because this problem is highly parallel, and whether each point is inside the circle depends on whether another point is. relational and therefore very suitable for GPU computing. Write an example of GLSL. (Not debugged, not guaranteed to be correct.)

in vec2 vertex;
out int inside;
uniform vec2 center;
uniform double r;
float distance(vec2 a, vec2 b)
{
//略
}
void main(void)
{
if(distance(center,vertex)>r)
inside = 0;
else 
inside = 1;
}

Then use a function to stuff the grid point array into the video memory. This shader will automatically process all points in parallel and return whether each point is within the circle. I don’t know if there are better CPU algorithms, but GPUs are generally very efficient in processing such highly parallel data and are unlikely to become an efficiency bottleneck.

Answer 5

For x,y,z in ［-r, r］:
     if x^2+y^2+z^2-r^2<0
         （x,y,z）is within sphere
     Vice versa

It can be written in the shader. In addition, if the coordinates of the ball are not at the origin, just add a translation matrix to move to that point.

Answer 6

Search for "Breshmen Midpoint Circle Drawing Method" by yourself
It talks about how to quickly calculate the coordinates of the 1/8 semicircle point in the first quadrant given the radius and coordinates, and the rest is calculated through mirroring
In any computer graphics textbook There should be detailed explanations