問題描述

希望能在球上獲得均勻分布, 或者 每兩個點之間的間距不小于某個值的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個點需要四個小時。結果畫圖：