CODEWITHSUNDEEP
algorithmmathgraphics
Andy S
Andy S

Reputation: 8861

Generate a random point on a rectangle's perimeter with uniform distribution

Given any particular rectangle (x1,y1)-(x2,y2), how can I generate a random point on its perimeter?

I've come up with a few approaches, but it seems like there ought to be a pretty canonical way to do it.

First, I thought I'd generate a random point within the rectangle and clamp it to the closest side, but the distribution didn't seem uniform (points almost never fell on the shorter sides). Second, I picked a side at random and then chose a random point on that side. The code was kind of clunky and it wasn't uniform either - but in the exact opposite way (short sides had the same chance of getting points as long sides). Finally, I've been thinking about "unfolding" the rectangle into a single line and picking a random point on the line. I think that would generate a uniform distribution, but I thought I'd ask here before embarking down that road.

Upvotes: 12

Views: 6055

Answers (8)

kitschmaster
kitschmaster

Reputation: 1299

here is the unfolding idea in objective-c, seems to work, doesn't it :)

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

Upvotes: 4

noio
noio

Reputation: 5812

Figured I would try to do this without branching, expressing both X and Y coords as a function of the random number that walks the "unfolded" rectangle.

X = Blue, Y = Red

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

Upvotes: 3

OpherV
OpherV

Reputation: 6937

Here's my implementation in 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
                }
            }
        }

Upvotes: 0

scgrn
scgrn

Reputation: 86

Here is my implementation with uniform distribution (assumes x1 < x2 and 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)...

    }
}

Upvotes: 1

leonbloy
leonbloy

Reputation: 75906

For example:

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

Upvotes: 3

AakashM
AakashM

Reputation: 63338

If by 'random point on the perimeter' you do in fact mean 'point selected from a uniform random distribution over the length of the perimeter', then yes, your 'unfolding' approach is correct.

It should be mentioned however that both your previous approaches do qualify as being a 'random point on the perimeter', just with a non-uniform distribution.

Upvotes: 3

amit
amit

Reputation: 178451

Your last suggestion seems best to me.

Look at the perimeter as a single long line [of length 2*a + 2*b], generate a random number within it, calculate where the point is on the rectangle [assume it starts from some arbitrary point, it doesn't matter which].

It requires only one random and thus is relatively cheap [random sometimes are costly operations].

It is also uniform, and trivial to prove it, there is an even chance the random will get you to each point [assuming the random function is uniform, of course].

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234795

Your last approach is what I would have recommended just from reading your title. Go with that. Your second approach (pick a side at random) would work if you picked a side with probability proportional to the side length.

Upvotes: 14

Related Questions