Losowe próbkowanie w wielokącie

9

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

John Mangual
źródło

Odpowiedzi:

9
  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
A.Schulz
źródło
Czy to pytanie nie jest duplikatem starszego, które łączysz?
Raphael
@Raphael: Powiązane, ale bardziej ogólne, powiedziałbym.
A.Schulz
4

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,y0,x+y1}. Aby równomiernie próbkować punkt z tego rozkładu, pierwsza próbkax[0,1] zgodnie z gęstością 2)(1-x) (tj. próbka munduru r[0,1] i oblicz x=1-1-r), a następnie próbka y[0,1-x] równomiernie (tzn. próbkuj mundur s[0,1] i oblicz y=(1-x)s). Jeszcze prostszą metodą jest próbkowaniex,y[0,1], i jeśli x+y>1 zastąpić (x,y) z (1-x,1-y).

Yuval Filmus
źródło
Próbkowanie przy odrzuceniu odrzuci z prawdopodobieństwem co najwyżej 1/2 na 2 wymiary, ale w wyższych wymiarach prawdopodobieństwo odrzucenia może być znacznie gorsze.
DW
Próbkowanie przy odrzuceniu może mieć większy współczynnik odrzucenia niż 1/2. Pomyśl tylko o spirali, lekko wytłoczonej.
A.Schulz
Co się stanie, jeśli wielokąt ma być wypukły?
Yuval Filmus,
Jeśli obwiednie są wyrównane względem osi, wypukłość nie jest pomocna; jak sugerują odpowiedzi na poprzednie pytanie, rozważ trójkąt z wierzchołkami w (0, 1), (1, 0) i (x, x) dla bardzo dużego x - zajmie to znikomą część jego obwiedni gdy x przechodzi w nieskończoność. Jeśli mówisz o najmniejszej możliwej obwiedni, to prawdopodobnie możesz wyliczyć granice objętości, którą zajmuje wypukły kształt, ale wtedy musisz znaleźć tę obwiednię ...
Steven Stadnicki
4

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órdo. 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 .

Nick Alger
źródło
Mapy konformalne niekoniecznie jednak zachowują obszar; oni kąt zachowania, ale to jest niemal gwarantowane nie do spróbowania wielokąt równomiernie.
Steven Stadnicki
Zatem potrzeba użycia go jako propozycji w MCMC, a nie jako rzeczywistego samplera. Dzięki nierówności Poincare możesz pokazać wariację mapy konformalnej od munduru ograniczoną stałą.
Nick Alger
Być może wciąż tego brakuje; dyskusja na wskazanej stronie Wikipedii mówi, że „dystrybucja próbna” nadal musi być bezpośrednia proporcjonalna do pożądanej dystrybucji; tzn. niezaP.(x)<fa(x)<bP.(x) dla niektórych stałych za i b, ale fa(x)=doP.(x)x. Lokalna wariancja odwzorowanej gęstości nadal będzie prowadzić do lokalnej wariancji w próbkowaniu.
Steven Stadnicki
Cały sens Metropolis Hastings MCMC polega na tym, że propozycja nie jest prawdziwą dystrybucją. Szybkość konwergencji łańcucha MCMC zależy od tego, jak dobrze propozycja przybliża prawdziwy rozkład. Najczęstszą propozycją jest umieszczenie gaussa w bieżącym punkcie, niezależnie od rozkładu, który próbujesz wypróbować ...
Nick Alger