Come trovare un punto casuale in un quadrilatero?

Devo essere in grado di impostare una posizione casuale per un waypoint per una simulazione di volo. La sfida matematica è semplice:

“Per trovare una singola posizione casuale all’interno di un quadrilatero, dove c’è un’uguale possibilità che il punto sia in qualsiasi posizione.”

Visivamente piace questo:

alt text

Un quadrilatero ABCD di esempio è: A: [21417.78 37105.97] B: [38197.32 24009.74] C: [1364.19 2455.54] D: [1227.77 37378.81]

Grazie in anticipo per qualsiasi aiuto tu possa fornire. 🙂

EDIT Grazie a tutti per le vostre risposte. Domani darò un’occhiata a questo e premierò la risposta accettata. A proposito avrei dovuto dire che il quadrilatero può essere CONVESSO O CONCAVO. Sry ‘dat.

Dividi il tuo quadrilatero in due triangoli e poi usa questa eccellente risposta SO per trovare rapidamente un punto casuale in uno di essi.

Aggiornare:

Prendendo in prestito questo grande link da Akusete sul raccogliere un punto casuale in un triangolo.

figura principale http://sofit.miximages.com/c%23/TrianglePointPicking_700.gif

Dato un triangolo con un vertice all’origine e gli altri alle posizioni v 1 e v 2 , selezionare x http://sofit.miximages.com/c%23/NumberedEquation2.gif dove A 1 e A 2 sono variabili uniformi nell’intervallo [0,1] , che dà punti distribuiti uniformsmente in un quadrilatero (figura a sinistra). I punti non all’interno del triangolo possono quindi essere scartati o trasformati nel punto corrispondente all’interno del triangolo (figura a destra).

Credo che ci siano due modi adatti per risolvere questo problema.

Il primo citato da altri poster è quello di trovare il riquadro di delimitazione più piccolo che racchiude il rettangolo, quindi generare punti in quella casella fino a trovare un punto che si trova all’interno del rettangolo.

Find Bounding box (x,y,width, height) Pick Random Point x1,y1 with ranges [x to x+width] and [y to y+height] while (x1 or y1 is no inside the quadrangle){ Select new x1,y1 } 

Supponendo che l’area del quadrilatero sia Q e il riquadro di delimitazione sia A, la probabilità che tu debba generare N coppie di punti è 1- (Q / A) ^ N, che si avvicina a 0 inverso in modo esponenziale.

Vorrei raccomandare l’approccio di cui sopra, in particolare in due dimensioni. È molto veloce generare i punti e testare.

Se si desidera un gaurentee di terminazione, è ansible creare un algoritmo per generare solo punti all’interno del quadrilatero (facile), ma è necessario assicurarsi che la distribuzione della probabilità dei punti sia pari al quadrilatero.

http://mathworld.wolfram.com/TrianglePointPicking.html

Offre un’ottima esplorazione

L’approccio “forza bruta” è semplicemente quello di scorrere fino a quando non si dispone di una coordinata valida. In pseudocodice:

 left = min(pa.x, pb.x, pc.x, pd.x) right = max(pa.x, pb.x, pc.x, pd.x) bottom = min(pa.y, pb.y, pc.y, pd.y) top = max(pa.y, pb.y, pc.y, pd.y) do { x = left + fmod(rand, right-left) y = bottom + fmod(rand, top-bottom) } while (!isin(x, y, pa, pb, pc, pd)); 

È ansible utilizzare una funzione di magazzino estratta dalla rete per “isin”. Mi rendo conto che questa non è la cosa che esegue più velocemente il mondo, ma penso che funzionerà.

Quindi, questa volta si affronta come capire se un punto è all’interno del quadruplo:

I quattro bordi possono essere espressi come linee nella forma y = mx + b . Controlla se il punto si trova sopra o sotto ciascuna delle quattro linee e, preso insieme, puoi capire se è dentro o fuori.

Ti è permesso semplicemente provare ripetutamente da qualche parte all’interno del rettangolo che delimita il quadrilatero, fino a quando non ottieni qualcosa nel quad? Potrebbe persino essere più veloce di un algoritmo elaborato per assicurarti di scegliere qualcosa all’interno del quad?

Per inciso, in questa affermazione problematica, penso che l’uso della parola “trovare” sia fonte di confusione. Non puoi davvero trovare un valore casuale che soddisfi una condizione; il randomizzatore te lo dà. Quello che stai cercando di fare è impostare i parametri sul randomizer per darti valori corrispondenti a determinati criteri.

Dividerei il tuo quadrilatero in più figure, dove ogni figura è un poligono regolare con un lato (o entrambi i lati) parallelo a uno degli assi. Ad esempio, per la figura sopra, vorrei prima trovare il rettangolo massimo che si adatta all’interno del quadrilatero, il rettangolo deve essere parallelo agli assi X / Y. Quindi nell’area rimanente, inserirò dei triangoli, tali triangoli saranno adiacenti a ciascun lato del rettangolo.

allora è semplice scrivere una funzione:

1) ottenere una figura a caso. 2) trova un punto casuale nella figura.

Se la figura scelta in # 1 è un rettangolo, dovrebbe essere piuttosto facile trovarne un punto a caso. La parte difficile è scrivere una routine che può trovare un punto casuale all’interno del triangolo

Puoi casualmente creare punti in un bound-in-box fermandoti solo dopo averne trovato uno che è all’interno del tuo poligono.

Così:

  1. Trova la scatola che contiene tutti i punti del tuo poligono.
  2. Creare un punto casuale all’interno dei limiti della casella precedentemente trovata. Utilizzare le funzioni casuali per generare valori xey.
  3. Controlla se quel punto si trova all’interno del poligono (vedi come qui o qui )
  4. Se quel punto si trova all’interno del poligono, hai finito, se non vai al passaggio 2

Quindi, dipende da come vuoi la tua distribuzione.

Se vuoi che i punti vengano campionati casualmente nel tuo spazio di visualizzazione 2D, la risposta di Jacob è ottima. Se vuoi che i punti siano come una prospettiva (nell’immagine di esempio, più densità in alto a destra che in basso a sinistra), puoi utilizzare l’interpolazione bilineare.

L’interpolazione bilineare è abbastanza semplice. Genera due numeri casuali s e t nell’intervallo [0..1]. Quindi se i tuoi punti di input sono p0, p1, p2, p3 l’interpolazione bilineare è:

 bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0) 

La differenza principale è se vuoi che la tua distribuzione sia uniforms nello spazio 2d (metodo di Jacob) o uniforms nello spazio dei parametri.

Questo è un problema interessante e probabilmente c’è una risposta davvero interessante, ma se vuoi semplicemente che funzioni, lascia che ti offra qualcosa di semplice.

Ecco l’algoritmo:

  1. Scegli un punto casuale che si trova all’interno del rettangolo che delimita il quadrilatero.
  2. Se non si trova nel quadrilatero (o in qualsiasi forma), ripetere.
  3. Profitto!

modificare

Ho aggiornato il primo passo per menzionare il riquadro di delimitazione, secondo il suggerimento di Bart K.