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

Question

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.

Answer 1

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.

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 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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].