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_{ilt{}j}frac{1}{d^2(i,j)}$$

這樣既突出了相鄰點間距又保持函數相對平滑。

我用的是Mathematica提供的NMinimize函數，點數比較多時需要很長計算。例如在我機器上算160點要四個小時。結果畫圖：