Bagaimana cara menghasilkan titik yang terdistribusi secara merata pada permukaan unit sphere 3-d?

68

Saya bertanya-tanya bagaimana cara menghasilkan titik yang terdistribusi secara merata di permukaan unit sphere 3-d? Juga setelah menghasilkan poin-poin itu, apa cara terbaik untuk memvisualisasikan dan memeriksa apakah mereka benar-benar seragam di permukaan $x^2+y^2+z^2=1$ ?

random-generation Qiang Li
sumber

Jika dengan seragam yang Anda maksud adalah "biasa", tidak ada cara untuk melakukannya di luar

n

$n$ = 2, 4, 6, 8, 12, 20.

Marcos

1

apa yang salah dengan sampel dari MultiVariateGaussian dan vektor itu hanya menormalkannya: v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))dan kemudian v = v/v.norm(10000)

Pinocchio

72

Metode standar adalah untuk menghasilkan tiga standar normal dan membangun vektor satuan dari mereka. Yaitu, ketika dan , maka didistribusikan secara seragam pada bola. Metode ini juga berfungsi dengan baik untuk bidang dimensi. $X_i \sim N(0,1)$ $\lambda^2 = X_1^2 + X_2^2 + X_3^2$ $(X_1/\lambda, X_2/\lambda, X_3/\lambda)$ $d$

Dalam 3D, Anda dapat menggunakan sampel penolakan: gambar dari distribusi seragam hingga panjang kurang dari atau sama dengan 1, lalu - sama seperti dengan metode sebelumnya - menormalkan vektor ke satuan panjang. Jumlah percobaan yang diharapkan per titik bola sama dengan = 1,91. Dalam dimensi yang lebih tinggi, jumlah uji coba yang diharapkan menjadi begitu besar sehingga dengan cepat menjadi tidak praktis. $X_i$ $[-1,1]$ $(X_1, X_2, X_3)$ $2^3/(4 \pi / 3)$

Ada banyak cara untuk memeriksa keseragaman . Cara yang rapi, meskipun agak intensif secara komputasi, adalah dengan fungsi K Ripley . Jumlah titik yang diharapkan dalam (3D Euclidean) jarak dari setiap lokasi di bola sebanding dengan luas bola dalam jarak , yang sama dengan . Dengan menghitung semua jarak antar titik, Anda dapat membandingkan data dengan yang ideal ini. $\rho$ $\rho$ $\pi\rho^2$

Prinsip umum pembuatan grafik statistik menyarankan cara yang baik untuk membuat perbandingan adalah dengan memplot residual yang distabilkan varians terhadap di mana adalah terkecil dari saling jarak dan $e_i(d_{[i]} - e_i)$ $i = 1, 2, \ldots, n(n-1)/2=m$ $d_{[i]}$ $i^\text{th}$ . Plot harus mendekati nol. (Pendekatan ini tidak konvensional.) $e_i = 2\sqrt{i/m}$

Berikut adalah gambar dari 100 undian independen dari distribusi bola seragam yang diperoleh dengan metode pertama:

100 titik bola seragam

Berikut adalah plot diagnostik jarak:

Plot diagnostik

Skala y menunjukkan bahwa nilai-nilai ini semuanya mendekati nol.

Berikut ini adalah akumulasi dari 100 plot seperti itu untuk menyarankan ukuran penyimpangan apa yang sebenarnya merupakan indikator signifikan dari ketidakseragaman:

Nilai simulasi

(Plot-plot ini terlihat sangat mengerikan seperti jembatan Brown) ... mungkin ada beberapa penemuan teoretis yang menarik yang bersembunyi di sini.)

Akhirnya, inilah plot diagnostik untuk satu set 100 titik acak yang seragam ditambah 41 titik yang hanya didistribusikan secara seragam di belahan bumi bagian atas saja:

Nilai simulasi yang tidak seragam

Relatif terhadap distribusi seragam, ini menunjukkan penurunan yang signifikan dalam jarak antar titik rata-rata ke kisaran satu belahan bumi. Itu sendiri tidak ada artinya, tetapi informasi yang berguna di sini adalah bahwa ada sesuatu yang tidak seragam pada skala satu belahan bumi. Efeknya, plot ini siap mendeteksi bahwa satu belahan memiliki kepadatan yang berbeda dari yang lain. (Tes chi-square yang lebih sederhana akan melakukan ini dengan lebih banyak kekuatan jika Anda tahu sebelumnya belahan mana yang harus diuji dari banyak kemungkinan yang tak terhingga.)

whuber
sumber

(X_{1} / λ, X_{2} / λ, X_{3} / λ)

$(X_1/\lambda, X_2/\lambda, X_3/\lambda)$

23

X \sim N (0, I_{n})

$X \sim \mathcal{N}(0, I_n)$

I_{n}

$I_n$

n \times n

$n \times n$

Q

$Q$

Q X \sim N (0, I_{n})

$Q X \sim N(0, I_n)$

X

$X$

Y = X / ‖ X ‖_{2}

$Y = X / \|X\|_2$

Y_{Q} = Q X / ‖ Q X ‖_{2} = Q X / ‖ X ‖_{2}

$Y_Q = Q X / \|Q X\|_2 = Q X / \|X\|_2$

Q

$Q$ . Karena tidak sama dengan rotasi, maka , dan karena hampir pasti, maka ia harus didistribusikan secara merata di bola.

X

$X$

Y

$Y$

‖ Y ‖_{2} = 1

$\|Y\|_2 = 1$

kardinal

3

@ Mike No, karena distribusi seragam lintang tidak memberikan distribusi seragam di bola. (Sebagian besar permukaan bola terletak di garis lintang lebih rendah di dekat Khatulistiwa jauh dari Polandia. Sebagai gantinya, Anda membutuhkan distribusi seragam .)

ϕ

$\phi$

\cos (ϕ)

$\cos(\phi)$

whuber

1

@Ahsan Karena matriks ortogonal membentuk kelompok transitif dari transformasi pelestarian area dari bola, distribusinya seragam atas subset bola dari bentuk : tetapi ini adalah seluruh bola.

X / | | X | |_{2}

$X/||X||_2$

whuber

1

@Cesar "Distribusi seragam" (di lingkup).

Whuber

19

Berikut adalah beberapa kode R yang agak sederhana

n     <- 100000                  # large enough for meaningful tests
z     <- 2*runif(n) - 1          # uniform on [-1, 1]
theta <- 2*pi*runif(n) - pi      # uniform on [-pi, pi]
x     <- sin(theta)*sqrt(1-z^2)  # based on angle
y     <- cos(theta)*sqrt(1-z^2)

Sangat sederhana untuk melihat dari konstruksi bahwa dan tetapi jika perlu diuji maka $x^2+y^2 = 1- z^2$ $x^2+y^2+z^2=1$

mean(x^2+y^2+z^2)  # should be 1
var(x^2+y^2+z^2)   # should be 0

dan mudah untuk menguji bahwa masing-masing dan terdistribusi secara merata pada ( jelas adalah) dengan $x$ $y$ $[-1,1]$ $z$

plot.ecdf(x)  # should be uniform on [-1, 1]
plot.ecdf(y)
plot.ecdf(z)

Jelas, diberi nilai , dan yang terdistribusi secara seragam di sekitar lingkaran jari-jari dan ini dapat diuji dengan melihat distribusi arang penentu rasio mereka. Tetapi karena memiliki distribusi marginal yang sama dengan dan sebagai , pernyataan yang sama berlaku untuk setiap pasangan, dan ini juga dapat diuji. $z$ $x$ $y$ $\sqrt{1-z^2}$ $z$ $x$ $y$

plot.ecdf(atan2(x,y)) # should be uniform on [-pi, pi]
plot.ecdf(atan2(y,z))
plot.ecdf(atan2(z,x))

Jika masih tidak yakin, langkah selanjutnya adalah melihat beberapa rotasi 3-D sewenang-wenang atau berapa banyak poin yang jatuh dalam sudut padat yang diberikan, tetapi itu mulai menjadi lebih rumit, dan saya pikir tidak perlu.

Henry
sumber

Saya hanya ingin tahu apakah metode Anda menghasilkan poin (x, y, z) pada dasarnya sama dengan metode whuber?

Qiang Li

3

Tidak bukan: whuber menggunakan tiga angka acak sementara saya menggunakan dua. Milik saya adalah kasus khusus "menghasilkan titik pada dengan kepadatan yang sesuai [sebanding dengan ] dan kemudian turunkan dimensi". Di sini nyaman karena ini secara resmi adalah 2-bola .

[- 1, 1]

$[-1,1]$

(1 - z^{2})^{n / 2 - 1}

$(1-z^2)^{n/2-1}$

n = 2

$n=2$

Henry

3

Atau, secara lebih umum, buat titik-titik seragam pada peta menggunakan proyeksi area-sama (milik Anda adalah area sama-silinder), lalu proyeksikan kembali. (+1)

whuber

@whuber: Memang. Offtopic, tetapi bagi siapa pun yang tertarik, saya memiliki pilihan interaktif proyeksi peta dunia di sini , beberapa di antaranya memiliki luas yang sama

Henry

2

Ini cukup banyak pendekatan standar yang digunakan dalam grafis komputer, berdasarkan Teorema Hat-Box Archimedes: mathworld.wolfram.com/ArchimedesHat-BoxTheorem.html

Edward KMETT

10

Jika Anda ingin mengambil sampel titik-titik yang terdistribusi secara merata pada bola 3D (yaitu, permukaan bola 3D), gunakan penolakan sederhana, atau metode Marsaglia (Ann. Math. Statist., 43 (1972), hlm. 645– 646). Untuk dimensi rendah, rasio penolakannya cukup rendah.

Jika Anda ingin menghasilkan titik acak dari bola dan bola dimensi tinggi, maka itu tergantung pada tujuan dan skala simulasi. Jika Anda tidak ingin melakukan simulasi besar, gunakan metode Muller (Commun. ACM, 2 (1959), hlm. 19-20) atau versi "bola" -nya (lihat kertas Harman & Lacko yang dikutip di atas). Itu adalah:

untuk mendapatkan sampel yang terdistribusi secara merata pada n-sphere (permukaan) 1) menghasilkan X dari distribusi normal standar n-dimensi 2) bagi setiap komponen X dengan norma Euclidean X

untuk mendapatkan sampel yang terdistribusi secara merata pada bola-n (interior) 1) menghasilkan X dari (n + 2) -distribusi normal standar berdimensi 2) bagi setiap komponen X dengan norma Euclidean X dan ambil hanya komponen n pertama

Jika Anda ingin melakukan simulasi besar, maka Anda harus menyelidiki metode yang lebih khusus. Atas permintaan, saya dapat mengirimkan kepada Anda makalah Harman dan Lacko tentang metode distribusi bersyarat, yang menyediakan klasifikasi dan generalisasi dari beberapa algoritma yang disebutkan dalam diskusi ini. Kontak tersedia di situs web saya (http://www.iam.fmph.uniba.sk/ospm/Lacko)

Jika Anda ingin memeriksa, apakah poin Anda benar-benar seragam di permukaan atau bagian dalam bola, lihat marginalnya (semua harus sama, karena invarian rotasi, norma kuadrat dari sampel yang diproyeksikan adalah terdistribusi beta).

V Lacko
sumber

apa yang salah dengan sampel dari MultiVariateGaussian dan vektor itu hanya menormalkannya: v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))dan kemudian v = v/v.norm(10000)

Pinocchio

8

Saya memiliki masalah yang sama (n-bola) selama PhD saya dan salah satu 'ahli' lokal menyarankan sampel penolakan dari n-cube! Ini, tentu saja, akan mengambil usia alam semesta ketika saya melihat n dalam urutan hunderds.

Algoritma yang saya gunakan akhirnya sangat sederhana dan diterbitkan dalam:

WP Petersen dan A. Bernasconic Uniform pengambilan sampel dari n-sphere: Metode Teknis isotropik, TR-97-06, Pusat Swiss untuk Komputasi Ilmiah

Saya juga memiliki makalah ini di bibliografi yang belum pernah saya lihat. Anda mungkin menemukan itu berguna.

Harman, R. & Lacko, V. Pada algoritma dekomposisi untuk pengambilan sampel yang seragam dari bola dan bola Journal of Multivariate Analysis, 2010 $n$ $n$

emakalic
sumber

apakah mungkin memposting tautan di mana saya dapat menemukan teks lengkap dari referensi ini? Terima kasih.

Qiang Li

Saya tidak punya makalah tentang saya, tetapi halaman ini tampaknya menggambarkan algoritma (dan beberapa orang lain) mlahanas.de/Math/nsphere.htm

emakalic

3

Seperti yang saya pahami, (dari kertas Petersen dan Bernasconic) untuk bola d-dimensi, seseorang dapat menghasilkan jari-jari dengan menaikkan variasi U (0,1) ke daya (1 / d), dan sudut terakhir sebagai Variasi U (0,2 ). Sudut perantara dapat diperoleh sebagai , di mana adalah . Bagi saya ini kedengarannya agak sederhana. Yang saya ingin tahu adalah ini: jika saya menggunakan urutan acak kuasi untuk seragam saya, akankah saya mendapatkan kebaikan juga di bola?

π

$\pi$

C . a s i n (\sqrt[k]{u})

$C. asin(\sqrt[k]{u})$

C^{- 1}

${C^{-1}}$

\frac{\sqrt{π} Γ (\frac{k}{2} + 0.5)}{Γ (\frac{k}{2} + 1)}

$\frac{\sqrt{\pi} \Gamma(\frac{k}{2} + 0.5)}{\Gamma(\frac{k}{2} + 1)}$

Mohit

3

Saya pernah mengalami masalah ini sebelumnya, dan inilah alternatif yang saya temukan,

Sedangkan untuk distribusinya sendiri, rumus yang saya temukan yang berfungsi dengan baik adalah dengan menggunakan koordinat polar (saya sebenarnya menggunakan variasi koordinat poler yang dikembangkan), kemudian dikonversi ke koordinat Cartesius.

Jari-jari tentu saja adalah jari-jari bola tempat Anda merencanakan. Kemudian Anda memiliki nilai kedua untuk sudut pada bidang datar, diikuti oleh nilai ketiga yaitu sudut di atas atau di bawah bidang itu.

Untuk mendapatkan distribusi yang layak, asumsikan bahwa U adalah bilangan acak yang terdistribusi seragam, r adalah jari-jari, a adalah koordinat polar kedua, dan b adalah koordinat polar ketiga,

a = U * 360 b = U + U-1 kemudian dikonversi ke kartesius melalui x = r * sin (b) dosa (a) z = r dosa (b) cos (a) y = r dosa (b)

Saya baru-baru ini menemukan yang berikut yang secara matematis lebih baik, a = 2 (pi) * Ub = cos ^ -1 (2U-1)

Tidak jauh berbeda dari formula asli saya, meskipun saya adalah derajat vs radian.

Versi terbaru ini konon dapat digunakan untuk hyperspheres, meskipun tidak disebutkan bagaimana mencapainya.

Meskipun saya memeriksa keseragaman secara visual dengan metode yang agak murah untuk membuat peta untuk Homeworld 2 dan kemudian "memainkan" peta itu. Faktanya, karena peta dibuat dengan skrip lua, Anda dapat membuat rumus tepat di peta dan dengan demikian memeriksa beberapa sampel tanpa harus meninggalkan permainan. Mungkin tidak ilmiah, tetapi merupakan metode yang baik untuk melihat hasilnya secara visual.

TheDerpyAlicorn
sumber

2

Inilah kodesemu:

$v \sim MultiVariateGaussian(\mu,\sigma I)$
$v = \frac{v}{ \| v \| }$

Di pytorch:

v = MultivariateNormal(torch.zeros(10000), torch.eye(10000))
v = v/v.norm(2)

Saya tidak mengerti ini cukup baik tetapi saya telah diberitahu oleh whuber bahwa:

v = torch.normal(torch.zeros(10000), torch.eye(10000))
v = v/v.norm(2)

juga benar yaitu pengambilan sampel dari normal univariat untuk setiap koordinat.

Pinokio
sumber

0

Tebakan terbaik saya adalah pertama-tama menghasilkan satu set titik yang terdistribusi secara seragam dalam ruang 2 dimensi dan kemudian memproyeksikan titik-titik tersebut ke permukaan bola menggunakan semacam proyeksi.

Anda mungkin harus mencampur dan mencocokkan cara Anda menghasilkan poin dengan cara Anda memetakannya. Dalam hal generasi titik 2D, saya pikir bahwa urutan perbedaan rendah yang diacak akan menjadi tempat yang baik untuk memulai (yaitu urutan Sobol yang diacak) karena biasanya menghasilkan poin yang tidak "digumpal bersama". Saya tidak yakin tentang jenis pemetaan yang akan digunakan, tetapi Woflram muncul proyeksi Gnonomis ... jadi mungkin itu bisa berhasil?

MATLAB memiliki implementasi yang layak dari urutan perbedaan rendah yang dapat Anda hasilkan menggunakan q = sobolset(2)dan mengacak menggunakan q = scramble(q). Ada juga kotak alat pemetaan di MATLAB dengan banyak fungsi proyeksi berbeda yang dapat Anda gunakan seandainya Anda tidak ingin membuat kode pemetaan dan gambar sendiri.

Berk U.
sumber

1

dapatkah salah satu proyeksi ini tetap mempertahankan keseragaman keacakan? Sekali lagi, bagaimana saya dapat memeriksa apakah distribusi akhir dari titik-titik ini benar-benar terdistribusi secara merata di permukaan bola? Terima kasih.

Qiang Li

Maaf saya baru saja berbicara secara hipotetis ... Saya pikir fungsi pemetaan pada MATLAB akan memungkinkan Anda untuk memeriksa karena mereka memiliki beberapa visualisasi yang tertanam di dalamnya. Jika tidak, saya juga menemukan situs web yang bagus yang membahas tentang cara menghasilkan titik-titik yang terdistribusi secara merata pada bidang 3D menggunakan hal-hal seperti sudut acak dll. Mereka juga memiliki beberapa kode C di sana. Lihatlah

Berk U.

3

Titik acak seragam pada proyeksi gnomonik tidak akan seragam pada bola, karena gnomonik bukan area yang sama. Proyeksi yang dikemukakan oleh Henry, -> (dari lintang-bujur ke persegi panjang di ), adalah luas yang sama.

(λ, ϕ)

$(\lambda, \phi)$

(λ, \sin (ϕ))

$(\lambda, \sin(\phi))$

R^{2}

$\mathbb{R}^2$

whuber

Bagaimana cara menghasilkan titik yang terdistribusi secara merata pada permukaan unit sphere 3-d?

Jawaban: