Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

计算球面上的随机坐标

  要从球面上获取一个随机坐标可不是件容易的事情。也许你会觉得绘制球体是很容易的,但是你有没有发现我们绘制球体时用的坐标分布是不均匀的。靠近极点的坐标就特别密集,在赤道上的坐标就特别稀疏。这是因为经线全是大圆,而纬线未必是大圆的缘故。
  如果我们在每一条纬线上的顶点数都相同,那么纬度越高的地方纬线的周长就越小(南北回归线的周长就比赤道短的多),顶点分布就越密集。在极点上,纬线甚至就是一个点。这样的构造显然是不均匀的,我们需要的是随机分布,当然需要均匀的分布。所以我们无法使用绘制球体时的方法来计算随机坐标。下面这个图就能很直观的看出顶点接近极点时分布的密集性。

  所有的经线都是经过两个极点的它是大圆(Great Circle),而纬线只有赤道的那一条是大圆,这就是分布无法均匀的原因。要让分布均匀,我们必须全都使用大圆。而使用大圆就意味着垂直于某个坐标平面,比如所有的经线圆都垂直于zx平面(我的坐标系高是y轴的)。我们可以抛弃纬线找到其它类似经线的大圆们,这就可以联想到欧拉角。只要对一个坐标随机的旋转3次就可以把它旋转到任意位置。使用欧拉角就可以得到均匀分布的随机坐标,但是欧拉角的计算是一个三阶矩阵,计算量会很大。它确实是一种数学上的解决方法,但是不是编程上的好方法。
  我在网络上搜索了下,找到了另一种算法,虽然平均计算量比欧拉角的方法低,但是稳定性就有问题了。这个方法是用一个循环来找到一个在球体内部的点,然后把这个点的坐标归一化得到单位法向量,也就是单位球体的表面坐标。但是用循环找一个球体内部的点,这个操作的时间复杂度是概率性很强的,所以这个算法的稳定性存在问题。下面是代码,知道原理即可,不要吐槽优化。 var coord=(function(){
  var x,y,z,s,n;
  do{
    x=Math.random();
    y=Math.random();
    z=Math.random();
    s=x*x+y*y+z*z;
  }while(s>1);
  n=Math.sqrt(s);
  return [x/n,y/n,z/n];
})();
  其实除了这些以外,我们也可以从绘制球体的思路出发找到一个获取球面随机点坐标的算法。在遍历球面时我们要使用两个参数,θ是遍历半个经线,φ是遍历纬线。但是接近两极的地方纬线就变短了,如果θ随机到两极的概率和赤道的概率相同就会得到两极较密集的分布。正常情况下我们在每条纬线上的顶点数量都是相同的,或者说随机点落在每条纬线上的概率是相同的。在这里,纬线本身的长度就被无视掉了。而纬线的周长是它自身半径的2π倍,2π是个常数可以作为齐次项处理掉。也就是说我们平时没有考虑到纬线自身的半径,只是把球上的顶点当做圆柱来计算了。
  现在我们注意一下纬线的半径从北极到南极的变化。它是圆弧上的,所以一定是cos或者sin。而我习惯把北极点当做0度,0度的时候半径是0所以是sin,如果使用赤道作为0度这里就是cos。也就是说,默认顶点在两极集中是被sin或cos分布上去的。那么,我们只要对这一步加个反三角函数来处理就行了。比如我的程序就是θ=asin(2rnd-1)+π/2。因为asin其实只是-π到π上的sin反函数,而我的程序是从0到2π的,所以asin值需要加上π/2。还可以根据反三角函数的性质把它化简成acos(1-2rnd)。如果纬度半径变化是使用cos函数,那么θ的取值就是acos(2rnd-1),这就不用做sin那样的调整了,因为你已经使用了-π到π的区间。函数中的rnd是[0,1)区间的随机数所以需要做乘2减1,把它转换成反三角函数的定义域-1到1上。最后是这个算法的代码
var coord=(function(){
  var a,b,l;
  a=Math.acos(1-2*Math.random()),b=Math.random()*Math.PI*2;
  l=Math.sin(a);
  return [Math.sin(b)*l,Math.cos(a),Math.cos(b)*l];
})();
网名:
54.224.247.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^