Pengambilan sampel acak dalam poligon

9

Saya ingin mencicipi titik acak seragam dalam poligon ...

Jika sampel dalam jumlah besar, mereka kemungkinan besar akan jatuh ke dalam dua wilayah jika mereka memiliki wilayah yang sama.

Ini akan sangat sederhana jika itu adalah kuadrat karena saya akan mengambil dua angka acak dalam [0,1] sebagai koordinat saya.

Bentuk yang saya miliki adalah poligon biasa, tetapi saya ingin poligon berfungsi untuk poligon apa pun.

/programming/3058150/how-to-find-a-random-point-in-a-quadrangle

algorithms randomness sampling random-number-generator John Mangual
sumber

Jawaban:

9
  1. Triangulasi poligon
  2. Tentukan di mana dari segitiga titik harus terletak (bobot daerah segitiga)
  3. Contoh titik dalam segitiga seperti yang dijelaskan dalam posting ini
A.Schulz
sumber
Apakah pertanyaan ini bukan duplikat dari yang lama Anda tautkan?
Raphael
@ Raphael: Terkait, tetapi lebih umum, saya akan mengatakan.
A.Schulz
4

Salah satu cara yang mudah adalah untuk menemukan kotak berlari polygon dan penggunaan penolakan sampling Anda: sampel dari kotak berlari dan menerima jika jatuh dalam poligon, yang akan terjadi dengan probabilitas setidaknya (saya pikir).1/2

Kemungkinan lain adalah melakukan triangulasi poligon Anda. Sampel pertama segitiga secara proporsional, lalu sampel titik acak dalam segitiga. Yang terakhir adalah sederhana: hingga transformasi affine, semua segitiga adalah dari bentuk . Untuk sampel seragam poin dari distribusi itu, sampel pertama x ∈ [ 0 , 1 ] menurut kepadatan 2 ( 1 - x ) (yaitu sampel seragam r{(x,y):x,y≥0,x+y≤1}x∈[0,1]2(1-x) dan hitung x = 1 - √r∈[0,1] ) dan kemudian sampely∈[0,1-x]secara seragam (yaitu sampel a seragams∈[0,1]dan hitungy=(1-x)s). Metode yang lebih sederhana adalah dengan mengambil sampelx,y∈[0,1], dan jikax+y>1ganti(x,y)x=1-1-ry∈[0,1-x]s∈[0,1]y=(1−x)sx,y∈[0,1]x+y>1(x,y)dengan .(1−x,1−y)

Yuval Filmus
sumber
Sampel penolakan akan ditolak dengan probabilitas paling banyak 1/2 dalam 2 dimensi, tetapi dalam dimensi yang lebih tinggi kemungkinan penolakan mungkin jauh lebih buruk.
DW
Sampel penolakan mungkin memiliki tingkat penolakan yang lebih besar dari 1/2. Bayangkan saja sebuah spiral, sedikit diekstrusi.
A.Schulz
Bagaimana jika poligon dijamin cembung?
Yuval Filmus
Jika kotak pembatas Anda sejajar sumbu, maka konveksitas tidak membantu; seperti yang disarankan oleh pertanyaan sebelumnya, anggap saja segitiga dengan simpul pada (0, 1), (1, 0) dan (x, x) untuk x yang sangat besar - ini akan mengambil proporsi kecil yang semakin kecil dari kotak pembatasnya sebagai x pergi hingga tak terbatas. Jika Anda berbicara tentang kotak pembatas sekecil mungkin maka Anda mungkin dapat memperoleh batas pada volume bentuk cembung Anda, tetapi kemudian Anda harus menemukan kotak ...
Steven Stadnicki
4

Ini sedikit gila, tetapi harus bekerja dengan baik walaupun poligon Anda sangat aneh.

Gunakan Reimann pemetaan teorema untuk menemukan peta konformal dari unit disk untuk poligon Anda, melihatnya sebagai bagian dari . Lihat, misalnya referensi di:C

http://siam.org/pdf/news/1297.pdf

Kemudian gunakan dorongan ke depan dari kerapatan yang seragam pada disk sebagai kerapatan proposal dalam pengambilan sampel Metropolis-Hastings MCMC .

Nick Algeria
sumber
Namun, peta konformal tidak melestarikan kawasan; mereka mempertahankan sudut , tetapi ini hampir dijamin untuk tidak mengambil sampel poligon secara seragam.
Steven Stadnicki
Jadi kebutuhan untuk menggunakannya sebagai proposal di MCMC, bukan sebagai sampler yang sebenarnya. Dengan ketidaksamaan Poincare Anda dapat menunjukkan variasi peta konformal dari seragam dibatasi oleh konstanta.
Nick Alger
aP(x)<f(x)<bP(x)abf(x)=cP(x)∀x
Steven Stadnicki
Inti dari Metropolis Hastings MCMC adalah bahwa proposal tersebut bukan distribusi yang sebenarnya. Kecepatan konvergensi rantai MCMC tergantung pada seberapa baik proposal mendekati distribusi yang sebenarnya. Proposal yang paling umum adalah menempatkan gaussian pada titik saat ini, terlepas dari distribusi yang Anda coba sampel ...
Nick Alger