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

Question

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

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

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

Answer 1

Il n'est pas difficile d'obtenir un échantillonnage uniforme sur une sphère. Il suffit d'utiliser des variables aléatoires distribuées normales pour générer des vecteurs tridimensionnels, puis de les unifier.

#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;
}

Mais je ne sais pas s’il répond aux exigences entre points adjacents. Si vous voulez vous assurer que les points adjacents sont éloignés, vous pouvez tirer des leçons d'idées telles que le
gigue ou l'échantillonnage stratifié.

Version 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);
        }
    }
}

De plus, le fichiersphere.txt enregistré peut être ouvert avec CloudCompare pour afficher les nuages ​​de points.

Answer 2

Le but de la question est de rendre la distance entre les points de la sphère aussi grande que possible, et une distribution aléatoire uniforme ne peut garantir que deux points avec une distance arbitrairement petite n'apparaîtront pas, donc cette question n'a rien à voir avec le hasard répartition sur la sphère (le titre est trop trompeur).

C’est un long mot lorsqu’il s’agit de répartition uniforme et aléatoire sur une sphère. Je suis intrigué par l'algorithme magique donné plus tôt par @lianera. Pourquoi utiliser la distribution normale ? Plus tard, j'ai eu un aperçu des indices de l'unitisation : L'unitisation est en fait la projection de la distribution du volume sur la sphère. La distribution normale étant à symétrie sphérique, elle doit être uniforme une fois projetée sur la sphère. En d'autres termes, Ce qui compte vraiment, c'est la symétrie sphérique de la distribution, et la forme spécifique n'a pas d'importance. Par exemple, si la zone à l'intérieur d'un cercle est uniformément répartie et projetée, la répartition uniforme sur le cercle peut être obtenue :

Codes sphériques

Après une recherche en ligne, j'ai découvert que ce problème a une certaine origine. Il s'appelle le problème de Tamme, et la solution au problème s'appelle "codes sphériques". Voici quelques résultats calculés. En même temps, nous savons aussi que il est très difficile de trouver et de prouver la solution optimale lorsqu'il y a de nombreux points. Ainsi, le porteur de la question peut simplement trouver une bonne solution sous-optimale.

Le lien donné par l'interrogateur est en fait basé sur une stratégie d'empilement moyenne : diviser la sphère en plusieurs cercles de manière égale avec des lignes de latitude, puis diviser chaque cercle en angles égaux, mais il y a moins de points au-dessus des cercles aux hautes latitudes. Il y en a davantage aux basses latitudes.

La question la plus précieuse

Pour obtenir de meilleurs résultats, vous pouvez utiliser diverses boîtes à outils d'optimisation pour trouver la valeur maximale de la distance minimale entre les points sphériques. Si la fonction objectif est écrite directement sous la forme de la distance minimale entre des points sphériques, la fonction aura une mauvaise stabilité et il sera difficile de trouver la solution optimale. Ici, la fonction objectif est prise comme la somme des réciproques des carrés de tous les espacements de points et la valeur minimale est trouvée :

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

Cela met non seulement en évidence la distance entre les points adjacents, mais maintient également la fonction relativement fluide.

J'utilise la fonction fournie par MathematicaNMinimize Lorsqu'il y a beaucoup de points, le calcul est long. Par exemple, il faut quatre heures pour calculer 160 points sur ma machine. Résultat tirage au sort :