84669 personnes étudient
152542 personnes étudient
20005 personnes étudient
5487 personnes étudient
7821 personnes étudient
359900 personnes étudient
3350 personnes étudient
180660 personnes étudient
48569 personnes étudient
18603 personnes étudient
40936 personnes étudient
1549 personnes étudient
1183 personnes étudient
32909 personnes étudient
如下图所示:圆心不一定会落在格点(每个格点都有坐标)上。格点的数据量很大,不太可能用最笨的全局利用圆公式进行与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半圆点的坐标,其余通过镜像计算任意计算机图形学教材中应该都有详解
如果我理解的没错的话,你的问题是,格点是固定的而且很大,而你的圆就是你的输入,给定一个圆,找出落在里面的格点。
可以先把问题转化成找 “落在圆的外切矩形的那些点”。这个问题相对好做,比如对格点建索引,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半圆点的坐标,其余通过镜像计算
任意计算机图形学教材中应该都有详解