algorithm - normal - generar numeros aleatorios sin repetir en matlab

Genera 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

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 2

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, se debe mencionar que ambos enfoques previos califican como un "punto aleatorio en el perímetro", solo que con una distribución no uniforme.

Answer 3

Tu última sugerencia me parece mejor.

Mire el perímetro como una única 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 cual].

Requiere solo un azar y, por lo tanto, es relativamente barato [al azar a veces son operaciones costosas].

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

Answer 4

Aquí está mi implementación con distribución uniforme (se supone x1 <x2 y 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 5

Aquí está mi implementación en Javascript

 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 6

Imaginé que intentaría hacer esto sin ramificar, expresando coords X e Y como una función del número aleatorio que recorre el 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))]
}

Answer 7

aquí está la idea que se desarrolla en objetivo-c, parece funcionar, ¿verdad?

//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 8

Su último acercamiento es lo que habría 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.