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

Question

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

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

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

Answer 1

Tidak sukar untuk mencapai pensampelan seragam pada sfera Hanya gunakan pembolehubah rawak teragih normal untuk menjana vektor tiga dimensi dan kemudian menyatukannya.

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

Tetapi saya tidak tahu sama ada ia memenuhi keperluan antara titik bersebelahan. Jika anda ingin memastikan bahawa titik bersebelahan berada jauh, anda boleh belajar daripada idea seperti
kegelisahan atau pensampelan berstrata.

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

Selain itu, sfera.txt yang disimpan boleh dibuka dengan CloudCompare untuk melihat awan titik.

Answer 2

Tujuan soalan adalah untuk menjadikan jarak antara titik pada sfera seluas mungkin, dan taburan rawak seragam tidak dapat menjamin bahawa dua titik dengan jarak yang sewenang-wenangnya kecil tidak akan muncul, jadi soalan ini tidak ada kena mengena dengan rawak pengedaran pada sfera (tajuknya terlalu menipu).

Ia adalah perkataan yang panjang apabila bercakap tentang pengedaran seragam dan rawak pada sfera. Saya hairan dengan algoritma ajaib yang diberikan oleh @lianera tadi. Mengapa menggunakan taburan normal? Kemudian, saya mendapat gambaran tentang petunjuk daripada penyatuan: Penyatuan sebenarnya ialah unjuran pengagihan volum ke sfera. Oleh kerana taburan normal adalah simetri sfera, ia mesti seragam apabila ditayangkan ke sfera. Dalam erti kata lain, Apa yang benar-benar penting ialah simetri sfera taburan, dan bentuk khusus tidak penting. Contohnya, jika kawasan dalam bulatan diagihkan secara seragam dan diunjurkan, taburan seragam pada bulatan boleh diperolehi:

Kod Sfera

Setelah mencari dalam talian, saya mendapati bahawa masalah ini mempunyai asal usul Ia dipanggil masalah Tamme, dan penyelesaian kepada masalah itu dipanggil "kod sfera". Berikut adalah beberapa keputusan yang dikira. Pada masa yang sama, kami juga tahu bahawa sangat sukar untuk mencari dan membuktikan penyelesaian yang optimum apabila terdapat banyak mata. Jadi pemegang soalan hanya boleh mencari penyelesaian sub-optimum yang baik.

Pautan yang diberikan oleh penyoal sebenarnya berdasarkan strategi susun rata-rata: bahagikan sfera kepada beberapa bulatan sama rata dengan garis latitud, dan kemudian bahagikan setiap bulatan kepada sudut yang sama, tetapi terdapat lebih sedikit titik di atas bulatan pada latitud tinggi. Terdapat lebih banyak di latitud yang lebih rendah.

Soalan yang paling berharga

Untuk mendapatkan hasil yang lebih baik, anda boleh menggunakan pelbagai kit alat pengoptimuman untuk mencari nilai maksimum jarak minimum antara titik sfera. Jika fungsi objektif ditulis secara langsung dalam bentuk jarak minimum antara titik sfera, fungsi tersebut akan mempunyai kestabilan yang lemah dan sukar untuk mencari penyelesaian yang optimum. Di sini, fungsi objektif diambil sebagai jumlah salingan kuasa dua semua jarak titik dan nilai minimum ditemui:

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

Ini bukan sahaja menyerlahkan jarak antara titik bersebelahan tetapi juga memastikan fungsinya agak lancar.

Saya menggunakan fungsi yang disediakan oleh MathematicaNMinimize Apabila banyak mata, ia mengambil masa yang lama untuk mengira. Sebagai contoh, ia mengambil masa empat jam untuk mengira 160 mata pada mesin saya. Lukisan keputusan: