Sebagian besar metode kuasi-acak dua dimensi dirancang untuk pengambilan sampel satuan persegi. Namun, segitiga juga sangat penting dalam grafik komputer. Oleh karena itu, saya menggambarkan metode konstruksi langsung sederhana untuk secara seragam mencakup urutan titik-titik segitiga dengan bentuk yang sewenang-wenang.

Gambar 1. Metode langsung baru untuk membangun urutan kuasi-acak terbuka (tak terbatas) dengan divergensi rendah dalam segitiga bentuk dan ukuran sewenang-wenang. Angka tersebut menunjukkan distribusi poin dalam lima belas segitiga acak untuk 150 poin pertama.

Ulasan singkat

Urutan perbedaan rendah yang secara seragam sampel / mengisi kotak telah aktif dipelajari selama hampir seratus tahun. Sebagian besar sekuens acak semu ini dapat diperluas menjadi persegi panjang dengan peregangan sederhana, tanpa secara signifikan merusak perbedaan.

Namun, dalam posting ini kami akan mempertimbangkan perpanjangan urutan yang menarik dan penting dengan divergensi rendah menjadi segitiga sembarang.

Sejauh yang saya bisa mengerti, sangat sedikit perhatian diberikan pada pembangunan set poin dan urutan yang terdistribusi secara seragam dalam sebuah segitiga. Karya-karya penting tahun-tahun terakhir oleh Basu [2014] , Pillands [2005] dan Brandolini [2013] mewakili artikel utama, jika bukan satu-satunya tentang topik ini.

Para penulis ini biasanya mempertimbangkan masalah ini dari sudut pandang yang sangat teoretis dan analitis, dan hampir selalu menyelesaikannya untuk satu segitiga biasa. Berbeda dengan mereka, posting saya terutama ditujukan untuk pengembangan teknik praktis dalam rendering grafik.

Pos menjelaskan metode sederhana konstruksi langsung, yang tidak memerlukan penerimaan / pengecualian, atau membuang atau rekursi; dan yang paling penting, ini dapat diterapkan pada segitiga dengan ukuran dan bentuk yang berubah-ubah.

Pos terdiri dari empat bagian:

Urutan acak kuadrat
Overlay satuan persegi pada segitiga.
Pengurangan distorsi
Generalisasi lebih lanjut

1. Urutan titik kuasi-acak

Anda mungkin berpikir bahwa menempatkan 100 titik dalam kotak sehingga jarak minimum antara titik-titik yang berdekatan tetap sebesar mungkin. Tetapi bagaimana jika Anda perlu menempatkan 13 poin? 47? Bagaimana dengan 2019 poin ?!

Ternyata urutan titik dengan divergensi rendah memberikan cara sistematis untuk menyelesaikan masalah ini. Ada banyak urutan kuasi-acak dengan divergensi rendah, dari urutan Holton sederhana ke urutan Sable yang lebih kompleks. Masing-masing dari sekuens ini memiliki kelebihan dan kekurangannya sendiri. Misalnya, sekuens Holton ternyata lebih berguna ketika menempatkan objek di suatu area, karena memiliki metrik jarak lokal yang dioptimalkan dengan baik seperti tetangga terdekat. Urutan Sable rentan untuk membentuk lebih "ramai", tetapi distribusi global titik sangat merata, sehingga memiliki sifat quadrature yang sangat baik.

Ada urutan lain yang ingin saya gunakan, dengan properti lokal dan global yang sangat baik. Ini urutannya

R_{2}

$R_2$ dijelaskan secara rinci dalam posting saya sebelumnya "Efisiensi tak terduga dari urutan kuasi-acak" .

Singkatnya, kita mendefinisikan urutan dua dimensi yang tak terbatas

R_{2}

$R_2$ sedemikian rupa

\ pmb {t} _n = \ kiri \ {n \ pmb {\ alpha} \ kanan \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ kiri \ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3, ...

$\ pmb {t} _n = \ kiri \ {n \ pmb {\ alpha} \ kanan \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ kiri \ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3, ...$

t e x t r m w h e r e q u a d p m b a l p h a = k i r i (f r a c 1 g, f r a c 1 g^{2} k a n a n),

$\ textrm {where} \ quad \ pmb {\ alpha} = \ kiri (\ frac {1} {g}, \ frac {1} {g ^ 2} \ kanan),$

t e x t r m a n d g s i m e q 1.32471795572 t a g 1

$\ textrm {and} \; g \ simeq 1.32471795572 \ tag {1}$

Baca lebih lanjut tentang makna khusus ini.

g

$g$ , yang sering disebut "konstanta plastik", dapat dibaca di Wikipedia atau Mathworld .

Sebagai hasilnya, Gambar 2 menunjukkan perbandingan urutan yang berbeda dengan divergensi rendah (dan sampel acak seragam sederhana untuk perbandingan). Seperti yang Anda lihat, sampel acak ini menunjukkan akumulasi poin. Selain itu, ini berisi area yang tidak mengandung titik sama sekali ("white noise"), sedangkan urutan kuasi-acak dengan divergensi rendah adalah metode membangun urutan titik (tak terbatas) dalam cara deterministik sehingga pada setiap tahap titik-titik yang ditempatkan didistribusikan secara merata di seluruh ruang.

Gambar 2. Ilustrasi 150 anggota pertama dari berbagai urutan kuasi-acak divergensi rendah. Perhatikan bahwa mereka semua membuat titik yang terdistribusi lebih merata di ruang daripada distribusi acak seragam yang sederhana (kiri bawah).

2. Pengenaan satuan persegi pada segitiga

Ada tiga metode terkenal untuk memastikan pengambilan sampel acak yang seragam dari segitiga:

metode jajaran genjang
Metode Kramer dan
metode distribusi probabilitas terbalik.

Gambar 3. Metode Parallelogram

Metode jajaran genjang adalah sebagai berikut.

Untuk segitiga

p m b A B C

$\ pmb {ABC}$ pertimbangkan jajar genjang

\ pmb {ABCA}}

$\ pmb {ABCA}}$ .

Untuk titik satuan persegi

(r_{1}, r_{2})

$(r_1, r_2)$ atur poin seperti itu

p m b P

$\ pmb {P}$ itu

p m b P = r_{1} p m b A C + r_{2} p m b A B

$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ .

Titik ini akan selalu berada di dalam jajaran genjang. Namun, jika muncul dalam segitiga tambahan

p m b A B C

$\ pmb {ABC}$ maka kita perlu membaliknya kembali ke segitiga

p m b A B C

$\ pmb {ABC}$ .

Itu kalau

r_{1} + r_{2} < 1

$r_1 + r_2 <1$ lalu

p m b P = r_{1} p m b A C + r_{2} p m b A B

$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ tetapi jika

r_{1} + r_{2} > 1

$r_1 + r_2> 1$ lalu

p m b P = (1 - r_{1}) p m b A C + (1 - r_{2}) p m b A B

$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$ .

Namun, sangat penting untuk memahami bahwa meskipun metode ini memberikan pengambilan sampel yang seragam dari sebuah segitiga, ini tidak berarti bahwa transformasi semacam itu akan mempertahankan pengaturan spasial yang seragam (yaitu, divergensi rendah) dari distribusi titik kuasi-acak kami.

Sebagai contoh, dalam kasus metode jajar genjang, refleksi seringkali dapat menghasilkan titik yang sangat dekat dengan titik lain yang ada. Jelas, ini menghancurkan struktur divergensi rendah dan muncul sebagai distorsi / strip.

Demikian pula, metode distribusi probabilitas terbalik menerapkan distorsi nonlinear ke poin. Dalam urutan Holton dan Sable, ini berarti bahwa dua poin sangat sering mendorong diri mereka sangat berdekatan.

Gambar 4 menunjukkan seberapa baik perbedaan rendah dipertahankan di masing-masing berbagai urutan kuasi-acak ketika mengubah suatu daerah dari satuan persegi ke segitiga menggunakan metode jajar genjang.

Gambar 4. Perbandingan transformasi berbagai urutan kuasi-acak dalam segitiga. Di atas adalah urutan Holton, di tengah adalah urutan Sable, di bawah ini adalah urutan

$R_2$ . Dapat dilihat bahwa crowding yang signifikan dari titik-titik terjadi dalam urutan Holton, dan pembentukan pita yang signifikan dalam urutan Sobol. Dibandingkan dengan mereka, secara berurutan

$R_2$ titik-titiknya didistribusikan dengan sangat merata, dan hampir tidak ada keramaian atau garis yang mencolok.

Dari tiga metode triangulasi yang berbeda dan banyak urutan kuasi-acak yang berbeda, metode jajaran genjang diterapkan pada metode urutan

$R_2$ adalah satu-satunya kombinasi yang secara konstan menciptakan hasil yang dapat diterima dalam hal mempertahankan varian rendah tanpa distorsi.

Hasil yang sangat baik dari kombinasi ini dapat diperiksa secara lebih rinci pada Gambar 5.

Gambar 5. Anda dapat melihat urutan yang dikonversi

$R_2$ menyediakan cara yang sangat sederhana namun efektif untuk mendistribusikan banyak

$N$ poin dalam segitiga. Ini bekerja dengan segitiga siku-siku dan tumpul. (Warna menunjukkan pengaturan).

3. Aspek lainnya

Distorsi

Metode jajar genjang membutuhkan pilihan dua sisi segitiga sebagai vektor basis.

Jika simpul ditandai dalam urutan acak, maka pola titik biasanya menyerupai yang ditunjukkan pada Gambar 6.

Gambar 6. Pola poin yang diperoleh dengan secara acak memilih urutan simpul. Perhatikan bahwa dalam kebanyakan kasus, distorsi jelas terlihat.

Namun, ternyata dengan pilihan urutan simpul yang hati-hati, distorsi dapat dikurangi secara signifikan. Terutama, jika Anda memberi label segitiga

A

$A$ adalah sudut terbesar (mis., sisi terbesar menentangnya), lalu sisi

p m b A B

$\ pmb {AB}$ dan

p m b A C

$\ pmb {AC}$ digunakan sebagai dua sisi jajaran genjang.

Jika kita mengambil urutan ini, maka kita mendapatkan pola titik-titik yang ditunjukkan di atas pada Gambar 1, 4 dan 5.

Namun, bahkan dengan urutan simpul tertentu, dalam beberapa kasus, efek distorsi masih terlihat. Mereka paling terlihat ketika salah satu sudut dalam segitiga sangat kecil. Dalam kasus segitiga tumpul, ketika sudut terkecil kurang dari 30 derajat, beberapa distorsi terlihat, dan dalam kasus segitiga siku akut, ketika sudut terkecil kurang dari 20 derajat, distorsi menjadi terlihat. (Jika segitiga sampel adalah bagian dari jaring Delaunay, maka masalah distorsi seperti itu bisa minimal, karena triangulasi Delaunay dirancang khusus untuk meminimalkan jumlah segitiga dengan sudut kecil.)

Bentuk lainnya

Sayangnya, teknik jajar genjang tidak dapat digunakan untuk bentuk lain, karena menggunakan simetri segitiga. Untuk beberapa angka, hasil yang baik dapat diperoleh dengan menggunakan metode distribusi probabilitas terbalik. Berikut ini adalah contoh bagaimana urutannya

R_{2} R_{2}

$R_2R_2$ dengan divergensi rendah, Anda dapat mengkonversi ke wilayah yang dibatasi oleh kurva Gaussian sambil mempertahankan jarak yang seragam antara titik-titik.

Distribusi titik yang seragam dalam suatu segitiga