# Efficiently generate a random position inside an outer rectangle but outside an inner rectangle

It should be a uniform distribution (ie: every point is equally as likely). I also don't want to use the simple solution of: "in a loop check to see if the current generated point is within the inner rectangle, and if so, try again". Here's my best solution so far. Is there any way to optimize it further? Or improve its correctness / efficiency / readability / etc?

function getRandomPoint(x, y, width, height) {
return {
x: Math.random() * width + x,
y: Math.random() * height + y
};
}

function randomPointInOuterExcludingInner(oX, oY, oW, oH, iX, iY, iW, iH) {
const iXW = iX + iW;
const iYH = iY + iH;

const leftWidth = iX - oX;
const rightWidth = oX + oW - iXW;
const topHeight = iY - oY;
const bottomHeight = oY + oH - iYH;

const leftArea = leftWidth * oH;
const rightArea = rightWidth * oH;
const topArea = iW * topHeight;
const bottomArea = iW * bottomHeight;

const totalArea = leftArea + rightArea + topArea + bottomArea;
const rand = Math.random() * totalArea;

if (rand < leftArea) {
return getRandomPoint(oX, oY, leftWidth, oH);
} else if (rand < leftArea + rightArea) {
return getRandomPoint(iXW, oY, rightWidth, oH);
} else if (rand < leftArea + rightArea + topArea) {
return getRandomPoint(iX, oY, iW, topHeight);
} else {
return getRandomPoint(iX, iYH, iW, bottomHeight);
}
}

const ctx = document.querySelector("canvas").getContext("2d");

const playerSquare = 100;
const outerX = 0;
const outerY = 0;
const outerW = 600;
const outerH = 600;
const innerX = 300 - playerSquare;
const innerY = 300 - playerSquare + 100;
const innerW = playerSquare * 2;
const innerH = playerSquare * 2;

ctx.rect(innerX, innerY, innerW, innerH);
ctx.stroke();

ctx.fillStyle = "blue";

for (let i = 0; i < 5000; i++) {
const pos = randomPointInOuterExcludingInner(outerX, outerY, outerW, outerH, innerX, innerY, innerW, innerH);

ctx.beginPath();
ctx.arc(pos.x, pos.y, 4, 0, 2 * Math.PI);
ctx.fill();
}
<canvas width="600" height="600"></canvas>

• Was there a goal to produce a set number of random points as efficiently as possible or was the goal to produce an algorithm that yields a single point as efficiently as possible? Question alludes to the latter. Commented Jul 22 at 6:09
• First, I'd move your const math calculations outside of the for loop. It's the same calculations 5k times. The following can be done with the rest of the const declarations outside of the randomPointInOuterExcludingInner and outside of the for loop
– Mike
Commented Jul 23 at 5:47

# implicit assumption

don't want to use [rejection sampling].

The source code and Review Context left it implicit that we're concerned about being frequently called with a "big" inner rectangle and "skinny" borders. It would be helpful to future maintenance engineers if you add an explicit // comment to that effect.

# abstraction

function getRandomPoint(x, y, width, height) {
...

function randomPointInOuterExcludingInner(oX, oY, oW, oH, iX, iY, iW, iH) {
...


That's a lot of args. For the first function I kind of want to see (point, size) coming in. I mean, after all, it does return a point. And for the second I'd like to see that twice, or perhaps (rect1, rect2). That said, if we're going to have eight parameters, the names are all very nice and clear, thank you.

Consider making this a problem which is just about the inner rectangle. That is, caller scales outer to be the unit square and so scales inner to fit within that. Then we need an affine transform when reporting the result. Or maybe preserve the current signature, let the library code do a change of coordinate system, call a simple helper, and then transform to report the answer.

While we're at it, we don't even need (rect2Point, rect2Size) input arguments. We can simplify it further, down to rect2Size, where we conventionally take rect2Point to be the origin of the unit square. Now we need only worry about an "L" shape rather than a full "frame".

# pre-conditions

We assume the widths and heights are non-negative. And the {outer, inner} names suggest some additional numeric relationships. The OP code doesn't test such things during a production run, and that is Fine.

Consider adding a debug flag, which performs careful checks.

Using higher level abstractions, such as rect, would make it easier to get the details right, as worrying about such Class Invariants is now the problem of some different piece of code.

# picture

  const iXW = iX + iW;
const iYH = iY + iH;


These are "ok" identifiers, I get what you're shooting for. But they're not exactly intuitive. I feel it would be better to include a .PNG image in a ReadMe.md, or even ASCII art in the source code, to offer a picture to the Gentle Reader. And then we might talk about labeled point "C" or "D" quite compactly.

One of the cognitive tasks you're asking the reader to do is to visualize which of these "natural" geometric decompositions you arbitrarily chose:

1. four "similar" size frame rectangles, clockwise from origin
2. four "similar" size frame rectangles, counterclockwise from origin
3. "big" vertical rectangles
4. "big" horizontal rectangles

Smart people participate on this SE site, and yet we've already seen that at least one such person didn't quite see the decomposition in the way you were seeing it. Independent of whether the OP code is Correct (it is!), this suggests that it is not yet doing an adequate job of quickly and clearly communicating the technical ideas you wish to convey. Using a picture and simpler terminology would help.

# identifiers

  const leftArea = ...
const rightArea = ...
const topArea = ...
const bottomArea = ...
const totalArea = leftArea + rightArea + topArea + bottomArea;


These are beautiful identifiers and I thank you for them. It is immediately apparent what's going on. (We could delete a pair of areas with the transform suggested above.)

  const rand = Math.random() * totalArea;


OTOH this is just kind of a lazy identifier. Sure, it's random, but what does it mean? What it is seems to be a randArea; what it does seems to be a regionSelector.

# caching

There's a bunch of temp variables here. I don't know what your calling pattern is. But if you often call in with the identical eight inputs, as we see in the example code, then caching the areas and other temp vars in a rect or rectPair datastructure might be winning.

For the very specific situation we see in the example caller, it suggests passing in a ninth numPoints parameter of 5000, and getting back a vector with thousands of random points which caller would then plot. Then we simply have some hoisting to do, which is no trouble for a good JIT'ing compiler with the code as-is. Or give it some help by computing temps prior to the result loop.

At least some random libraries (perhaps not the one used here) perform substantially better when you request a few thousand random numbers in a single call, rather than making thousands of calls.

This codebase accomplishes its design goals.

I would be willing to delegate or accept maintenance tasks on it.

• Thanks for the reply but I wasn't really looking for advice on variable names. It's appreciated, but I'm almost entirely concerned with the actual algorithm itself, and whether there is a way to make it more efficient, concise, correct, etc. Commented May 25 at 20:59

I cannot find a superior algorithm than the one you have adopted to calculate this any faster. Essentially my idea was the same as yours:

• Identify four regions around the hole.
• Caluclate the area of each region and order them by size (largest first).
• Choose a Random Variable in uniform [0,1].
• Find which region the RV belongs to (by size comparisons) checking largest first to maximise short circuiting.
• Find a random point in that region with usual uniform RV choosing.

This is essentially what you have done. Besides the well posted comment about not repeating constants calculation I can't see anything more to do.

The getRandomPoint does an unnecessary random. You could just adjust and pass your original random value into it and calculate the location. I.e. your first random value is a unique location in the area. You use that value to determine which of the four subareas it's in. Great. You can use the same value to determine where in the area it is supposed to be.

function locateInSubArea(randomValue, width, leftStart, topStart) {
return {
x:  leftStart + randomValue % width,
y:  topStart + randomValue / width,
};
}


This saves the second random. You could go further and refactor the selection process to not use a function call at all, e.g. by moving the subareas into an array and processing them with a while loop.

Note that you have to subtract the previous areas from the random value before calling this function.