我需要一个算法,可以给我一个球体周围的位置N点(可能小于20)模糊地展开它们 . 没有必要“完美”,但我只需要它,所以它们都不会聚在一起 .
-
This question提供了良好的代码,但我找不到制作这种制服的方法,因为这似乎是100%随机化的 .
-
This blog post推荐有两种允许在球体上输入点数的方法,但Saff and Kuijlaars算法完全在我可以转录的伪代码中,而code example我发现包含"node[k]",我无法看到解释并破坏了这种可能性 . 第二个博客的例子是Golden Section Spiral,它给了我奇怪的,揉成一团的结果,没有明确的方法来定义一个恒定的半径 .
来自this question的 -
This algorithm似乎可以正常工作,但我可以在该页面上't piece together what'进入psuedocode或其他任何东西 .
我遇到的一些其他问题主题是随机均匀分布,这增加了我不关心的复杂程度 . 我很抱歉这是一个如此愚蠢的问题,但我想表明我真的很努力,但仍然很短暂 .
所以,我正在寻找的是简单的伪代码,可以在单位球体周围均匀分布N个点,这些点可以返回球形或笛卡尔坐标 . 如果它甚至可以通过一些随机化分布甚至更好(想想围绕恒星的行星,分散得很好,但有余地的余地) .
14 回答
在this example code
node[k]
只是第k个节点 . 您正在生成数组N个点,node[k]
是第k个(从0到N-1) . 如果这一切让您感到困惑,希望您现在可以使用它 .(换句话说,
k
是一个大小为N的数组,它在代码片段开始之前定义,并包含一个点列表) .或者,在此处构建另一个答案(并使用Python):
如果你绘制它,你会看到在极点附近的垂直间距更大,这样每个点位于大约相同的总空间面积(靠近极点的地方空间更小"horizontally",所以它给出更多"vertically") .
这与所有与他们的邻居有相同距离的点(这是我认为你的链接所讨论的)并不相同,但它可能足以满足您的需求,并且只需制作统一的lat / lon网格即可 .
Fibonacci球体算法非常适合这种情况 . 它速度快,结果一目了然很容易愚弄人眼 . You can see an example done with processing将随着时间的推移显示结果 . Here's another great interactive example由@gman制作 . 这是一个带有简单随机选项的快速python版本:
1000个样本给你这个:
这被称为球体上的包装点,并且没有(已知的)通用的完美解决方案 . 但是,有很多不完美的解决方案 . 最受欢迎的三个似乎是:
Create a simulation . 将每个点视为约束到球体的电子,然后运行模拟一定数量的步骤 . 电子的排斥自然会使系统趋向于更稳定的状态,在这种状态下,这些点可以得到的距离彼此相差很远 .
Hypercube rejection . 这种奇特的方法实际上非常简单:你在球体周围的立方体内统一选择点(远远超过它们的
n
),然后拒绝球体外的点 . 将剩余的点视为向量,并将它们标准化 . 这些是你的"samples" - 使用某种方法选择n
(随机,贪婪等) .Spiral approximations . 您在球体周围追踪螺旋线,并均匀分布螺旋线周围的点 . 由于涉及数学,这些比模拟更复杂,但更快(并且可能涉及更少的代码) . 最受欢迎的似乎是Saff, et al .
有关此问题的更多信息可以在here找到
金色螺旋方法
你说你无法让黄金螺旋方法起作用,这是一种耻辱,因为它真的非常非常好 . 我想让你完全理解它,这样你就可以理解如何避免被“束缚” .
所以这是一种快速,非随机的方法来创建一个近似正确的晶格;如上所述,没有格子是完美的,但这可能是"good enough" . 将其与其他方法进行比较,例如在BendWavy.org但它只是有一个漂亮和漂亮的外观,以及在极限内均匀间距的保证 .
底漆:单位圆盘上的向日葵螺旋
为了理解这个算法,我首先邀请您来看看2D向日葵螺旋算法 . 这是基于这样一个事实,即最无理的数字是黄金比率
(1 + sqrt(5))/2
如果通过方法发出一个点"stand at the center, turn a golden ratio of whole turns, then emit another point in that direction,",一个人自然地构造了一个螺旋,当你得到越来越多的点时,它仍然拒绝拥有定义良好的"bars"点数排成一行 . (注1)磁盘上均匀间隔的算法是,
它会产生看起来像(n = 100和n = 1000)的结果:
径向间隔点
关键奇怪的是公式
r = sqrt(indices / num_pts)
;我怎么来那个? (笔记2 . )好吧,我在这里使用平方根,因为我希望这些在球体周围有均匀的区域间距 . 这就像说在大N的极限中我想要一个小区域R∈(r,r dr),θ∈(θ,θdθ)包含与其面积成比例的多个点,即rdrθ . 现在,如果我们假装我们在这里谈论一个随机变量,这有一个直截了当的解释,即(R,Θ)的联合概率密度对于某个常数c来说只是c r . 然后单位磁盘上的归一化强制c = 1 /π .
现在让我介绍一个技巧 . 它来自概率论,它被称为sampling the inverse CDF:假设您想要生成一个概率密度为f(z)的随机变量,并且您有一个随机变量U~Uniform(0,1),就像
random()
中出现的一样 . 编程语言 . 你怎么做到这一点?首先,将密度转换为cumulative distribution function F(z),记住,使用导数f(z)单调地从0增加到1 .
然后计算CDF的反函数F-1(z) .
您会发现Z = F-1(U)是根据目标密度分布的 . (注3) .
现在,黄金比率的螺旋技巧以一种非常均匀的θ模式将点分开,所以让我们把它整合出来;对于单位圆,我们留下F(r)= r2 . 因此,反函数是F-1(u)= u1 / 2,因此我们将在极坐标中使用
r = sqrt(random()); theta = 2 * pi * random()
在球体上生成随机点 .现在我们不是对这个反函数进行随机抽样,而是对其进行均匀采样,而关于均匀采样的好处是我们关于点如何在大N的极限中展开的结果将表现得好像我们随机采样它一样 . 这种组合就是诀窍 . 而不是
random()
,我们使用(arange(0, num_pts, dtype=float) + 0.5)/num_pts
,所以,如果我们想要取样10个点,那么它们就是r = 0.05, 0.15, 0.25, ... 0.95
. 我们统一采样r以获得等面积间距,并且我们使用向日葵增量来避免输出中可怕的"bars"点 .现在在球体上做向日葵
我们需要通过点来点球体的变化仅涉及切换球坐标的极坐标 . 当然,径向坐标不是单位球面上的 . 为了使这里的事情更加一致,即使我被训练为物理学家,我也需要坐标,其中0≤φ≤π是从极点下来的纬度,0≤θ≤2π是经度 . 所以与上面的区别在于我们基本上用φ替换变量r .
我们的面积元素是rdrdθ,现在变成了不那么复杂的sin(φ)dφdθ . 所以我们的均匀间距的连接密度是sin(φ)/4π . 积分θ,我们发现f(φ)= sin(φ)/ 2,因此F(φ)=(1-cos(φ))/ 2 . 反过来我们可以看到一个均匀的随机变量看起来像acos(1 - 2 u),但我们均匀地采样而不是随机,所以我们改为使用φk= acos(1 - 2(k 0.5)/ N) . 算法的其余部分只是将其投影到x,y和z坐标上:
同样,对于n = 100和n = 1000,结果如下:
注意事项
z + 1/(n_1 + 1/(n_2 + 1/(n_3 + ...)))
其中z
是一个整数,n_1, n_2, n_3, ...
是有限或无穷大的正整数序列:由于分数部分
1/(...)
总是在0和1之间,连续分数中的大整数允许特别好的有理逼近:"one divided by something between 100 and 101"优于"one divided by something between 1 and 2."因此最无理数是1 + 1/(1 + 1/(1 + ...))
并且没有特别好的有理逼近;通过乘以φ可以求解φ= 1 1 /φ,得到黄金比例的公式 .对于不太熟悉NumPy的人 - 所有函数都是"vectorized",因此
sqrt(array)
与其他语言可能编写的map(sqrt, array)
相同 . 所以这是一个按组件分组的sqrt
应用程序 . 同样也适用于标量划分或添加标量 - 这些适用于并行的所有组件 .一旦你知道这是结果,证据很简单 . 如果你问z <Z <z dz的概率是多少,这与询问z <F-1(U)<z dz的概率是一样的,将F应用于所有三个表达式,注意它是单调递增函数因此,F(z)<U <F(z dz),向右扩展以找到F(z)f(z)dz,并且因为U是均匀的,所以这个概率只是所承诺的f(z)dz .
这个答案是基于this answer所概述的'theory'我将这个答案添加为:
with N at 20:
and then N at 80:
这是准备运行的python3代码,其中仿真是相同的源:“http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere”由其他人发现 . (绘制我've included, that fires when run as ' main,'取自:http://www.scipy.org/Cookbook/Matplotlib/mplot3D)
在低计数(N,2,5,7,13等)测试,似乎工作'很好'
您正在寻找的是一种球形覆盖物 . 球形覆盖问题非常困难,除了少量的点之外,解决方案是未知的 . 有一点可以肯定的是,给定球体上的n个点,总是存在两个距离点
d = (4-csc^2(\pi n/6(n-2)))^(1/2)
或更近 .如果你想要一种概率方法来生成均匀分布在球体上的点,那么很容易:通过高斯分布统一生成空间中的点(它内置于Java中,不难找到其他语言的代码) . 所以在三维空间中,你需要类似的东西
然后通过标准化距离原点的距离将点投影到球体上
n维的高斯分布是球对称的,因此球体上的投影是均匀的 .
当然,最好生成整个集合,然后在必要时拒绝整个集合 . (或者使用"early rejection"拒绝整个集合你've generated so far; just don' t保留一些点并放弃其他点 . )你可以使用上面给出的
d
的公式,减去一些松弛,来确定点之间的最小距离,在这之下你将拒绝一组点 . 你很难说怎么做,所以运行一个模拟来感受相关的统计数据 .尝试:
上述函数应该在循环中运行,具有N个循环总和k循环电流迭代 .
它基于向日葵种子图案,除了向日葵种子弯曲成半圆顶,并再次成为球形 .
这是一张照片,除了我把相机放在球体的一半,所以它看起来是2d而不是3d,因为相机与所有点的距离相同 . http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg
你可以运行模拟的点数很少:
取
N
的两个最大因子,如果N==20
那么两个最大因子是{5,4}
,或者更一般地{a,b}
. 计算把你的第一个点放在
{90-dlat/2,(dlong/2)-180}
,你的第二个点位于{90-dlat/2,(3*dlong/2)-180}
,你的第三个点位于{90-dlat/2,(5*dlong/2)-180}
,直到你've tripped round the world once, by which time you'到达{90-3*dlat/2,(dlong/2)-180}
时,你去了{90-3*dlat/2,(dlong/2)-180}
.显然,我在球形地球表面上以度为单位工作,通常用于平移/ - 到N / S或E / W.显然,这给你一个完全非随机的分布,但它是统一的,并且点不会聚集在一起 .
为了增加一定程度的随机性,你可以生成2个正态分布(适当的平均0和std dev为{dlat / 3,dlong / 3})并将它们添加到均匀分布的点 .
edit: 这并没有回答OP打算提出的问题,请将其留在这里以防人们发现它有用 .
我们使用概率的乘法规则,结合无穷的动物 . 这导致2行代码实现您期望的结果:
(在以下坐标系中定义:)
您的语言通常具有统一的随机数基元 . 例如,在python中,您可以使用
random.random()
返回[0,1)
范围内的数字 . 您可以将此数字乘以k,以获得[0,k)
范围内的随机数 . 因此在python中,uniform([0,2pi))
意味着random.random()*2*math.pi
.Proof
现在我们不能统一分配θ,否则我们会在极点处聚集 . 我们希望分配与球形楔形表面积成比例的概率(该图中的θ实际上是φ):
赤道处的角位移dφ将导致位移dφ* r . 那个位移在任意方位θ上会是什么?那么,z轴的半径是
r*sin(θ)
,所以与楔形相交的"latitude"的arclength是dφ * r*sin(θ)
. 因此,我们通过将切片的区域从南极到北极进行积分来计算从中采样的区域的cumulative distribution .(其中stuff =
dφ*r
)我们现在将尝试获取CDF的反转样本:http://en.wikipedia.org/wiki/Inverse_transform_sampling首先,我们将几乎CDF除以其最大值进行归一化 . 这具有抵消dφ和r的副作用 .
从而:
或者......放置20个点,计算二十面体面的中心 . 对于12个点,找到二十面体的顶点 . 对于30点,二十面体边缘的中点 . 你可以用四面体,立方体,十二面体和八面体做同样的事情:一组点位于顶点上,另一组位于面的中心,另一组位于边缘的中心 . 但是,他们不能混在一起 .
Healpix解决了一个密切相关的问题(用等面积像素对球体进行像素化):
http://healpix.sourceforge.net/
它可能有点过分,但也许在看完之后你就会发现其中一些其他不错的属性对你来说很有趣 . 它不仅仅是一个输出点 Cloud 的函数 .
我降落在这里试图再次找到它; “healpix”这个名字并不能完全唤起领域......
这很有效,而且非常简单 . 尽可能多的要点: