Puntos aleatorios dentro de un paralelogramo

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 (ver http://mathworld.wolfram.com/TrianglePointPicking.html , que tiene un muy buena explicación).

Para lograr esto nosotros:

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

   

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:

   

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

   

4. Sea v0, v1, v2 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 desde el intervalo [0,1]. Luego calculamos el punto aleatorio x por x = a0 ( v1-v0) + a1 (v2-v0).

   

5. Tenga en cuenta que con probabilidad 0.5, x se encuentra fuera 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 por 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 cualquiera deterministamente, y luego elegir el punto x sin probar que está dentro de su triángulo fuente.

Suponiendo que desea una distribución uniforme: Forme dos triángulos de su polígono. Elija en qué triángulo generar el punto de acuerdo con su relación de área.

Llame a las esquinas del triángulo A, B, C, los vectores laterales AB, BC, AC y genere dos números aleatorios en [0,1] llamados u y v. Deje 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 por el preprocesamiento y el último paso que dobla el punto de nuevo en un triángulo, por lo que puede manejar otras formas que paralelogramos).

Su polígono es de dos triángulos, así que ¿por qué no seleccionar al azar uno de ellos, a continuación, encontrar un punto aleatorio en el triángulo.

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

Un enfoque algo menos "naïve" sería usar un algoritmo de relleno de polígonos , y luego seleccionar puntos de las líneas de relleno al azar.

Ejemplo 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" ¿se refiere a todos los polígonos de 4 lados no paralelogramo en general o a todos los polígonos posibles?

¿Qué tal dibujar una línea aleatoria que conecte los 4 lados, por ejemplo, si tiene 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 usando el valor del eje Y.

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

No es uniforme porque los errores de redondeo ayudarán a ciertos puntos, pero debe estar cerca si está trabajando con valores de puntos flotantes.

La implementación también debería ser bastante fácil, ya que ya está trabajando con polígonos. Ya deberías tener 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 (de 4 lados) (consulte la sección 16.5 aquí). Básicamente, hay una parametrización bilineal que asigna un cuadrado en el espacio u-v (para u, v \in [-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 llaman \eta y \ xi.

Receta básica:

1. Elija un generador de números aleatorios adecuado para generar puntos bien distribuidos en un dominio cuadrado 2D
2. Generar pares u-v aleatorios en el rango [-1, 1]
3. Para cada u-v par, el correspondiente punto al azar 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 uniformemente distribuidos en el espacio u-v no producirán puntos uniformemente distribuidos 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 los puntos aleatorios que están fuera.

¿Los puntos necesitan ser distribuidos uniformemente, o cualquier distribución está bien?

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

Si la respuesta a los dos anteriores es no, entonces elija dos vértices cualquiera 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 uniformes); puede hacerlo un poco mejor eligiendo un tercer vértice y luego eligiendo un punto entre ese y el primer punto -- todavía no es 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

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 descomponer el cuadrilátero en triángulos es más eficiente.

Para PostGIS, esto es lo que estoy usando (es posible que desee una sala 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;