問題描述

希望能在球上獲得均勻分布, 或者 每兩個點之間的間距不小于某個值的N個點的坐標.點的數(shù)量不需要太大, 在100到200之間就夠用了.球的中心點就是坐標系原點.

有看到另外一個大牛寫的.https://www.oschina.net/code/...但是傳入100個點的時候, 相鄰很近的點出現(xiàn)幾率非常大. 導致在球面上的點上放東西的時候, 就疊在一起了.

求教, 有沒有什么其他算法能實現(xiàn).

問題解答

球面上要實現(xiàn)均勻采樣不難，用正態(tài)分布隨機變量產(chǎn)生三維向量再單位化就可以了。

#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打開查看點云。

題主的意思是想讓球面上的點間距盡量大，而均勻隨機分布無法保證不出現(xiàn)距離任意小的兩點，所以這個題與球面上的隨機分布無關(guān)（標題太坑人）。

說到球面均勻隨機分布就啰嗦一句。前面@lianera給出的神奇算法我百思不得其解，為啥用正態(tài)分布？后來從單位化上窺見了端倪：單位化其實是體分布到球面的投影。因為正態(tài)分布是球?qū)ΨQ的，因此它投影到球面上就一定是均勻的了。也就是說，真正重要的是分布的球?qū)ΨQ性，具體形式無所謂。比如圓內(nèi)的面積均勻分布投影可以得到圓上的均勻分布：

網(wǎng)上一搜才發(fā)現(xiàn)，原來這個問題還是蠻有來頭的，叫做Tamme’s problem，問題的解稱為“spherical codes”。這里有一些計算好的結(jié)果。同時也知道，當點數(shù)比較多時尋找和證明最優(yōu)解是很困難的。所以題主找到個還不錯的次優(yōu)解就可以啦。

題主給出的鏈接其實就是基于一種平均化的碼放策略：把球面用緯線平均分成若干個圓，每個圓再做等角劃分，但高緯度的圓上方的點少些，低緯度的多些。

要想求得更好的結(jié)果，可以借助各種優(yōu)化工具包求解球面點最小間距的最大值。目標函數(shù)直接寫成球面點最小間距的形式會導致函數(shù)穩(wěn)定性很差，不容易求到最優(yōu)解。這里將目標函數(shù)取為所有點間距平方的倒數(shù)和并求最小值：

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

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

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