Generate point within bounds of rectangle that is a minimum distance but not more than max distance from a given point A

Question

I am working on a hobby project and have run into an issue that I wonder if there is a "simple" solution for.

The problem is as follows:

Assume a 2-dimensional grid with a rectangle defined by 4 points, (x0,y0) (x0,y1) (x1,y0) (x1,y1).

Assume a point A always within the bounds of the rectangle.

Generate a point B that has a Euclidean distance of at least d_min and at most d_max, that is within the bounds of x1, y1, x2, y2.

What I have tried:

So far my naive approach has been to generate a point with the correct Euclidean distance and then check if it's within the bounds. If it is not, I generate another and check, repeating until I find a result. The issue with this is that it's of course not particularly performant. I am wondering if there is a more performant solution or if there is a known algorithim that solves this issue. To help visualize the question I made a quick sketch. The gray area would be the valid area to generate point B in.

EDIT:

d_max and d_min are constants. The value of A is variable and can be anywhere within the rectangle bounds. d_max can not be said to always be less than min(x_1-A_x, y_1-A_y). In other words, the ring follows A around with the inner circle of the ring at a constant radius from A equal to d_min and the outer circle of the ring at a constant radius from A equal to d_max.

A single point B is sufficient, however it should be random within the gray area. A perfect distribution in generated locations is not necessarily required, a good approximation is sufficient.

If A is placed in the middle of the rectangle, it is guaranteed that any point within the d_min/d_max will be always within the bounds of the rectangle. I.e:

• d_max < 0.5(x_1-x_0)

• d_max < 0.5(y_1-y_0)

Answer 1

Assuming d_max<min(x_1-A_x,y_1-A_y)

You might be able to generalize the same approach by segmenting the valid regions if that is not the case.

Step 1: Generate (randomized) distance to A. Call it radius. This radius should have weights proportional to the circular segments within bound. That means you first generate a point in [0,1] with a uniformly distributed generator and map the generated point through the inverse of the CDF of radius. More on its CDF later.

Step 2: Conditionally generate angle relative to (0,1) vector with the range determined by the coordinates of A and the earlier radius.

Step 3: Convert radius and angle to Cartesian coordinates

---

The natural way for you to generate a point as described in your diagram is for the generated points to uniformly distribute over the valid region. In other words, the probability of finding a point in any sub-region should be proportional to its area.

To fulfill the above, we need to work out the cumulated distribution of radius based on A_x (x-coordinate of A), A_y, d_min and d_max, which is:

• F(r) = (area of disk from d_min to r) / (area of disk from d_min to d_max)

You need the respective areas within bounds. And you can work out the analytical expression of F(r) and then its inverse ahead of programming. (Maybe use a symbolic computational tool such as Mathematica to validate your answer. WolframAlpha is a related tool.)

With F(r) inverse, you generate a point randomly distributed on [0,1]. That will be the value of F(r) and you solve for r using the inverse we had from earlier.

And that r will be the radius.

You then find the intersects between r^2=(x_x-A_x)^2+(x_y-A_y)^2 your boundary lines respectively, which are y=0 and x=0. Those intersects would form the range for angle, which you then use a uniformly distributed random number for.

With radius and angle, you can convert to Cartesian coordinates.

This is as performant as it gets because you are not generating invalid points and discarding them with a high probability of generating invalid points. You need two random numbers per point which cannot be reduced further unless you discretize the real numbers (as represented by doubles, for example). So the only thing potentially above minimal computation is the requirements to calculate F(r) inverse and to find intersects. You do have analytical expressions for those. They probably contain sqrt. Still, that should be much faster compared to discarding points at quantity.