java - 求算法. 在球面上取随机N个均匀的点(或者间距不小于某距离的点)

问题描述

希望能在球上获得均匀分布, 或者 每两个点之间的间距不小于某个值的N个点的坐标.点的数量不需要太大, 在100到200之间就够用了.球的中心点就是坐标系原点.

有看到另外一个大牛写的.https://www.oschina.net/code/...但是传入100个点的时候, 相邻很近的点出现几率非常大. 导致在球面上的点上放东西的时候, 就叠在一起了.

求教, 有没有什么其他算法能实现.

问题解答

球面上要实现均匀采样不难，用正态分布随机变量产生三维向量再单位化就可以了。

#include <iostream>#include <fstream>#include <random>using namespace std;int main(){ std::default_random_engine gen; std::normal_distribution<float> distrib(0.f, 1.f); ofstream ofs('sphere.txt'); for (int i = 0; i < 1000; i++) {float x = distrib(gen);float y = distrib(gen);float z = distrib(gen);float r = sqrt(x*x + y*y + z*z);ofs << x / r << ’ ’ << y / r << ’ ’ << z / r << endl; } return 0;}

不过不知道满不满足相邻点之间的要求。如果要保证相邻点比较远，可以借鉴一下jittering或者stratified sampling之类的思路。

Java版

import java.util.Random;import java.io.*;class SphericalSampling{ public static void main(String[] args){Random rnd = new Random();try{ PrintWriter writer = new PrintWriter('sphere.txt', 'UTF-8'); for(int i = 0; i < 1000; i++){double x = rnd.nextGaussian();double y = rnd.nextGaussian();double z = rnd.nextGaussian();double r = Math.sqrt(x*x + y*y + z*z);writer.println(x/r + ' ' + y/r + ' ' + z/r); } }catch (Exception e) { e.printStackTrace(System.out);} }}

另外，保存的sphere.txt可以用CloudCompare打开查看点云。

题主的意思是想让球面上的点间距尽量大，而均匀随机分布无法保证不出现距离任意小的两点，所以这个题与球面上的随机分布无关（标题太坑人）。

说到球面均匀随机分布就啰嗦一句。前面@lianera给出的神奇算法我百思不得其解，为啥用正态分布？后来从单位化上窥见了端倪：单位化其实是体分布到球面的投影。因为正态分布是球对称的，因此它投影到球面上就一定是均匀的了。也就是说，真正重要的是分布的球对称性，具体形式无所谓。比如圆内的面积均匀分布投影可以得到圆上的均匀分布：

网上一搜才发现，原来这个问题还是蛮有来头的，叫做Tamme’s problem，问题的解称为“spherical codes”。这里有一些计算好的结果。同时也知道，当点数比较多时寻找和证明最优解是很困难的。所以题主找到个还不错的次优解就可以啦。

题主给出的链接其实就是基于一种平均化的码放策略：把球面用纬线平均分成若干个圆，每个圆再做等角划分，但高纬度的圆上方的点少些，低纬度的多些。

要想求得更好的结果，可以借助各种优化工具包求解球面点最小间距的最大值。目标函数直接写成球面点最小间距的形式会导致函数稳定性很差，不容易求到最优解。这里将目标函数取为所有点间距平方的倒数和并求最小值：

$$text{minimize:} quad sum_{ilt{}j}frac{1}{d^2(i,j)}$$

这样既突出了相邻点间距又保持函数相对平滑。

我用的是Mathematica提供的NMinimize函数，点数比较多时需要很长计算。比如在我机器上算160个点需要四个小时。结果画图：