Punti casuali all’interno di un parallelogramma

Ho un poligono convesso di 4 lati definito da 4 punti in 2D, e voglio essere in grado di generare punti casuali al suo interno.

Se semplifica davvero il problema, posso limitare il poligono a un parallelogramma, ma è preferibile una risposta più generale.

Generare punti casuali fino a quando uno è all’interno del poligono non funzionerebbe perché è davvero imprevedibile il tempo necessario.

A. Se riesci a limitare l’input al parallelogramma, questo è molto semplice:

  1. Prendi due numeri casuali tra 0 e 1. Chiameremo quindi u e v .
  2. Se il tuo parallelogramma è definito dai punti ABCD in modo tale che AB, BC, CD e DA sono i lati, prendi il tuo punto di vista come:

      p = A + (u * AB) + (v * AD) 

Dove AB è il vettore da A a B e AD il vettore da A a D.

B. Ora, se non puoi, puoi ancora usare le coordinate baricentriche. Le coordinate baricentriche corrispondono, per un quadruplo, a 4 coordinate (a,b,c,d) tali che a+b+c+d=1 . Quindi, qualsiasi punto P all’interno del quad può essere descritto da un 4-uple in modo tale che:

 P = a A + b B + c C + d D 

Nel tuo caso, puoi disegnare 4 numeri casuali e normalizzarli in modo che aggiungano fino a 1. Questo ti darà un punto. Nota che la distribuzione dei punti NON sarà uniforms in quel caso.

C. Puoi anche, come proposto altrove, scomporre il quad in due triangoli e usare il metodo semic parallelo (cioè, come il parallelogramma ma aggiungi la condizione u+v=1 ) o le coordinate baricentriche per i triangoli. Tuttavia, se si desidera una distribuzione uniforms, la probabilità di avere un punto in uno dei triangoli deve essere uguale all’area del triangolo divisa per l’area del quad.

La domanda dell’OP è un po ‘ambigua quindi la domanda a cui risponderò è: Come generare un punto da una distribuzione uniforms all’interno di un quadrilatero arbitrario , che è in realtà una generalizzazione di Come generare un punto da una distribuzione uniforms all’interno di un arbitrario ( poligono convesso) . La risposta si basa sul caso di generare un campione da una distribuzione uniforms in un triangolo (vedi http://mathworld.wolfram.com/TrianglePointPicking.html , che ha una spiegazione molto bella).

Per realizzare questo noi:

  1. Triangola il poligono (cioè genera una raccolta di regioni triangolari non sovrapposte che coprono il poligono). Nel caso di un quadrilatero, crea un bordo attraverso qualsiasi due vertici non adiacenti. Per altri poligoni, vedi http://en.wikipedia.org/wiki/Polygon_triangulation per un punto di partenza, o http://www.cgal.org/ se hai solo bisogno di una biblioteca.

    inserisci la descrizione dell'immagine qui

  2. Per scegliere uno dei triangoli in modo casuale, assegniamo un indice a ciascun triangolo (cioè 0,1,2, …). Per il quadrilatero, saranno 0,1. Per ogni triangolo assegniamo un peso uguale come segue:

    calcolo del peso

  3. Quindi genera un indice casuale i dalla distribuzione finita sugli indici in base al loro peso. Per il quadrilatero, questa è una distribuzione di Bernoulli:

    inserisci la descrizione dell'immagine qui

  4. Sia v0, v1, v2 siano i vertici del triangolo (rappresentati dalle loro posizioni dei punti, in modo che v0 = (x0, y0), ecc. Quindi generiamo due numeri casuali a0 e a1, entrambi disegnati uniformsmente dall’intervallo [0,1 ] Quindi calcoliamo il punto casuale x per x = a0 (v1-v0) + a1 (v2-v0).

    inserisci la descrizione dell'immagine qui

  5. Si noti che con probabilità 0.5, x giace all’esterno del triangolo, tuttavia se lo fa, si trova all’interno del parallelogramma composto dall’unione del triangolo con la sua immagine dopo una rotazione di pi attorno al punto medio di (v1, v2) (linee tratteggiate nell’immagine). In tal caso, possiamo generare un nuovo punto x ‘= v0 + R (pi) (x – v3), dove R (pi) è una rotazione per pi (180 gradi). Il punto x ‘sarà all’interno del triangolo.

  6. Inoltre, se il quadrilatero era già un parallelogramma, non è necessario selezionare un triangolo a caso, possiamo selezionarne uno in modo deterministico e quindi scegliere il punto x senza verificare che si trovi all’interno del triangolo sorgente.

Supponendo che tu voglia una distribuzione uniforms: forma due triangoli dal tuo poligono. Scegli quale triangolo generare il punto in base al loro rapporto di area.

Chiama gli angoli del triangolo A, B, C, i vettori laterali AB, BC, AC e genera due numeri casuali in [0,1] chiamati uev. Sia p = u * AB + v * AC.

Se A + p è all’interno del triangolo, restituisci A + p

Se A + p è fuori dal triangolo, restituisci A + AB + AC – p

(Questa è fondamentalmente la formula di PierreBdR ad eccezione della pre-elaborazione e dell’ultimo passo che ripiega il punto in un triangolo, in modo che possa gestire altre forms rispetto ai parallelogrammi).

Il tuo poligono è di due triangoli, quindi perché non sceglierne uno a caso, quindi trova un punto casuale nel triangolo.

Probabilmente non è la soluzione migliore, ma funzionerebbe.

Un approccio un po ‘meno ” ingenuo ” sarebbe quello di utilizzare un algoritmo di riempimento poligonale e quindi selezionare i punti dalle linee di riempimento a caso.

Esempio di codice C

 // public-domain code by Darel Rex Finley, 2007 int nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ; // Loop through the rows of the image. for (pixelY=IMAGE_TOP; pixelY=(double) pixelY || polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) { nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i]) *(polyX[j]-polyX[i])); } j=i; } // Sort the nodes, via a simple “Bubble” sort. i=0; while (inodeX[i+1]) { swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; } else { i++; }} // Fill the pixels between node pairs. // Code modified by SoloBold 27 Oct 2008 // The flagPixel method below will flag a pixel as a possible choice. for (i=0; i=IMAGE_RIGHT) break; if (nodeX[i+1]> IMAGE_LEFT ) { if (nodeX[i ]< IMAGE_LEFT ) nodeX[i ]=IMAGE_LEFT ; if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT; for (j=nodeX[i]; j 

Con “generale” intendi tutti i poligoni a 4-lati non-parallelogramma in generale o tutti i possibili poligoni?

Che ne dici di disegnare una linea casuale che collega i 4 lati, ad es. Se hai questo:

 .BBBB. AC AC .DDDD. 

Quindi genera un punto casuale su un quadrato unitario, quindi contrassegna il punto sulla linea B e D sulla percentuale di distanza sull’asse X. Fai lo stesso sulle linee A e C usando il valore dall’asse Y.

Quindi colbind il punto sulla linea A alla linea C e la linea B alla linea D, il punto di intersezione viene quindi utilizzato come punto casuale.

Non è uniforms perché gli errori di arrotondamento aiuteranno alcuni punti, ma dovrebbe essere vicino se lavori con valori a virgola mobile.

Anche l’implementazione dovrebbe essere abbastanza facile, dato che stai già lavorando con i poligoni. Dovresti già avere il codice che fa quelle semplici attività.

Ecco uno pseudocodice veloce:

 void GetRandomPoint(Polygon p, ref float x, ref float y) { float xrand = random(); float yrand = random(); float h0 = p.Vertices[0] + xrand * p.Vertices[1]; float h1 = p.Vertices[2] + yrand * p.Vertices[3]; float v0 = p.Vertices[0] + xrand * p.Vertices[2]; float v1 = p.Vertices[1] + yrand * p.Vertices[3]; GetLineIntersection(h0, h1, v0, v1, x, y); } 

Funziona per quadrilateri generali e convessi:

È ansible prendere in prestito alcuni concetti dal metodo degli elementi finiti, in particolare per gli elementi quadrilateri (a 4 lati) ( fare riferimento alla sezione 16.5 qui ). Fondamentalmente, c’è una parametrizzazione bilineare che mappa un quadrato nello spazio uv (per u, v \ in [-1, 1] in questo caso) al tuo quadrilatero che consiste di punti p_i (per i = 1,2,3,4 ). Si noti che nel riferimento fornito, i parametri sono chiamati \ eta e \ xi.

Ricetta di base:

  1. Scegli un generatore di numeri casuali adatto per generare punti ben distribuiti in un dominio 2D quadrato
  2. Genera coppie uv casuali nell’intervallo [-1, 1]
  3. Per ogni coppia uv, il punto casuale corrispondente nel quadruplo = 1/4 * ((1-u) (1-v) * p_1 + (1 + u) (1-v) * p_2 + (1 + u) ( 1 + v) * p_3 + (1-u) (1 + v) * p_4)

L’unico problema è che i punti uniformsmente distribuiti nello spazio uv non producono punti distribuiti uniformsmente nel quad (nel senso euclideo). Se ciò è importante, puoi lavorare direttamente in 2D all’interno del riquadro di delimitazione del quad e scrivere un point-in-quad (magari dividendo il problema in due punti in tris) per scovare i punti casuali che si trovano all’esterno.

I punti devono essere distribuiti uniformsmente, o c’è qualche distribuzione ok?

Il poligono può essere concavo o è garantito per essere convesso?

Se la risposta a entrambi i precedenti è no, quindi scegli due qualsiasi dei vertici e scegli un punto casuale sul segmento di linea tra loro. Questo è limitato ai segmenti di linea che collegano i vertici (cioè, MOLTO non uniforms); puoi fare un po ‘meglio selezionando un terzo vertice e poi selezionando un punto tra quello e il primo punto – ancora non uniforms, ma è ansible che almeno un punto del poligono sia ansible

Scegliere un punto casuale su una linea tra due punti è facile, solo A + p (BA), dove A e B sono i punti e p è un numero casuale compreso tra 0.0 e 1.0

Che tipo di distribuzione vuoi che i punti abbiano? Se non ti interessa, i metodi sopra funzioneranno bene. Se vuoi una distribuzione uniforms, la seguente procedura funzionerà: Dividi il poligono in due triangoli, a e b. Sia A (a) e A (b) le loro aree. Campionare un punto p dalla distribuzione uniforms nell’intervallo tra 0 e A (a) + A (b). Se p

La funzione MATLAB cprnd genera punti dalla distribuzione uniforms su un politopo convesso generale. Per la tua domanda è più efficiente un algoritmo più specializzato basato sulla scomposizione del quadrilatero in triangoli.

Per PostGIS, questo è quello che sto usando (potresti volere un reparto per possibili loop infiniti). Potresti esportare l’algoritmo nel tuo linguaggio di programmazione:

 CREATE or replace FUNCTION random_point(geometry) RETURNS geometry AS $$ DECLARE env geometry; corner1 geometry; corner2 geometry; minx real; miny real; maxx real; maxy real; x real; y real; ret geometry; begin select ST_Envelope($1) into env; select ST_PointN(ST_ExteriorRing(env),1) into corner1; select ST_PointN(ST_ExteriorRing(env),3) into corner2; select st_x(corner1) into minx; select st_x(corner2) into maxx; select st_y(corner1) into miny; select st_y(corner2) into maxy; loop select minx+random()*(maxx-minx) into x; select miny+random()*(maxy-miny) into y; select ST_SetSRID(st_point(x,y), st_srid($1)) into ret; if ST_Contains($1,ret) then return ret ; end if; end loop; end; $$ LANGUAGE plpgsql volatile RETURNS NULL ON NULL INPUT;