Generar un punto aleatorio en el perímetro de un rectángulo con distribución uniforme

Question

Dado un rectángulo particular (x1, y1) - (x2, y2), ¿cómo puedo generar un punto aleatorio en su perímetro?

He llegado a algunos enfoques, pero parece que debería haber una manera bastante canónica de hacerlo.

Primero, pensé que generaría un punto aleatorio dentro del rectángulo y lo sujetaría al lado más cercano, pero la distribución no parecía uniforme (los puntos casi nunca caían en los lados más cortos). Segundo, escogí un lado al azar y luego elegí un punto al azar en ese lado. El código era un poco torpe y tampoco era uniforme, pero exactamente de la manera opuesta (los lados cortos tenían la misma posibilidad de obtener puntos como lados largos). Finalmente, he estado pensando en "desplegar" el rectángulo en una sola línea y elegir un punto al azar en la línea. Creo que eso generaría una distribución uniforme, pero pensé que podría preguntar aquí antes de embarcarme en ese camino.

Answer 1

Su último enfoque es el que le hubiera recomendado solo leyendo su título. Ve con eso. Su segundo enfoque (escoger un lado al azar) funcionaría si eligiera un lado con probabilidad proporcional a la longitud del lado.

Answer 2

Su última sugerencia me parece mejor.

Mire el perímetro como una sola línea larga [de longitud 2*a + 2*b], genere un número aleatorio dentro de él, calcule dónde está el punto en el rectángulo [suponga que comienza desde un punto arbitrario, no importa cuál] .

Requiere solo un elemento aleatorio y, por lo tanto, es relativamente económico [las operaciones aleatorias a veces son costosas].

También es uniforme, y trivial para demostrarlo, existe la posibilidad de que el azar te lleve a cada punto [suponiendo que la función aleatoria es uniforme, por supuesto].

Answer 3

Si por 'punto aleatorio en el perímetro' de hecho significa 'punto seleccionado de una distribución aleatoria uniforme a lo largo del perímetro', entonces sí, su enfoque de 'despliegue' es correcto.

Sin embargo, debe mencionarse que sus dos enfoques anteriores califican como como un "punto aleatorio en el perímetro", solo que con una distribución no uniforme.

Answer 4

Por ejemplo:

static Random random = new Random(); 

/** returns a point (x,y) uniformly distributed 
    * in the border of the rectangle 0<=x<=a, 0<=y<=b 
    */ 
public static Point2D.Double randomRect(double a, double b) { 
    double x = random.nextDouble() * (2 * a + 2 * b); 
    if (x < a) 
     return new Point2D.Double(x, 0); 
    x -= a; 
    if (x < b) 
     return new Point2D.Double(a, x); 
    x -= b; 
    if (x < a) 
     return new Point2D.Double(x, b); 
    else 
     return new Point2D.Double(0, x-a); 
} 

Answer 5

aquí es la idea que se desarrolla en Objective-C, parece que funciona, no se :)

//randomness macro 
#define frandom (float)arc4random()/UINT64_C(0x100000000) 
#define frandom_range(low,high) ((high-low)*frandom)+low 

//this will pick a random point on the rect edge 
- (CGPoint)pickPointOnRectEdge:(CGRect)edge { 
    CGPoint pick = CGPointMake(edge.origin.x, edge.origin.y); 
    CGFloat a = edge.size.height; 
    CGFloat b = edge.size.width; 
    CGFloat edgeLength = 2*a + 2*b; 

    float randomEdgeLength = frandom_range(0.0f, (float)edgeLength); 

    //going from bottom left counter-clockwise 
    if (randomEdgeLength<a) { 
    //left side a1 
    pick = CGPointMake(edge.origin.x, edge.origin.y + a); 
    } else if (randomEdgeLength < a+b) { 
    //top side b1 
    pick = CGPointMake(edge.origin.x + randomEdgeLength - a, edge.origin.y + edge.size.height); 
    } else if (randomEdgeLength < (a + b) + a) { 
    //right side a2 
    pick = CGPointMake(edge.origin.x + edge.size.width, edge.origin.y + randomEdgeLength - (a+b)); 
    } else { 
    //bottom side b2 
    pick = CGPointMake(edge.origin.x + randomEdgeLength - (a + b + a), edge.origin.y); 
    } 
    return pick; 
} 

Answer 6

Aquí está mi aplicación con una distribución uniforme (asume x1 x2 < e y1 y2 <):

void randomPointsOnPerimeter(int x1, int y1, int x2, int y2) { 
    int width = abs(x2 - x1); 
    int height = abs(y2 - y1); 
    int perimeter = (width * 2) + (height * 2); 

    // number of points proportional to perimeter 
    int n = (int)(perimeter/8.0f); 

    for (int i = 0; i < n; i++) { 
     int x, y; 
     int dist = rand() % perimeter; 

     if (dist <= width) { 
      x = (rand() % width) + x1; 
      y = y1; 
     } else if (dist <= width + height) { 
      x = x2; 
      y = (rand() % height) + y1; 
     } else if (dist <= (width * 2) + height) { 
      x = (rand() % width) + x1; 
      y = y2; 
     } else { 
      x = x1; 
      y = (rand() % height) + y1; 
     } 

     // do something with (x, y)... 

    } 
} 

Answer 7

Aquí está mi aplicación en Javascri pt

 function pickPointOnRectEdge(width,height){ 
      var randomPoint = Math.random() * (width * 2 + height * 2); 
      if (randomPoint > 0 && randomPoint < height){ 
       return { 
        x: 0, 
        y: height - randomPoint 
       } 
      } 
      else if (randomPoint > height && randomPoint < (height + width)){ 
       return { 
        x: randomPoint - height, 
        y: 0 
       } 
      } 
      else if (randomPoint > (height + width) && randomPoint < (height * 2 + width)){ 
       return { 
        x: width, 
        y: randomPoint - (width + height) 
       } 
      } 
      else { 
       return { 
        x: width - (randomPoint - (height * 2 + width)), 
        y: height 
       } 
      } 
     } 

Answer 8

pensé que sería tratar de hacer esto sin ramificación, que expresan tanto coords X e Y como una función del número aleatorio que camina del rectángulo "desplegado".

JS:

function randomOnRect() { 
    let r = Math.random(); 
    return [Math.min(1, Math.max(0, Math.abs((r * 4 - .5) % 4 - 2) - .5)), 
      Math.min(1, Math.max(0, Math.abs((r * 4 + .5) % 4 - 2) - .5))] 
}