Puntos aleatorios dentro de un paralelogramo

StackOverflow https://stackoverflow.com/questions/240778

Pregunta

Tengo un polígono convexo de 4 lados definido por 4 puntos en 2D y quiero poder generar puntos aleatorios dentro de él.

Si realmente simplifica el problema, puedo limitar el polígono a un paralelogramo, pero se prefiere una respuesta más general.

Generar puntos aleatorios hasta que uno esté dentro del polígono no funcionaría porque el tiempo que lleva es realmente impredecible.

¿Fue útil?

Solución

A.Si puedes restringir tu entrada a paralelogramo, esto es realmente simple:

  1. Tome dos números aleatorios entre 0 y 1.llamaremos entonces u y v.

  2. Si su paralelogramo está definido por los puntos ABCD de modo que AB, BC, CD y DA son los lados, entonces tome su punto como:

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

Dónde AB es el vector de A a B y AD el vector de A a D.

B.Ahora, si no puedes, aún puedes usar las coordenadas baricéntricas.Las coordenadas baricéntricas corresponden, para un quad, a 4 coordenadas (a,b,c,d) tal que a+b+c+d=1.Entonces, cualquier punto P dentro del cuádruple se puede describir mediante un cuádruple tal que:

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

En tu caso, puedes sacar 4 números aleatorios y normalizarlos para que sumen 1.Eso te dará un punto.Tenga en cuenta que la distribución de puntos NO será uniforme en ese caso.

C.También puedes, como se propone en otra parte, descomponer el quad en dos triángulos y usar el método del medio paralelogramo (es decir, como el paralelogramo pero agregas la condición u+v=1) o las coordenadas baricéntricas de los triángulos.Sin embargo, si desea una distribución uniforme, la probabilidad de tener un punto en uno de los triángulos debe ser igual al área del triángulo dividida por el área del cuadrilátero.

Otros consejos

La pregunta del OP es un poco ambigua, por lo que la pregunta que responderé es: Cómo generar un punto a partir de una distribución uniforme dentro de un cuadrilátero arbitrario , que en realidad es una generalización de Cómo generar un punto a partir de una distribución uniforme dentro de un polígono arbitrario (convexo) . La respuesta se basa en el caso de generar una muestra a partir de una distribución uniforme en un triángulo (consulte http: // mathworld .wolfram.com / TrianglePointPicking.html , que tiene una muy buena explicación).

Para lograr esto, nosotros:

  1. Triangula el polígono (es decir, genera una colección de regiones triangulares no superpuestas que cubren el polígono). Para el caso de un cuadrilátero, cree un borde cualesquiera dos vértices no adyacentes. Para otros polígonos, vea http://en.wikipedia.org/wiki/Polygon_triangulation para comenzar punto, o http://www.cgal.org/ si solo necesita una biblioteca.

    ingrese la descripción de la imagen aquí

  2. Para elegir uno de los triángulos al azar, asignemos un índice a cada triángulo (es decir, 0,1,2, ...). Para el cuadrilátero, serán 0,1. Para cada triángulo asignamos un peso igual de la siguiente manera:

    cálculo de peso

  3. Luego genera un índice aleatorio i a partir de la distribución finita sobre los índices dados sus pesos. Para el cuadrilátero, esta es una distribución de Bernoulli:

    ingrese la descripción de la imagen aquí

  4. Sean v0, v1, v2 los vértices del triángulo (representados por sus ubicaciones de puntos, de modo que v0 = (x0, y0), etc. Luego generamos dos números aleatorios a0 y a1, ambos dibujados uniformemente a partir de el intervalo [0,1]. Luego calculamos el punto aleatorio x por x = a0 (v1-v0) + a1 (v2-v0).

    ingrese la descripción de la imagen aquí

  5. Tenga en cuenta que con probabilidad 0.5, x se encuentra fuera del triángulo, sin embargo, si lo hace, se encuentra dentro del paralelogramo compuesto por la unión del triángulo con su imagen después de una rotación de pi alrededor del punto medio de (v1 , v2) (líneas discontinuas en la imagen). En ese caso, podemos generar un nuevo punto x '= v0 + R (pi) (x - v3), donde R (pi) es una rotación de pi (180 grados). El punto x 'estará dentro del triángulo.

  6. Además, tenga en cuenta que, si el cuadrilátero ya era un paralelogramo, entonces no tenemos que elegir un triángulo al azar, podemos elegir uno de manera determinista y luego elegir el punto x sin probar que está dentro de él. triángulo fuente

Suponiendo que desea una distribución uniforme: forme dos triángulos a partir de su polígono. Elija en qué triángulo generar el punto según su relación de área.

Llama a las esquinas del triángulo A, B, C, los vectores laterales AB, BC, AC y genera dos números aleatorios en [0,1] llamados u y v. Sea p = u * AB + v * AC.

Si A + p está dentro del triángulo, devuelve A + p

Si A + p está fuera del triángulo, devuelve A + AB + AC - p

(Esta es básicamente la fórmula de PierreBdR, excepto el preprocesamiento y el último paso que pliega el punto en un triángulo, para que pueda manejar otras formas que no sean paralelogramos).

Su polígono es dos triángulos, entonces, ¿por qué no seleccionar uno de ellos al azar y luego encontrar un punto aleatorio en el triángulo?

Probablemente no sea la mejor solución, pero funcionaría.

Un " na & # 239; ve " el enfoque sería utilizar un algoritmo de relleno de polígono , y luego seleccionar puntos de las líneas de relleno al azar.

Muestra de código 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.

Por " general " ¿te refieres a todos los polígonos de 4 lados no paralelogramo en general o todos los polígonos posibles?

¿Qué hay de dibujar una línea aleatoria que conecta los 4 lados, p. Si tienes esto: 

.BBBB.
A    C
A    C
.DDDD.

Luego genere un punto aleatorio en un cuadrado unitario, luego marque el punto en la línea B y D en el porcentaje de distancia en el eje X. Haga lo mismo en la línea A y C utilizando el valor del eje Y.

Luego conecte el punto en la línea A a la línea C y la línea B a la línea D, el punto de intersección se usa como punto aleatorio.

No es uniforme porque los errores de redondeo ayudarán a ciertos puntos, pero deberían estar cerca si está trabajando con valores de coma flotante.

La implementación también debería ser bastante fácil, ya que ya está trabajando con polígonos. Ya debería tener un código que haga esas tareas simples.

Aquí hay un pseudocódigo rápido: 

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

}

Esto funciona para cuadriláteros convexos generales:

Puede tomar prestados algunos conceptos del Método de elementos finitos, específicamente para elementos cuadriláteros (4 lados) ( consulte la sección 16.5 aquí ). Básicamente, hay una parametrización bilineal que asigna un cuadrado en el espacio uv (para u, v \ en [-1, 1] en este caso) a su cuadrilátero que consiste en puntos p_i (para i = 1,2,3,4 ) Tenga en cuenta que en la referencia proporcionada, los parámetros se denominan \ eta y \ xi.

Receta básica:

  1. Elija un generador de números aleatorios adecuado para generar puntos bien distribuidos en un dominio 2D cuadrado
  2. Generar pares u-v aleatorios en el rango [-1, 1]
  3. Para cada par uv, el punto aleatorio correspondiente en su 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)

El único problema es que los puntos distribuidos uniformemente en el espacio u-v no producirán puntos distribuidos uniformemente en su quad (en el sentido euclidiano). Si eso es importante, puede trabajar directamente en 2D dentro del cuadro delimitador del quad y escribir una prueba de punto en quad (tal vez dividiendo el problema en dos puntos en tris) para eliminar puntos aleatorios que están fuera.

¿Es necesario que los puntos se distribuyan uniformemente, o está bien alguna distribución?

¿Puede el polígono ser cóncavo, o se garantiza que sea convexo?

Si la respuesta a las dos anteriores es no, elija dos de los vértices y elija un punto aleatorio en el segmento de línea entre ellos. Esto se limita a los segmentos de línea que conectan los vértices (es decir, MUY no uniforme); puede hacerlo un poco mejor eligiendo un tercer vértice y luego seleccionando un punto entre ese y el primer punto, aún no uniforme, pero al menos cualquier punto en el polígono es posible

Elegir un punto aleatorio en una línea entre dos puntos es fácil, solo A + p (B-A), donde A y B son los puntos y p es un número aleatorio entre 0.0 y 1.0

¿Qué tipo de distribución quieres que tengan los puntos? Si no te importa, los métodos anteriores funcionarán bien. Si desea una distribución uniforme, el siguiente procedimiento funcionará: Divida el polígono en dos triángulos, a y b. Sean A (a) y A (b) sus áreas. Muestra un punto p de la distribución uniforme en el intervalo entre 0 y A (a) + A (b). Si p & Lt; A (a), elija el triángulo a. De lo contrario, elija el triángulo b. Elija un vértice v del triángulo elegido y deje que c y d sean los vectores correspondientes a los lados del triángulo. Muestra dos números x e y de la distribución exponencial con unidad promedio. Entonces el punto (xc + yd) / (x + y) es una muestra de la distribución uniforme en el polígono.

La función MATLAB cprnd genera puntos a partir de la distribución uniforme en un politopo convexo general. Para su pregunta, un algoritmo más especializado basado en la descomposición del cuadrilátero en triángulos es más eficiente.

Para PostGIS, esto es lo que estoy usando (es posible que desee una protección para posibles bucles infinitos). Puede exportar el algoritmo a su lenguaje de programación: 

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;
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top