Генерация случайной точки по периметру прямоугольника с равномерным распределением

Question

Учитывая какой-либо конкретный прямоугольник (x1, y1) - (x2, y2), как я могу создать случайную точку на его периметре?

Я придумал несколько подходов, но похоже,должен быть довольно канонический способ сделать это.

Во-первых, я подумал, что я бы сгенерировал случайную точку внутри прямоугольника и привязал ее к ближайшей стороне, но распределение не казалось равномерным (точкипочти никогда не падал на более короткие стороны).Во-вторых, я выбрал случайную сторону, а затем выбрал случайную точку на этой стороне.Код был немного неуклюжим, и он не был одинаковым - но прямо противоположным образом (короткие стороны имели такой же шанс получить очки, как и длинные).Наконец, я думал о том, чтобы «развернуть» прямоугольник в одну линию и выбрать случайную точку на линии.Я думаю, что это привело бы к равномерному распределению, но я подумал спросить здесь, прежде чем отправиться в путь.

Answer 1

Ваш последний подход - это то, что я бы порекомендовал, просто прочитав ваш заголовок. Иди с этим. Ваш второй подход (выбрать случайную сторону) сработает, если вы выбрали сторону с вероятностью, пропорциональной длине стороны.

Answer 2

вот разворачивающаяся идея в target-c, похоже, работает, не так ли:)

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

Если под «случайной точкой на периметре» вы на самом деле подразумеваете «точку, выбранную из равномерного случайного распределения по длине периметра», то да, ваш подход «разворачивания» верен.

Однако следует отметить, что оба ваших предыдущих подхода квалифицируют как «случайную точку на периметре», просто с неравномерным распределением.

Answer 4

Ваше последнее предложение кажется мне лучшим.

Посмотрите на периметр как одну длинную линию [длиной 2*a + 2*b], сгенерируйте в ней случайное число, вычислите, где находится точка на прямоугольнике [предположим, что он начинается с некоторой произвольной точки, не имеет значения, какой].

Требуется только одно случайное и, следовательно, относительно дешево [случайные иногда являются дорогостоящими операциями].

Это также равномернои тривиально, чтобы доказать это, есть равный шанс, что случайное приведет вас к каждой точке [конечно, при условии, что случайная функция равномерна].

Answer 5

Вот моя реализация с равномерным распределением (предполагается, что x1

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 6

Например:

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 7

Я хотел бы попытаться сделать это без разветвления, выражая координаты X и Y как функцию от случайного числа, которое идет вокруг "развернутого" прямоугольника.

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 8

Вот моя реализация в 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
                }
            }
        }