Amostragem aleatória em um polígono

9

Gostaria de provar um ponto uniformemente aleatório em um polígono ...

Se provar um número grande, eles provavelmente cairão em duas regiões se tiverem a mesma área.

Isso seria bem simples se fosse um quadrado, pois eu usaria dois números aleatórios em [0,1] como minhas coordenadas.

A forma que tenho é um polígono regular, mas eu gostaria que funcionasse para qualquer polígono.

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

algorithms randomness sampling random-number-generator john mangual
fonte

Respostas:

9
  1. Triangular o polígono
  2. Determine em qual dos triângulos o ponto deve estar (pesa áreas do triângulo)
  3. Faça uma amostra do ponto no triângulo, conforme explicado nesta postagem
A.Schulz
fonte
Esta pergunta não é uma duplicata da pergunta mais antiga que você vincula?
Raphael
@ Rafael: Relacionado, mas mais geral, eu diria.
A.Schulz
4

Uma maneira fácil é encontrar a caixa delimitadora para o seu polígono e uso rejeição de amostragem: amostra da caixa delimitadora e aceito se ele cai dentro do polígono, o que vai acontecer com probabilidade , pelo menos, (eu acho).1 1/2

Outra possibilidade é triangular seu polígono. Primeiro experimente um triângulo de maneira proporcional e, em seguida, experimente um ponto aleatório no triângulo. O último é simples: até transformações afins, todos os triângulos têm a forma . Para amostrar uniformemente um ponto dessa distribuição, primeira amostra x ∈ [ 0 , 1 ] de acordo com a densidade 2 ( 1 - x ) (isto é, amostra um r uniforme{(x,y):x,y≥0 0,x+y≤1 1}x∈[0 0,1 1]2(1 1-x) e calcule x = 1 - √r∈[0 0,1 1] ) e depois amostrary∈[0,1-x]uniformemente (ou seja, provar asuniforme∈[0,1]e calculary=(1-x)s). Um método ainda mais simples é a amostrax,y∈[0,1], e sex+y>1substitua(x,y)x=1−1−ry∈[0,1−x]s∈[0,1]y=(1−x)sx,y∈[0,1]x+y>1(x,y)com .(1−x,1−y)

Yuval Filmus
fonte
A amostragem de rejeição rejeitará com probabilidade no máximo 1/2 em 2 dimensões, mas em dimensões mais altas a probabilidade de rejeição pode ser muito pior.
DW
A amostragem de rejeição pode ter uma taxa de rejeição maior que 1/2. Basta pensar em uma espiral, levemente extrudada.
precisa saber é o seguinte
E se for garantido que o polígono é convexo?
Yuval Filmus
Se suas caixas delimitadoras estiverem alinhadas ao eixo, a convexidade não ajudará; como sugerem as respostas da pergunta anterior, considere apenas um triângulo com vértices em (0, 1), (1, 0) e (x, x) para x muito grande - isso ocupará uma proporção muito pequena da sua caixa delimitadora como x vai para o infinito. Se você está falando de menor caixa delimitadora do possível, então você pode provavelmente limites retirarem o volume a sua forma convexa ocupa, mas então você tem que encontrar a caixa ...
Steven Stadnicki
4

Isso é um pouco louco, mas deve funcionar bem, mesmo que seu polígono seja muito estranho.

Use o Teorema de Reimann para encontrar uma projecção conforme partir do disco de unidade para seu polígono, vendo-o como um subconjunto de . Veja, por exemplo, as referências em:C

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

Em seguida, use o pushforward de uma densidade uniforme no disco como a densidade proposta na amostragem Metropolis-Hastings MCMC .

Nick Alger
fonte
Os mapas conformes não são necessariamente de preservação de área; eles preservam o ângulo , mas é quase garantido que não seja possível amostrar o polígono uniformemente.
Steven Stadnicki
Daí a necessidade de usá-lo como uma proposta no MCMC, não como um amostrador real. Com a desigualdade de Poincaré, é possível mostrar que a variação de um mapa conforme do uniforme é limitada por uma constante.
Nick Alger
aP(x)<f(x)<bP(x)abf(x)=cP(x)∀x
Steven Stadnicki
O ponto principal do Metropolis Hastings MCMC é que a proposta não é a verdadeira distribuição. A velocidade de convergência da cadeia MCMC depende de quão bem a proposta se aproxima da verdadeira distribuição. A proposta mais comum é colocar um Gaussian no ponto atual, independentemente da distribuição que você está tentando amostra ...
Nick Alger