Getting two points on the edges of a rectangle

Question

I have a rectangle and would like to:

1. Get a random point on one (any) of the sides.
2. Get a random point on one (except for the previously picked) side.

My initial approach is to create arrays for each possible side.

var arr:Array = [[{x:0,y:0},           // Top
                  {x:width,y:0}],      //
                 [{x:width,y:0},       // Right
                  {x:width,y:height}], //
                 [{x:width,y:height},  // Bottom
                  {x:0,y:height}],     //
                 [{x:0,y:height},      // Left
                  {x:0,y:0}]];         //

Then, I get the sides. rand is an instance of Rand and has the methods: .next() which provides a random number between 0 and 1 .between(x,y) which returns a random number between x and y.

var firstSide:Array = arr[rand.next() * arr.length];
var secondSide:Array;
do {
    secondSide = arr[rand.next() * arr.length];
} while(secondSide.equals(firstSide));

Finally, I calculate my points.

var pointOnFirstSide:Object = {x:rand.between(firstSide[0].x, firstSide[1].x),
                               y:rand.between(firstSide[0].y, firstSide[1].y};
var pointOnSecondSide:Object = {x:rand.between(secondSide[0].x, secondSide[1].x),
                                y:rand.between(secondSide[0].y, secondSide[1].y};

I don't think this is the most efficient way to solve this.

How would you do it?

Answer 1

jcalz already gave an excellent answer. Here is an alternate version for the variant I asked about in the comments: When you want your points uniformly chosen over two sides of the perimeter, so that if your w : h ratio was 4 : 1, the first point is four times as likely to lie on a horizontal side as a vertical one. (This means that the chance of hitting two opposite long sides is 24/45; two opposite short side, 1/45; and one of each, 20/45 -- by a simple but slightly tedious calculation.)

const rand = {
  next: () => Math. random (),
  between: (lo, hi) => lo + (hi - lo) * Math .random (),
}

const vertices = (w, h) => [ {x: 0, y: h}, {x: w, y: h}, {x: w, y: 0}, {x: 0, y: 0} ]

const edges = ([v1, v2, v3, v4]) => [ [v1, v2], [v2, v3], [v3, v4], [v4, v1] ]

const randomPoint = ([v1, v2], rand) => ({
  x: v1 .x + rand .next () * (v2 .x - v1 .x),
  y: v1 .y + rand .next () * (v2 .y - v1 .y),
})

const getIndex = (w, h, x) => x < w ? 0 : x < w + h ? 1 : x < w + h + w ? 2 : 3

const twoPoints = (w, h, rand) => {
  const es = edges (vertices (w, h) )
  const perimeter = 2 * w + 2 * h
  const r1 = rand .between (0, perimeter)
  const idx1 = getIndex (w, h, r1)
  const r2 = (
    rand. between (0, perimeter - (idx1 % 2 == 0 ? w : h)) +
      Math .ceil ((idx1 + 1) / 2) * w + Math .floor ((idx1 + 1) / 2) * h
  ) % perimeter
  const idx2 = getIndex (w, h, r2)
  return {p1: randomPoint (es [idx1], rand), p2: randomPoint (es [idx2], rand)}
}

console .log (
  // Ten random pairs on rectangle with width 5 and height 2
  Array (10) .fill () .map (() => twoPoints (5, 2, rand))
)

The only complicated bit in there is the calculation of r2. We calculate a random number between 0 and the total length of the remaining three sides, by adding all four sides together and subtracting off the length of the current side, width if idx is even, height if it's odd. Then we add it to the total length of the sides up to and including the index (where the ceil and floor calls simply count the number of horizontal and vertical sides, these values multiplied by the width and height, respectively, and added together) and finally take a floating-point modulus of the result with the perimeter. This is the same technique as in jcalz's answer, but made more complex by dealing with side lengths rather than simple counts.

I didn't make rand an instance of any class or interface, and in fact didn't do any Typescript here, but you can add that yourself easily enough.

Answer 2

Assuming we have the following interfaces and types:

interface Rand {
  next(): number;
  between(x: number, y: number): number;
}
interface Point {
  x: number;
  y: number;
}
type PointPair = readonly [Point, Point];

and taking you at your word in the comment that the procedure is: first randomly pick two sides, and then pick random points on those sides... first let's see what's involved in picking two sides at random:

  const s1 = Math.floor(rand.between(0, arr.length));
  const s2 = (Math.floor(rand.between(1, arr.length)) + s1) % arr.length; 

s1 and s2 represent the indices of arr that we are choosing. The first one chooses a whole number between 0 and one less than the length of the array. We do this by picking a real number (okay, floating point number, whatever) between 0 and the length of the array, and then taking the floor of that real number. Since the length is 4, what we are doing is picking a real number uniformly between 0 and 4. One quarter of those numbers are between 0 and 1, another quarter between 1 and 2, another quarter between 2 and 3, and the last quarter are between 3 and 4. That means you have a 25% chance of choosing each of 0, 1, 2 and 3. (The chance of choosing 4 is essentially 0, or perhaps exactly 0 if rand is implemented in the normal way which excludes the upper bound).

For s2 we now pick a number uniformly between 1 and the length of the array. In this case, we are picking 1, 2, or 3 with a 33% chance each. We add that number to s1 and then take the remainder when dividing by 4. Think of what we are doing as starting on the first side s1, and then moving either 1, 2, or 3 sides (say) clockwise to pick the next side. This completely eliminates the possibility of choosing the same side twice.

---

Now let's see what's involved in randomly picking a point on a line segment (which can be defined as a PointPair, corresponding to the two ends p1 and p2 of the line segment) given a Rand instance:

function randomPointOnSide([p1, p2]: PointPair, rand: Rand): Point {
  const frac = rand.next(); // between 0 and 1
  return { x: (p2.x - p1.x) * frac + p1.x, y: (p2.y - p1.y) * frac + p1.y };
}

Here what we do is pick a single random number frac, representing how far along the way from p1 to p2 we want to go. If frac is 0, we pick p1. If frac is 1, we pick p2. If frac is 0.5, we pick halfway between p1 and p2. The general formula for this is a linear interpolation between p1 and p2 given frac.

---

Hopefully between the two of those, you can implement the algorithm you're looking for. Good luck!

Link to code