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

Question

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

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

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

Answer 1

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

#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打开查看点云。

Answer 2

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

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

Spherical Codes

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

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

最值问题

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

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

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

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