Distribusi titik-titik pada bola yang paling seragam adalah tugas yang sangat penting dalam matematika, sains, dan sistem komputer, dan menerapkan kisi Fibonacci ke permukaan bola menggunakan proyeksi yang sama adalah metode perkiraan yang sangat cepat dan efisien untuk menyelesaikannya. Saya akan menunjukkan bagaimana, dengan perubahan kecil, itu bisa dibuat lebih baik.

Beberapa waktu yang lalu posting ini muncul di beranda Hacker News. Pembahasannya bisa dibaca di sini .

Pendahuluan

Masalah distribusi titik-titik yang seragam pada suatu bola memiliki sejarah yang sangat panjang. Ini adalah salah satu masalah yang paling banyak dipelajari dalam literatur matematika tentang geometri bola. Ini sangat penting dalam banyak bidang matematika, fisika, kimia, termasuk metode komputasi, teori aproksimasi, teori pengkodean, kristalografi, elektrostatik, grafik komputer, morfologi virus dan banyak lainnya.

Sayangnya, dengan pengecualian beberapa kasus khusus (yaitu, padatan Platonis), tidak mungkin untuk mendistribusikan poin pada bola dengan sempurna. Selain itu, solusi masalah sangat tergantung pada kriteria yang digunakan untuk menilai keseragaman. Dalam praktiknya, banyak kriteria digunakan, termasuk:

Pengemasan dan pelapisan
Hull cembung, sel Voronoi, dan segitiga Delaunay
Kernel $s$ Energi Beras
Cubature dan kualifikasi

Sangat penting untuk memperjelas aspek ini: biasanya tidak ada solusi optimal tunggal untuk masalah ini, karena solusi optimal berdasarkan satu kriteria seringkali bukan distribusi poin yang optimal untuk orang lain. Misalnya, kami juga akan menemukan bahwa pengoptimalan pengemasan tidak harus menciptakan cembung cembung yang optimal dan sebaliknya.

Demi singkatnya, dalam posting ini kami hanya akan mempertimbangkan dua kriteria: jarak pengepakan minimum dan cembung cembung / jaring Delaunay (volume dan area).

Di bagian 1, kami menunjukkan bagaimana Anda dapat mengubah kisi Fibonacci kanonik untuk membangun distribusi pengemasan yang ditingkatkan. Pada Bagian 2, kami menunjukkan bagaimana Anda dapat mengubah kisi Fibonacci kanonik untuk membangun parameter yang lebih baik untuk cembung cembung (volume dan luas permukaan).

Bagian 1. Optimalisasi jarak pengemasan

Seringkali masalah ini disebut tugas Tamm untuk menghormati ahli botani Tems, yang mencari penjelasan tentang struktur permukaan butir serbuk sari. Kriteria pengepakan mengharuskan kami untuk memaksimalkan jarak terkecil antar tetangga

$N$ poin. Yaitu

$d_N = \ min_ {i \ neq j} | x_i - x_j |$

Nilai ini berkurang dengan kecepatan.

$~ 1 / \ sqrt {N}$ Oleh karena itu, akan berguna untuk menentukan jarak dinormalisasi, serta batas asimptotik dari jarak dinormalisasi, seperti

$d ^ * _ N = \ sqrt {N} d_N, \ quad \ quad d ^ * = \ lim_ {N \ rightarrow \ infty} d ^ * _ N$

Grid Fibonacci

Salah satu solusi yang sangat elegan adalah memodelkan simpul yang ditemukan di alam, misalnya, distribusi biji dalam bunga matahari atau kerucut pinus. Fenomena ini disebut spiral phyllotaxis . Coxeter menunjukkan bahwa struktur seperti itu memiliki koneksi mendasar dengan seri Fibonacci,

F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}

$F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}$ dan rasio emas

$\ phi = (1+ \ sqrt {5}) / 2$ .

Dalam literatur, dua definisi yang sama dari himpunan poin dari grid Fibonacci bulat ditemukan. Sumber didefinisikan secara ketat untuk

$N$ sama dengan salah satu anggota seri Fibonacci,

$F_m$ , dan dipelajari dengan baik dalam teori bilangan.

$t_i = \ kiri (\ frac {i} {F_m}, \ frac {i F_ {m-1}} {F_m} \ kanan) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1$

Definisi kedua menggeneralisasikan formula ke jumlah yang sewenang-wenang

$N$ dan lebih sering digunakan dalam perhitungan:

$t_i = \ kiri (\ frac {i} {N}, \ frac {i} {\ phi} \ kanan) \ quad \ textrm {for} \; 0 \ leq i \ leq N \ tag {1}$

dimana

$\ phi = \ frac {1+ \ sqrt {5}} {2} = \ lim_ {n \ rightarrow \ infty} \ kiri (\ frac {F_ {n + 1}} {F_n} \ kanan)$

Di bawah ini adalah contoh dari grid Fibonacci yang sama. Dengan transformasi, Anda dapat mengubah set poin ini menjadi Fibonacci spiral yang terkenal bagi kami.

$(r, \ theta) = (\ sqrt {x_1}, 2 \ pi x_2)$

Demikian pula, set poin ini dapat ditransfer dari unit square

$[0, 1] ^ 2$ pada bola menggunakan proyeksi isometrik silinder:

$(x, y) \ rightarrow (\ theta, \ phi): \ quad \ left (\ cos ^ {- 1} (2x-1) - \ pi / 2, 2 \ pi y \ right)$

$(\ theta, \ phi) \ rightarrow (x, y, z): \ quad \ left (\ cos \ theta \ cos \ phi, \ cos \ theta \ sin \ phi, \ sin \ theta \ right)$

Banyak versi berbeda dari kode Python untuk itu dapat ditemukan di stackoverflow: Merata poin secara merata .

Bahkan terlepas dari kenyataan bahwa set Fibonacci bulat secara global bukan distribusi sampel terbaik pada suatu bola (karena solusi mereka tidak bertepatan dengan solusi untuk padatan Platonik untuk

$n = $ 4,6,8,12,2$ ), mereka memiliki sifat pengambilan sampel yang sangat baik dan sangat mudah dibangun dibandingkan dengan skema pengambilan sampel berbentuk bola yang lebih kompleks.

Karena pemindahan dari unit square ke permukaan bola dilakukan oleh proyeksi dengan pengawetan area, dapat diharapkan bahwa jika titik awal terdistribusi secara merata, mereka juga akan terdistribusi dengan cukup baik di permukaan bola. Namun, ini tidak berarti bahwa distribusi akan terbukti optimal.

Transfer ini menderita dua masalah yang berbeda tetapi saling terkait.

Pertama, overlay ini dilakukan dengan tetap menjaga area, bukan jarak. Mengingat bahwa dalam kasus kami, ketentuannya adalah untuk memaksimalkan jarak berpasangan minimum antara titik, kondisi dan hubungan tersebut tidak harus terpenuhi setelah proyeksi.

Masalah kedua adalah yang paling sulit dipecahkan dari sudut pandang praktis: superposisi memiliki dua titik degenerasi di setiap kutub. Pertimbangkan dua titik yang sangat dekat dengan kutub, tetapi garis bujurnya berbeda 180 derajat. Pada satu bujur sangkar (dan pada proyeksi silindris) mereka akan bersesuaian dengan dua titik yang sangat jauh satu sama lain, namun ketika ditumpangkan pada permukaan bola, mereka dapat dihubungkan oleh busur yang sangat kecil melewati kutub utara. Karena masalah khusus ini, banyak overlay spiral tidak cukup optimal.

Fibonacci Spherical Helix yang diperoleh dari Persamaan 1 memberikan nilai

$d_N ^ *$ untuk semua

$N$ itu adalah

$d ^ * = 2$ .

Mesh 1

Versi yang lebih umum (terutama pada sistem komputer) yang menciptakan nilai yang lebih baik

$d ^ * = 3.09$ memiliki bentuk:

$t_i = \ kiri (\ frac {i + 1/2} {N}, \ frac {i} {\ phi} \ kanan) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {2}$

Ini mengatur titik pada interval titik tengah (sesuai dengan aturan titik tengah dalam rumus kuadrat Gaussian), oleh karena itu, untuk

$n = 100$ , nilai-nilai koordinat pertama adalah sebagai berikut:

$\ {\ frac {0.5} {100}, \ frac {1.5} {100}, \ frac {2.5} {100}, \ ldots, \ frac {97.5} {100}, \ frac {98.5} {100} , \ frac {99.5} {100} \}$

Kisi 2.

Kunci untuk lebih lanjut meningkatkan Persamaan 2 adalah realisasi itu

$d ^ * _ N$ selalu sesuai dengan jarak antar titik

$t_0$ dan

$t_3$ yang ada di kutub. Yaitu, untuk meningkatkan

$d_N$ titik dekat kutub harus ditempatkan lebih jauh.

Jika kita mendefinisikan distribusi berikut:

$t_i (\ varepsilon) = \ kiri (\ frac {i + 1/2 + \ varepsilon} {N + 2 \ varepsilon}, \ frac {i} {\ phi} \ kanan) \ quad \ textrm {for} \ ; 0 \ leq i \ leq N-1$

$d ^ * _ N$ - kurva untuk berbagai nilai.

$\ varepsilon = 0$ (biru);

$\ varepsilon = \ frac {1} {2}$ (oranye);

$\ varepsilon = \ frac {3} {2}$ (hijau); dan

$\ varepsilon = \ frac {5} {2}$ (merah). Anda bisa melihatnya

$\ varepsilon = \ frac {5} {2}$ memberikan hasil yang lebih dekat dengan hasil asimptotik. Yaitu dengan

$N> 20$ Ungkapan sederhana berikut menghasilkan hasil yang jauh lebih baik.

$d ^ * = 3,29$ dibandingkan dengan kisi Fibonacci bulat kanonik:

$t_i = \ kiri (\ frac {i + 3} {N + 5}, \ frac {i} {\ phi} \ kanan) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {3}$

Yaitu dengan

$N = 100$ nilai koordinat pertama akan sama dengan:

$\ {\ frac {3} {105}, \ frac {4} {105}, \ frac {5} {105}, \ ldots, \ frac {100} {105}, \ frac {101} {105} , \ frac {102} {105} \}$

Gambar 1. Nilai berbeda

$d_N ^ *$ pada nilai yang berbeda

$\ epsilon$ . Semakin tinggi nilainya, semakin optimal konfigurasi. Kami melihat itu

$\ epsilon \ simeq 2.5$ memberikan solusi yang mendekati optimal.

Mesh 3.

Seperti disebutkan di atas, salah satu masalah paling serius dari distribusi titik yang seragam pada suatu bola adalah bahwa optimalitas distribusi sangat tergantung pada fungsi objektif yang digunakan. Ternyata. seperti jumlah lokal

$d_N ^ *$ kadang-kadang mereka hampir “tidak memaafkan kesalahan” - satu titik dalam posisi yang tidak optimal secara serempak dapat mengurangi penilaian seluruh distribusi titik.

Dalam kasus kami, terlepas dari besarnya

$N$ nilai

$D_N ^ *$ biasanya ditentukan oleh empat titik yang paling dekat dengan masing-masing kutub, terutama

$t_0$ dan

$t_3$ . Namun, juga diketahui tentang kisi ini bahwa poligon Voronoi terbesar ada di kutub. Jadi berusaha memaksimalkan

$d_N$ dengan membagi titik kutub asli berturut-turut, kami benar-benar meningkatkan kekosongan di kutub bahkan lebih! Oleh karena itu, kami menyajikan alternatif untuk kisi 2, yang umumnya lebih disukai karena tidak menunjukkan kekosongan besar di dekat kutub.

Hampir identik dengan kisi 2, tetapi memiliki dua perbedaan. Pertama, dia menggunakan

$\ varepsilon = 11/2$ di

$1 \ leq i \ leq N-2$ . Kedua, selain ini

$N-2$ Poin pertama dan terakhir terletak di masing-masing kutub.

Itu adalah:

$t_0 = (0,0); \; t_n = (1,0); \ quad t_i = \ kiri (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ kanan) \ quad \ textrm {for} \; 1 \ leq i \ leq N-2 \ tag {4}$

Properti yang luar biasa dari metode konstruksi ini adalah bahwa terlepas dari kenyataan bahwa pembuatannya dimotivasi oleh keinginan untuk meminimalkan kekosongan di kutub, sebenarnya memiliki nilai terbaik di antara semua metode

$d_N$ dan

$d ^ *$ dengan

$d ^ * = 3,31$ !

Yaitu dengan

$N = 100$ nilai koordinat pertama adalah sebagai berikut:

$\ {0; \; \ frac {7} {111}, \ frac {8} {111}, \ frac {9} {1111}, \ ldots, \ frac {102} {111}, \ frac {103} {111}, \ frac {104} {111}; \; 1 \}$

Gambar 2. Berbagai konfigurasi kisi. Kisi Fibonacci kanonik di sebelah kiri. Perhatikan bahwa meskipun tengah grid

$d_N ^ *$ meningkat, di kutub dia memiliki kekosongan yang nyata. Kotak 3 tidak memiliki kekosongan di kutub dan memiliki nilai terbaik

$d_N ^ *$ .

Perbandingan

Untuk nilai besar

$N$ nilai ini

$d ^ *$ sangat baik dibandingkan dengan metode lain, misalnya, kubah geodesik, yang didasarkan pada proyeksi triangulasi dari permukaan padatan Platonis ke permukaan bola. Tidak mengherankan bahwa kubah geodesik berkualitas tinggi dibangun berdasarkan icosahedron atau dodecahedron.

Kubah geodesik berbasis Icosahedron pada berbagai nilai

$N$ .

$\ begin {arr} & 3.15 & 3.09 & 3.06 & 3.03 & 3.00 & 2.99 \\ \ hline \ end {array}$

Kubah geodesik berbasis Dodecahedron untuk berbagai nilai

$N$ .

$\ begin {arr} 2.81 \\ \ hline \ end {array}$

Selain itu, icosahedron terpotong sesuai dengan bentuk fullerene

$C_ {60}$ hanya memiliki

$d ^ * = 3,125$ .

Yaitu dengan

$N> 100$ mesh berdasarkan persamaan 3 lebih baik daripada polyhedron geodesik.

Menurut data dari sumber pertama dalam daftar referensi di bawah ini, beberapa metode modern, yang biasanya kompleks dan membutuhkan pemrograman rekursif dan / atau dinamis, memiliki indikator berikut.

$\ begin {array} {| lr |} \ hline \ text {Lattice 1} & 3.09 \\ \ hline \ text {Max Determinant} & 3.19 \\ \ hline \ text {Lattice 2} & 3.28 \\ \ hline \ text {Lattice 3} & 3.31 \\ \ hline \ text {Zonal Equal Area} & 3.32 \\ \ hline \ text {Coulomb} & 3.37 \\ \ hline \ text {Log Energy} & 3.37 \\ \ hline \ end { array}$

Kesimpulan dari Bagian 1

Grid 3, dibuat oleh Equation 3, adalah modifikasi dari grid Fibonacci kanonik, yang menyediakan kemasan yang jauh lebih baik untuk distribusi poin. Yaitu

$t_0 = (0,0); \; \; t_i = \ kiri (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ kanan); \; \; t_ {N-1} = (0,1); \ quad \ textrm {for} \; 1 \ leq i \ leq N-2$

Bagian 2. Optimalisasi convex hull (Delaunay mesh)

Di bagian sebelumnya, kami mengoptimalkan distribusi dengan

$d ^ * _ N$ Namun, modifikasi ini memperburuk indikator lain, misalnya, volume lambung cembung (Delaunay mesh). Bagian ini menjelaskan cara mendistribusikan titik pada bola secara merata sedemikian rupa untuk mengoptimalkan (memaksimalkan) indikator yang lebih global seperti volume lambung cembung.

Kami menunjukkan

$C_N$ seperti lambung cembung

$N$ poin

$\ epsilon_N = N \ kiri (\ frac {4 \ pi} {3} \; - \ textrm {Vol} (C_N) \ kanan)$

termasuk faktor normalisasi

$N$ , karena perbedaan absolut berkurang dengan kecepatan

$~ 1 / N$ .

Perilaku

$\ epsilon_N$ di berbagai

$N$ dapat dilihat pada Gambar 3 (garis biru).

Untuk mengurangi ketidakcocokan volume, perlu dicatat bahwa meskipun penggunaan

$\ phi$ , dari logika bagian emas di

$N \ rightarrow \ infty$ itu tidak selalu berarti bahwa itu adalah nilai terbaik untuk final

$N$ . Berbicara secara ilmiah, kita dapat mengatakan bahwa kita perlu memperhitungkan pengaruh anggota koreksi ekstremitas.

Mari kita simpulkan persamaan 1 sebagai berikut:

$t_i = \ kiri (\ frac {i + 1/2} {N}, \ frac {i} {g (N)} \ kanan) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {4}$

di mana kita mendefinisikan

$g (n)$ bagaimana

$g (n) = \ begin {cases} 3- \ phi, & \ text {jika $ k $ genap} \\ \ phi, & \ text {jika $ k $ ganjil} \ end {cases} \ tag {5}$

dimana

$k = \ kiri \ lfloor \ textrm {log} _ {\ phi} (\ frac {n} {1.5}) \ right \ rfloor = \ kiri \ lfloor \ frac {\ ln (n / 1.5)} {\ ln \ phi} \ right \ rfloor$

dimana

$\ lfloor x \ rfloor$ - fungsi pembulatan ke bilangan bulat terdekat ke bawah.

Gambar 3 menunjukkan berapa banyak ketidakcocokan volume dioptimalkan untuk setengah dari nilai.

$N$ .

Alasan untuk ini adalah fakta yang sedikit diketahui: semua angka

$x$ memuaskan transformasi Mobius khusus, mulai dari irasionalitas, adalah setara

$\ phi$ .

$x = \ frac {a \ phi + b} {c \ phi + d}, \ quad \ textrm {untuk semua bilangan bulat} \; \; a, b, c, d \; \ textrm {sedemikian rupa} | ad-bc | = 1$

Karena itu, alasan itu

$\ phi$ dan

$3- \ phi$ cocok bersama dengan baik, apakah itu

$\ frac {1} {\ phi} = \ frac {\ phi + 1} {2 \ phi + 1}, \ quad \ quad \ frac {1} {3- \ phi} = \ frac {2 \ phi + 1} {1 \ phi + 1}$

Gambar 3. Ketidakcocokan antara volume lambung cembung poin dan volume bola unit. Perlu diingat bahwa semakin kecil, semakin baik. Angka tersebut menunjukkan bahwa model hybrid (garis oranye) berdasarkan

$\ phi$ dan

$3- \ phi$ , memberikan distribusi poin yang lebih baik daripada grid Fibonacci kanonik (garis biru).

Untuk separuh sisanya, pertama-tama kita mendefinisikan seri bantu

$A_N$ menjadi variasi dari seri Fibonacci

$A_1 = 1, \; A_2 = 4; \; A_ {n + 2} = A_ {n + 1} + A_n \; \ textrm {for} n = 1,2,3, ...$

Yaitu

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411, ...$

Semua fraksi dari seri ini memiliki fraksi kontinu yang elegan, dan dalam batas menyatu

$\ phi$ . Sebagai contoh

$t _5 / t_4 = 1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {4}}}}$

Sekarang kita dapat menggeneralisasi sepenuhnya

$g (n)$ sebagai berikut:

$g (N) = \ begin {cases} 3- \ phi, & \ text {jika $ k $ genap} \\ A_ {j + 1} / A_j, & \ text {jika $ k $ aneh, di mana $ j = (k + 7) / 2 $} \ end {cases} \ tag {6}$

Tabel di bawah ini menunjukkan nilainya

$g (N)$ untuk berbagai

$N$ .

$\ begin {array} {| c | c | c | c | c | c | c | c |} \ hline N & 4-6 & 7-10 & 11-16 & 17-26 & 27-43 & 44- 70 & 71-114 & 115-184 & 185-300 \\ \ hline g (n) & 3- \ phi & \ frac {23} {14} & 3- \ phi & \ frac {37} {23} & 3- \ phi & \ frac {60} {37} & 3- \ phi & \ frac {97} {60} & 3- \ phi \\ \ hline \ end {array}$

Gambar 4 menunjukkan bahwa sehubungan dengan volume convex hull, distribusi baru ini lebih baik daripada kisi kanonik untuk semua nilai

$n$

Gambar 4. Ketidakcocokan antara volume lambung cembung dan volume bola unit. Semakin rendah nilainya, semakin baik. Ini memberitahu kita bahwa metode baru yang diusulkan (garis hijau) terus-menerus menyediakan distribusi yang lebih baik daripada kiblat Fibonacci kanonik (garis biru).

Gambar 5. Perbandingan visual dari jaring kanonik (kiri) dengan jaring yang dimodifikasi baru (kanan) dengan n = 35 dan n = 150. Secara visual, perbedaannya hampir tak terlihat. Namun, dalam kondisi yang membutuhkan efisiensi maksimum, versi yang dimodifikasi (di sebelah kanan) memberikan peningkatan kecil, tetapi dapat diukur dalam volume dan luas permukaan lambung cembung.

Anehnya, distribusi ini juga tidak signifikan, tetapi terus mengurangi ketidakcocokan antara luas permukaan lambung cembung dan luas permukaan bola tunggal. Ini ditunjukkan pada Gambar 6.

Gambar 5. Ketidakcocokan dinormalisasi daerah antara luas permukaan cembung cembung (Delaunay mesh) dan luas permukaan bola tunggal. Semakin rendah nilainya, semakin baik. Ini menunjukkan bahwa modifikasi baru yang diusulkan (titik hijau) menunjukkan penurunan kecil tetapi konstan dalam perbedaan luas permukaan dibandingkan dengan grid Fibonacci kanonik (titik biru)

Kesimpulan dari Bagian 2

Kisi yang sesuai dengan Persamaan 6 adalah modifikasi kisi Fibonacci kanonik, menciptakan distribusi poin yang jauh lebih baik berdasarkan volume dan luas permukaan cembung cembung (kisi Delaunay).

Sumber

Distribusi titik-titik pada bola yang seragam

Pendahuluan

Bagian 1. Optimalisasi jarak pengemasan

Bagian 2. Optimalisasi convex hull (Delaunay mesh)

More articles: