campione punto casuale nel triangolo

Question

Supponiamo di avere un triangolo arbitrario con i vertici A, B e C. This paper (section 4.2) dice che è possibile generare un punto casuale, P, uniformemente dall'interno triangolo ABC dal seguente combinazione convessa dei vertici:

P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C 

dove r1 e r2 sono uniformemente tratti da [0, 1], e sqrt è la funzione radice quadrata .

Come si giustifica che i punti campionati che sono distribuiti uniformemente all'interno del triangolo ABC?

EDIT

Come sottolineato in un commento su the mathoverflow question, Graphical Gems discusses this algorithm.

Answer 1

Hai una mappa P (r1, r2) dal quadrato dell'unità al tuo triangolo. Scegliendo r1 e r2 in modo uniforme si ottiene un punto casuale nel quadrato unitario. L'immagine nel triangolo è distribuita secondo il determinante Jacobiano della mappa P, che risulta essere una costante. Pertanto anche la distribuzione dell'immagine è uniforme.

In realtà, per verificare questo è necessario solo verificarlo per un triplo di punti non collineari A, B, C. Le mappe lineari affini hanno Jacobian costante, quindi puoi applicare una di queste per spostare una tripla arbitraria in questa posizione standard senza influire sulla distribuzione.

Infine, una parola sul "perché": considera il triangolo come compilato da segmenti di linea paralleli al lato BC. Nella formula per P, la variabile r1 seleziona su quale segmento sarà posizionato il punto, mentre r2 determina dove sarà lungo il segmento. Per uniformità, tutti i punti su un dato segmento dovrebbero essere trattati allo stesso modo (quindi lineare in r2). Ma per r1, poiché alcuni segmenti sono più brevi di altri, dobbiamo favorire i segmenti lunghi per ottenere una distribuzione uniforme. Il sqrt (r1) nella formula tiene conto di ciò.