84669인 학습
152542인 학습
20005인 학습
5487인 학습
7821인 학습
359900인 학습
3350인 학습
180660인 학습
48569인 학습
18603인 학습
40936인 학습
1549인 학습
1183인 학습
32909인 학습
如下图所示：圆心不一定会落在格点（每个格点都有坐标）上。格点的数据量很大，不太可能用最笨的全局利用圆公式进行与R比较得出圆内的各个格点的坐标。各位特别是搞计算机图形学（CG）的朋友，有没有比较好的算法，需要效率比较高。获取可以给出相关资料，我自己去看。
人生最曼妙的风景，竟是内心的淡定与从容！
如果我理解的没错的话，你的问题是，格点是固定的而且很大，而你的圆就是你的输入，给定一个圆，找出落在里面的格点。可以先把问题转化成找 “落在圆的外切矩形的那些点”。这个问题相对好做，比如对格点建索引，KD-Tree，quad-tree 什么的。之后再遍历一遍，用圆的方程筛掉不满足的点。
建空间索引，方法很多比如geohash
说一个思路，假设输入数据是三个浮点数X, Y, R表示圆心坐标和半径，那么满足在圆内的整数点的X'坐标在[X-R, X+R]之中，对于每一个X'，二分出满足条件的最小纵坐标Y'和最大纵坐标Y''，则对于同一个X'，Y'到Y''之间所有的Y均满足条件。
不知道你这个算法要用在什么领域里？实际上，在计算机图形学里，这种问题一般都是用最笨的用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处理这样高度并行的数据一般非常高效，很难成为效率瓶颈。
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 里，另外如果如果球的坐标不在原点，加一个平移矩阵挪到那个点就好了。
自行搜索 "Breshmen中点画圆法"讲的是给半径和坐标如何快速求解第一象限上1/8半圆点的坐标，其余通过镜像计算任意计算机图形学教材中应该都有详解
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
如果我理解的没错的话，你的问题是，格点是固定的而且很大，而你的圆就是你的输入，给定一个圆，找出落在里面的格点。
可以先把问题转化成找 “落在圆的外切矩形的那些点”。这个问题相对好做，比如对格点建索引，KD-Tree，quad-tree 什么的。之后再遍历一遍，用圆的方程筛掉不满足的点。
建空间索引，方法很多比如geohash
说一个思路，假设输入数据是三个浮点数X, Y, R表示圆心坐标和半径，那么满足在圆内的整数点的X'坐标在[X-R, X+R]之中，对于每一个X'，二分出满足条件的最小纵坐标Y'和最大纵坐标Y''，则对于同一个X'，Y'到Y''之间所有的Y均满足条件。
不知道你这个算法要用在什么领域里？
实际上，在计算机图形学里，这种问题一般都是用最笨的用R暴力计算的方法的，因为这个问题高度并行，每一个点是否在圆内部都和另一个点是没有关系的，因此非常适合GPU计算。写个GLSL的示例。（未调试，不保证正确。）
然后用一个函数把格点数组塞进显存，这个shader就会自动并行处理所有的点并返回每个点是否在圆内。有没有更好的CPU算法我不知道，但是GPU处理这样高度并行的数据一般非常高效，很难成为效率瓶颈。
可以写在 shader 里，另外如果如果球的坐标不在原点，加一个平移矩阵挪到那个点就好了。
自行搜索 "Breshmen中点画圆法"
讲的是给半径和坐标如何快速求解第一象限上1/8半圆点的坐标，其余通过镜像计算
任意计算机图形学教材中应该都有详解