c++ - 【算法】大量格点数中给定一个点,画半径为R的圆,得到圆中各个格点的坐标
黄舟
黄舟 2017-04-17 13:06:09
0
6
825

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

黄舟
黄舟

人生最曼妙的风景,竟是内心的淡定与从容!

répondre à tous(6)
阿神

如果我理解的没错的话,你的问题是,格点是固定的而且很大,而你的圆就是你的输入,给定一个圆,找出落在里面的格点。
可以先把问题转化成找 “落在圆的外切矩形的那些点”。这个问题相对好做,比如对格点建索引,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 里,另外如果如果球的坐标不在原点,加一个平移矩阵挪到那个点就好了。

PHPzhong

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

Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!