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

Question

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

Answer 1

如果我理解的没错的话，你的问题是，格点是固定的而且很大，而你的圆就是你的输入，给定一个圆，找出落在里面的格点。
可以先把问题转化成找 “落在圆的外切矩形的那些点”。这个问题相对好做，比如对格点建索引，KD-Tree，quad-tree 什么的。之后再遍历一遍，用圆的方程筛掉不满足的点。

Answer 2

建空间索引，方法很多比如geohash

Answer 3

说一个思路，假设输入数据是三个浮点数X, Y, R表示圆心坐标和半径，那么满足在圆内的整数点的X'坐标在[X-R, X+R]之中，对于每一个X'，二分出满足条件的最小纵坐标Y'和最大纵坐标Y''，则对于同一个X'，Y'到Y''之间所有的Y均满足条件。

Answer 4

不知道你这个算法要用在什么领域里？
实际上，在计算机图形学里，这种问题一般都是用最笨的用R暴力计算的方法的，因为这个问题高度并行，每一个点是否在圆内部都和另一个点是没有关系的，因此非常适合GPU计算。写个GLSL的示例。（未调试，不保证正确。）

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

然后用一个函数把格点数组塞进显存，这个shader就会自动并行处理所有的点并返回每个点是否在圆内。有没有更好的CPU算法我不知道，但是GPU处理这样高度并行的数据一般非常高效，很难成为效率瓶颈。

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

可以写在 shader 里，另外如果如果球的坐标不在原点，加一个平移矩阵挪到那个点就好了。

Answer 6

自行搜索 "Breshmen中点画圆法"
讲的是给半径和坐标如何快速求解第一象限上1/8半圆点的坐标，其余通过镜像计算
任意计算机图形学教材中应该都有详解