Losowe próbkowanie w wielokącie

Chciałbym pobrać próbkę jednorodnie losowego punktu w wielokącie ...

Gdyby pobrać próbkę dużej liczby, równie dobrze mogliby wpaść w dwa regiony, jeśli mają ten sam obszar.

Byłoby to dość proste, gdyby był kwadratem, ponieważ jako moje współrzędne wziąłbym dwie liczby losowe w [0,1].

Kształt, który mam, jest zwykłym wielokątem, ale chciałbym, aby działał dla każdego wielokąta.

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

1. Trójkątowanie wielokąta
2. Określ, w którym z trójkątów powinien znajdować się punkt (waży obszary trójkąta)
3. Próbkuj punkt w trójkącie, jak wyjaśniono w tym poście

Jednym prostym sposobem jest znalezienie ramki granicznej dla swojego wielokąta i użycie próbkowania odrzucenia: pobierz próbkę z ramki granicznej i zaakceptuj, czy mieści się ona w wielokącie, co nastąpi z prawdopodobieństwem $1/2$ przynajmniej (tak mi się wydaje).

Inną możliwością jest triangulacja wielokąta. Najpierw próbkuj trójkąt w sposób proporcjonalny, a następnie próbkuj losowy punkt w trójkącie. To ostatnie jest proste: aż do afinicznych przekształceń, wszystkie trójkąty mają formę$\{(x,y) : x,y \geq 0, x+y \leq 1\}$. Aby równomiernie próbkować punkt z tego rozkładu, pierwsza próbka$x \in [0,1]$ zgodnie z gęstością $2(1-x)$ (tj. próbka munduru $r \in [0,1]$ i oblicz $x = 1-\sqrt{1-r}$), a następnie próbka $y \in [0,1-x]$ równomiernie (tzn. próbkuj mundur $s \in [0,1]$ i oblicz $y = (1-x)s$). Jeszcze prostszą metodą jest próbkowanie$x,y \in [0,1]$, i jeśli $x+y > 1$ zastąpić $(x,y)$ z $(1-x,1-y)$.

To trochę szalone, ale powinno działać dobrze, nawet jeśli twój wielokąt jest bardzo dziwny.

Skorzystaj z twierdzenia o odwzorowaniu Reimanna, aby znaleźć mapę konformalną z dysku jednostki na wielokąt, widząc ją jako podzbiór$\mathbb{C}$. Zobacz na przykład odniesienia w:

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

Następnie użyj przesunięcia o jednolitą gęstość na dysk jako gęstość propozycji w próbkowaniu MetropMC-Hastings MCMC .