Muestreo aleatorio en un polígono

9

Me gustaría probar un punto aleatorio uniforme en un polígono ...

Si muestra una gran cantidad, es probable que se dividan en dos regiones si tienen la misma área.

Esto sería bastante simple si fuera un cuadrado, ya que tomaría dos números aleatorios en [0,1] como mis coordenadas.

La forma que tengo es un polígono regular, pero me gustaría que funcione para cualquier polígono.

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

algorithms randomness sampling random-number-generator john mangual
fuente

Respuestas:

9
  1. Triangular el polígono
  2. Determine en cuál de los triángulos debe estar el punto (pondera las áreas del triángulo)
  3. Muestra el punto en el triángulo como se explica en esta publicación
A.Schulz
fuente
¿Esta pregunta no es un duplicado de la anterior que usted vincula?
Raphael
@Raphael: Relacionado, pero más general, diría.
A.Schulz
4

Una forma fácil es encontrar el cuadro de límite para su muestreo rechazo polígono y uso: muestra del cuadro delimitador y aceptar si se encuentra dentro del polígono, lo que va a ocurrir con una probabilidad de por lo menos (creo).1/2

{(x,y):x,y≥0,x+y≤1}x∈[0,1]2(1−x)r∈[0,1]x=1−1−ry∈[0,1−x]s∈[0,1]y=(1−x)sx,y∈[0,1]x+y>1(x,y)(1−x,1−y)

Yuval Filmus
fuente
El muestreo de rechazo rechazará con probabilidad como máximo 1/2 en 2 dimensiones, pero en dimensiones más altas la probabilidad de rechazo podría ser mucho peor.
DW
El muestreo de rechazo puede tener una tasa de rechazo mayor que 1/2. Solo piense en una espiral, ligeramente extruida.
A.Schulz
¿Qué pasa si se garantiza que el polígono sea convexo?
Yuval Filmus
Si sus cuadros delimitadores están alineados con el eje, entonces la convexidad no es de ayuda; Como sugieren las respuestas a la pregunta anterior, solo considere un triángulo con vértices en (0, 1), (1, 0) y (x, x) para x muy grande: esto ocupará una proporción muy pequeña de su cuadro delimitador como x va al infinito Si está hablando del cuadro delimitador más pequeño posible, entonces probablemente pueda derivar límites en el volumen que ocupa su forma convexa, pero luego debe encontrar el cuadro ...
Steven Stadnicki
4

Esto es un poco loco, pero debería funcionar bien incluso si su polígono es muy extraño.

C

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

Luego, utilice el avance de una densidad uniforme en el disco como la densidad propuesta en el muestreo MCMC de Metropolis-Hastings .

Nick Alger
fuente
Sin embargo, los mapas conformales no necesariamente conservan el área; son ángulo de preservación, pero esto es casi seguro que no muestrear el polígono de manera uniforme.
Steven Stadnicki
De ahí la necesidad de usarlo como una propuesta en MCMC, no como una muestra real. Con la desigualdad de Poincare puede mostrar que la variación de un mapa conforme del uniforme está limitada por una constante.
Nick Alger
aP(x)<f(x)<bP(x)abf(x)=cP(x)∀x
Steven Stadnicki
El objetivo de Metropolis Hastings MCMC es que la propuesta no es la verdadera distribución. La velocidad de convergencia de la cadena MCMC depende de qué tan bien se aproxima la propuesta a la distribución real. La propuesta más común es poner un gaussiano en el punto actual, independientemente de la distribución que esté tratando de probar ...
Nick Alger