Punti casuali all'interno di un parallelogramma

Question

Ho un poligono convesso su 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 finché uno non è all'interno del poligono non funzionerebbe perché è davvero imprevedibile il tempo impiegato.

Answer 1

A. Se puoi limitare il tuo input al parallelogramma, questo è davvero 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 siano i lati, allora prendi il tuo punto 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 comunque usare le coordinate baricentriche. Le coordinate baricentriche corrispondono, per un quadrante, 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 tale che:

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

Nel tuo caso, puoi disegnare 4 numeri casuali e normalizzarli in modo che si sommino a 1. Questo ti darà un punto. Si noti che la distribuzione dei punti NON sarà uniforme in quel caso.

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

Answer 2

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

Al fine di raggiungere questo obiettivo:

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

   

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

   

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

   

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

   

5. Si noti che con probabilità 0,5, x si trova all'esterno del triangolo, tuttavia in tal caso 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 di pi (180 gradi). Il punto x 'sarà all'interno del triangolo.

6. Si noti inoltre che, se il quadrilatero era già un parallelogramma, allora non dobbiamo scegliere un triangolo a caso, possiamo sceglierne uno in modo deterministico, quindi scegliere il punto x senza verificare che sia all'interno triangolo sorgente.

Answer 3

Supponendo che desideri una distribuzione uniforme: forma due triangoli dal poligono. Scegli in 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 u e v. Sia p = u * AB + v * AC.

Se A + p è all'interno del triangolo, restituisce A + p

Se A + p è fuori dal triangolo, restituisce A + AB + AC - p

(Questa è sostanzialmente la formula di PierreBdR fatta eccezione per la preelaborazione e l'ultimo passaggio che ripiega il punto in un triangolo, in modo che possa gestire altre forme oltre ai parallelogrammi).

Answer 4

Il tuo poligono è composto da due triangoli, quindi perché non selezionarne uno a caso, quindi trovare un punto casuale nel triangolo.

Probabilmente non è la soluzione migliore, ma funzionerebbe.

Answer 5

Un po 'meno " na & # 239; ve < ! / a> <> quot; l'approccio sarebbe quello di utilizzare un algoritmo di riempimento poligonale , quindi selezionare i punti dalle linee di riempimento in modo casuale.

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<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(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 (i<nodes-1) {
    if (nodeX[i]>nodeX[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<nodes; i+=2) {
    if   (nodeX[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<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

Answer 6

Per " generale " intendi tutti i poligoni a 4 lati non parallelogrammi in generale o tutti i poligoni possibili?

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

.BBBB.
A    C
A    C
.DDDD.

Quindi genera un punto casuale su un quadrato di unità, quindi segna il punto sulla linea B e D sulla percentuale di distanza sull'asse X. Fai lo stesso sulla linea A e C usando il valore dell'asse Y.

Quindi collegare 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 è uniforme perché gli errori di arrotondamento aiuteranno alcuni punti, ma dovrebbe essere vicino se si lavora con valori in virgola mobile.

Anche l'implementazione dovrebbe essere piuttosto semplice, poiché stai già lavorando con i poligoni. Dovresti già avere un codice che svolge tali semplici compiti.

Ecco un rapido pseudocodice:

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);

}

Answer 7

Funziona con quadrilateri convessi generali:

È possibile prendere in prestito alcuni concetti dal metodo degli elementi finiti, in particolare per gli elementi quadrilaterali (a 4 lati) ( fai riferimento alla sezione 16.5 qui ). Fondamentalmente, esiste una parametrizzazione bilineare che mappa un quadrato nello spazio uv (per u, v \ in [-1, 1] in questo caso) al 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 base:

1. Scegli un generatore di numeri casuali adatto per generare punti ben distribuiti in un dominio 2D quadrato
2. Genera coppie u-v casuali nell'intervallo [-1, 1]
3. Per ogni coppia uv, il corrispondente punto casuale nel quad = 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 distribuiti uniformemente nello spazio u-v non produrranno punti distribuiti uniformemente nel tuo quad (nel senso euclideo). Se questo è importante, puoi lavorare direttamente in 2D all'interno del riquadro di delimitazione del quad e scrivere un test point-in-quad (magari dividendo il problema in due punti in tris) per eliminare i punti casuali che si trovano all'esterno.

Answer 8

I punti devono essere distribuiti uniformemente o la distribuzione va bene?

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

Se la risposta a entrambi i precedenti è no, allora scegli due qualsiasi dei vertici e scegli un punto casuale sul segmento di linea tra di loro. Ciò è limitato ai segmenti di linea che collegano i vertici (cioè MOLTO non uniformi); puoi fare un po 'meglio selezionando un terzo vertice e quindi selezionando un punto tra quello e il primo punto - ancora non uniforme, ma almeno qualsiasi punto nel poligono è possibile

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

Answer 9

Che tipo di distribuzione vuoi avere i punti? Se non ti interessa, i metodi di cui sopra funzioneranno bene. Se si desidera una distribuzione uniforme, funzionerà la seguente procedura: Dividere il poligono in due triangoli, a e b. Sia A (a) e A (b) le loro aree. Campionare un punto p dalla distribuzione uniforme sull'intervallo tra 0 e A (a) + A (b). Se p & Lt; A (a), selezionare il triangolo a. Altrimenti, scegli triangolo b. Scegli un vertice v del triangolo scelto e lascia che c e d siano i vettori corrispondenti ai lati del triangolo. Campionare due numeri xey dalla distribuzione esponenziale con media unitaria. Quindi il punto (xc + yd) / (x + y) è un campione della distribuzione uniforme sul poligono.

Answer 10

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

Answer 11

Per PostGIS, questo è quello che sto usando (potresti voler un reparto per possibili cicli 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;