Échantillonnage aléatoire dans un polygone

9

Je voudrais échantillonner un point uniformément aléatoire dans un polygone ...

S'ils en échantillonnent un grand nombre, ils seraient également susceptibles de tomber dans deux régions s'ils ont la même superficie.

Ce serait assez simple s'il s'agissait d'un carré car je prendrais deux nombres aléatoires en [0,1] comme coordonnées.

La forme que j'ai est un polygone régulier, mais j'aimerais qu'il fonctionne pour n'importe quel polygone.

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

algorithms randomness sampling random-number-generator John mangual
la source

Réponses:

9
  1. Trianguler le polygone
  2. Déterminez dans lequel des triangles le point doit se trouver (pondère les zones de triangle)
  3. Échantillonnez le point dans le triangle comme expliqué dans cet article
A.Schulz
la source
Cette question n'est-elle pas un double de l'ancienne que vous liez?
Raphael
@Raphael: Associé, mais plus général, je dirais.
A.Schulz
4

Un moyen facile est de trouver la boîte englobante pour votre polygone et utiliser un échantillonnage de rejet: échantillon de la zone de délimitation et d' accepter si elle tombe dans le polygone, qui se produira avec une probabilité au moins (je pense).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
la source
L'échantillonnage de rejet rejettera avec une probabilité d'au plus 1/2 en 2 dimensions, mais dans des dimensions plus élevées, la probabilité de rejet pourrait être bien pire.
DW
L'échantillonnage de rejet peut avoir un taux de rejet supérieur à 1/2. Pensez juste à une spirale, légèrement extrudée.
A.Schulz
Et si le polygone est garanti convexe?
Yuval Filmus
Si vos boîtes de délimitation sont alignées sur l'axe, alors la convexité n'est d'aucune aide; comme le suggèrent les réponses à la question précédente, il suffit de considérer un triangle avec des sommets à (0, 1), (1, 0) et (x, x) pour un très grand x - cela occupera une proportion infiniment petite de sa boîte englobante lorsque x va à l'infini. Si vous parlez de la plus petite boîte englobante possible, vous pouvez probablement déduire des limites sur le volume que prend votre forme convexe, mais alors vous devez trouver la boîte ...
Steven Stadnicki
4

C'est un peu fou, mais ça devrait bien marcher même si votre polygone est très bizarre.

C

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

Utilisez ensuite la poussée vers l'avant d'une densité uniforme sur le disque comme densité de proposition dans l' échantillonnage MCMC de Metropolis-Hastings .

Nick Alger
la source
Les cartes conformes ne préservent pas nécessairement la zone, cependant; ils préservent l' angle , mais cela est presque garanti de ne pas échantillonner le polygone uniformément.
Steven Stadnicki
D'où la nécessité de l'utiliser comme une proposition dans MCMC, pas comme un véritable échantillonneur. Avec l'inégalité de Poincaré, vous pouvez montrer la variation d'une carte conforme d'uniforme est délimitée par une constante.
Nick Alger
aP(x)<f(x)<bP(x)abf(x)=cP(x)∀x
Steven Stadnicki
L'intérêt de Metropolis Hastings MCMC est que la proposition n'est pas la vraie distribution. La vitesse de convergence de la chaîne MCMC dépend de la façon dont la proposition se rapproche de la distribution réelle. La proposition la plus courante consiste à mettre un gaussien au point actuel, quelle que soit la distribution que vous essayez d'échantillonner ...
Nick Alger