Zufallsstichprobe in einem Polygon

9

Ich möchte einen gleichmäßig zufälligen Punkt in einem Polygon abtasten ...

Wenn eine große Anzahl beprobt wird, fallen sie mit gleicher Wahrscheinlichkeit in zwei Regionen, wenn sie dieselbe Fläche haben.

Dies wäre ziemlich einfach, wenn es ein Quadrat wäre, da ich zwei Zufallszahlen in [0,1] als meine Koordinaten nehmen würde.

Die Form, die ich habe, ist ein reguläres Polygon, aber ich möchte, dass es für jedes Polygon funktioniert.

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

algorithms randomness sampling random-number-generator John Mangual
quelle

Antworten:

9
  1. Triangulieren Sie das Polygon
  2. Bestimmen Sie, in welchem ​​der Dreiecke der Punkt liegen soll (gewichtet Dreiecksbereiche)
  3. Probieren Sie den Punkt im Dreieck aus, wie in diesem Beitrag erläutert
A.Schulz
quelle
Ist diese Frage nicht ein Duplikat der älteren, die Sie verlinken?
Raphael
@ Raphael: Verwandte, aber allgemeiner würde ich sagen.
A.Schulz
4

Eine einfache Möglichkeit ist es, die Zeichen - Box für Ihre Polygon und Verwendung Verwerfungsmethode zu finden: Probe aus dem Begrenzungsrahmen und akzeptieren , wenn sie innerhalb des Polygons fällt, die mit Wahrscheinlichkeit passieren werden mindestens (glaube ich).1/.2

Eine andere Möglichkeit besteht darin, Ihr Polygon zu triangulieren. Abtasten Sie zuerst ein Dreieck proportional und dann einen zufälligen Punkt im Dreieck. Letzteres ist einfach: Bis zu affinen Transformationen haben alle Dreiecke die Form . Um einen Punkt aus dieser Verteilung gleichmäßig abzutasten, muss zuerst x ∈ [ 0 , 1 ] gemäß der Dichte 2 ( 1 - x ) abgetastet werden (dh es wird ein gleichmäßiges r abgetastet{(x,y)::x,y≥0,x+y≤1}}x∈[0,1]]2(1- -x) und berechne x = 1 - √r∈[0,1]] ) und danny∈[0,1-x]gleichmäßig abtasten (dh eine einheitliches∈[0,1]abtasten undy=(1-x)sberechnen). Eine noch einfachere Methode besteht darin,x,y∈[0,1]abzutastenund(x,y) durchx+y>1 zuersetzen.x=1- -1- -ry∈[0,1- -x]]s∈[0,1]]y=(1- -x)sx,y∈[0,1]]x+y>1(x,y)mit .(1- -x,1- -y)

Yuval Filmus
quelle
Die Ablehnungsstichprobe wird mit einer Wahrscheinlichkeit von höchstens 1/2 in 2 Dimensionen zurückgewiesen, aber in höheren Dimensionen kann die Wahrscheinlichkeit einer Zurückweisung viel schlechter sein.
DW
Die Ablehnungsabtastung hat möglicherweise eine größere Ablehnungsrate als 1/2. Denken Sie nur an eine Spirale, die leicht extrudiert ist.
A.Schulz
Was ist, wenn das Polygon garantiert konvex ist?
Yuval Filmus
Wenn Ihre Begrenzungsrahmen achsenausgerichtet sind, ist Konvexität keine Hilfe. Wie aus den Antworten auf die vorherige Frage hervorgeht, betrachten Sie einfach ein Dreieck mit Eckpunkten bei (0, 1), (1, 0) und (x, x) für sehr großes x - dies nimmt einen verschwindend kleinen Teil seines Begrenzungsrahmens ein als x geht ins Unendliche. Wenn Sie über den kleinstmöglichen Begrenzungsrahmen sprechen, können Sie wahrscheinlich Grenzen für das Volumen ableiten, das Ihre konvexe Form einnimmt, aber dann müssen Sie den Rahmen finden ...
Steven Stadnicki
4

Das ist ein bisschen verrückt, sollte aber gut funktionieren, auch wenn Ihr Polygon sehr seltsam ist.

C.

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

Verwenden Sie dann die Vorwärtsbewegung einer einheitlichen Dichte auf der Disc als Vorschlagsdichte bei der Metropolis-Hastings-MCMC-Abtastung .

Nick Alger
quelle
Konforme Karten sind jedoch nicht unbedingt flächenerhaltend. sie sind Winkel zu bewahren, aber das ist fast garantiert nicht das Polygon gleichmäßig zu probieren.
Steven Stadnicki
Daher muss es als Vorschlag in MCMC verwendet werden, nicht als tatsächlicher Sampler. Mit der Poincare-Ungleichung können Sie zeigen, dass die Abweichung einer konformen Karte von der Uniform durch eine Konstante begrenzt ist.
Nick Alger
einP.(x)<f(x)<bP.(x)einbf(x)=cP.(x)∀x
Steven Stadnicki
Der springende Punkt bei Metropolis Hastings MCMC ist, dass der Vorschlag nicht die wahre Verteilung ist. Die Konvergenzgeschwindigkeit der MCMC-Kette hängt davon ab, wie gut sich der Vorschlag der tatsächlichen Verteilung annähert. Der häufigste Vorschlag ist, einen Gaußschen Wert an den aktuellen Punkt zu setzen, unabhängig von der Verteilung, die Sie abtasten möchten ...
Nick Alger