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

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

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

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

Ответ 1

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

Ответ 2

вот разворачивающая идея в objective-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;
}

Ответ 3

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

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

Ответ 4

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

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

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

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

Ответ 5

Например:

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

Ответ 6

Вот моя реализация с равномерным распределением (принимает x1 < x2 и 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)...

    }
}

Ответ 7

Здесь моя реализация в 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
                }
            }
        }

Ответ 8

Полагаю, что я попытался бы сделать это без разветвления, выражая как координаты 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))]
}