Sign in to follow this  

Getting random points within an area:

This topic is 3591 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to be able to get a random point within an area defined by xmin, ymin, xmax, ymax, it's shape and the distribution of the points. Shapes -rectangle -diamond -ellipse -line (from x_min,y_min to x_max,y_max) Distribution -linear (equal chance for the entire area) -gaussian (more likly to be in the centre) -inverse gaussian(more likly around the edges) A linear rectangle is pretty straight forward(random x and random y) but I'm not sure how to get accurate but fast distributions for the other combinations?

Share this post


Link to post
Share on other sites
There are a few parts to this that are significant problems on their own...

If you have a probability distribution P(x) that's normalized for some range of x values, say x = x1 .. x2, then the integral of P(x)dx from x = x1 to x2 is 1. That is, the total probability of the chosen point being in the range x1 to x2 is 1.

To randomly pick a point in the range x1 to x2 from that probability distribution, you need to sample the inverted cumulative distribution function corresponding to P(x). This is commonly used in monte carlo simulations of physical processes (among others).

If you integrate P(x) from x1 to x, you get C(x), the cumulative distribution function. C(x1) = 0, and C(x2) = 1 due ot the normalization condition above. If you invert C(x), you get the inverted cumulative distribution function, which I'll call x = Q(c). If you randomly generate a number c between 0 and 1 with a uniform (what you called linear) distribution, and then caluclate Q(c), you'll get an x value in the range x1 to x2, which will have effectively sampled P(x).

You might want to read about monte carlo, and Quantile functions (what wikipedia seems to call the inverted cumulative distribution).

Once you've got 1D sampling on a range worked out, you can parameterize your 2D surfaces (shape) so that a pair of coordinates (a, b) that are both independently uniformly sampled in the range 0 to 1 gives you a point on the surface that's also uniformly distributed. This is a whole separate problem for complicated shapes, though is easy for lines or rectangles.

Your distributions (gaussians, uniform) are rotationally symmetric, so you can probably parameterize the non-simple ones in terms of angular coordinate (uniformly sampled) and radial coordinate, which will have to be sampled carefully to get uniform sampling across the surface. Then you can invert the radial part, find the inverse cumulative distribution function, and sample it to get a radial position...

But then it might be more difficult if you want to use a rotationally symetric distribution on a non-circular surface, as normalization will be quite tricky, and possible range of radial value will vary with angle...

You might have an easier time if you sample a 1D gaussian in two dimensions, instead of doing a true rotationally symmetric 2D gaussian distribution for the non-circular shapes.

Edit: also, integrating and inverting gaussians isn't going to be doable in closed form, so you'll have to numerically approximate that.

Another alternative is to define the probability distribution you want in terms of (x, y) on the surface. Randomly pick (using a uniform distribution) a point on the surface. Find the maximum value of the probability distribution, and randomly sample a uniform value in the range from 0 to the distribution maximum. If the randomly sampled value is larger than the probability distribution at (x, y), reject (x, y), and generate a new point on the surface, and repeat. This will require repeated iterations in some cases to get a point, particularly for very peaky distributions, but is probably a lot easier to implement. /Edit

This has gotten a bit rambly and probably hard to follow, but hopefully contains some useful thoughts and suggestions...

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
I want to be able to get a random point within an area defined by xmin, ymin, xmax, ymax, it's shape and the distribution of the points.

Shapes
-rectangle
-diamond
-ellipse
-line (from x_min,y_min to x_max,y_max)

Distribution
-linear (equal chance for the entire area)
-gaussian (more likly to be in the centre)
-inverse gaussian(more likly around the edges)

A linear rectangle is pretty straight forward(random x and random y) but I'm not sure how to get accurate but fast distributions for the other combinations?


you will need:

vector maths
euler rotation

for the line:
* calculate the length len of line L.
* Pick a random number R between 0 and len
* Calculate the direction Dn of the line by normalising the vector (Lmin - Lmax)
your random point is R * Dn.


for the ellipse:
* find the centre point.
* find a random rotation in D-1 dimensions, where D is the number of dimensions of the ellipse. This is a separate problem altogether.
* draw a line from the center, along this vector, to the edge of the ellipse.
* Draw a line between the intersection of the edge and the line, and the same line with one of the axis reversed.
* perform the line test as above.
[update]
* if you have a third dimension, draw a line at a right angle to the previous one, starting on the random point you chose, and ending at the edge of the ellipse.
* calculate a new random distance along that line, and perform the line test, you have your random point.
* if you have a forth dimension.....



for the diamond: ( I assume you mean a diamond where length AB = length BC = lenth CD = length DA)
* Calculate the angle of the bottom left corner.
* Perform the rectangle algorythm using the sides of the diamond as the parameters.
* Rotate the resulting point around the corner you used, by the angle you calculated.

Share this post


Link to post
Share on other sites
If you can't understand the math for the more complicated cases, you probably won't be able to program a solution to all the cases listed in your original post. You might want to start with something much simpler, like a picking points on a 1D range with a simple probability distribution.

The simplest case: You want a point at position x which ranges continuously between 0 and 1 in one dimension. The point should be chosen according to a uniform distribution (all possible x have equal probability). If you have a random number generating function rand() that outputs a number between 0 and 1, you can immediately generate points for this case.

If you want a more complicated probability distribution, you need to parameterize it in terms of the position. We'll call the probability distribution function P(x). P(x) gives the probability density at the position x. This is a somewhat abstract concept, as P(x) is not the probability that a chosen point will have value x. Rather, if you integrate P(x) from x1 to x2, you get the probability that a chosen point will lie between x1 and x2.

Probability distributions like P(x) should be normalized, meaning that the total probability of a point being between 0 and 1 should be 100%. Mathematically, that means that integrating P(x) from 0 to 1 with respect to x gives 1.

If you have a function P(x) defined on the range 0 to 1, you can use two methods to generate points on the range. The simpler one is the second I described earlier. Randomly pick a point y in the range 0 to 1 using a uniform distribution (which is discussed above), and calculate P(y). Then generate a random value z with a uniform distribution between 0 and the largest value your function P(x) takes for any values of x between 0 and 1 (the range on which it is defined). If this second random value z is larger than P(y), then reject y and repeat for a new value of y until you get one that isn't rejected. When you get a non-rejected y, you can use it as a random point in the range 0 to 1 that was generated according to the probability distribution P(x).

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
Can someone explain that in more simple terms? Ive got no idea how to do the maths behind that...


Do you know how to calculate a gaussian distribution? Can you do the maths to find the relative probability of a point at any given location within the shape? No? Well, this is fundamentally a maths problem, not a programming one, so...

Make sure you can at least specify the problem accurately. As speciesUnknown points out, the term "diamond" is ambiguous. And anyway, a distribution can only be linear or gaussian with respect to some variable. For the rectangle, do you want a distribution that's gaussian with respect to straight-line distance from the center, or Manhattan distance, or the maximum component of the direction vector, or something else?

I.e., say we calculate it for a rectangle that happens to be a square.


+++++++++
++++Y++++
++++ZX+++
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++


Do you want the same chance of a point at X as at Y (that would be Manhattan distance)? Or perhaps, the same chance at X as at Z (maximum component)? Or just what? Put another way: Suppose you coloured the shape according to the relative probability at each point. What kind of pattern would you expect to see in the colours - diamonds, circles, concentric rectangles? Something else?

Share this post


Link to post
Share on other sites
Hmm, its a bit complicated, UNTIL you learn the basics of what my maths is saying. Then, it all just fits into place.
I frequently advise people to learn more vector and matrix maths. when I did, it started to all come together.

Share this post


Link to post
Share on other sites
Ive done a little vector maths at school. Havn't covered matrics yet :(. I'll take a look around to see if I can find any introductory articles on those cause I realy ave no idea what they are lol...

Share this post


Link to post
Share on other sites
Couldn't you just use the random generation for a rectangle (xmin, ymin)-(xmax, ymax) and then throw away all results that are not within the required shape? Since all of the shapes (except for the line) covers at least half of the rectangle, it probably won't be a significant slowdown.

Maybe I'm missing some important mathematical concept here?

Share this post


Link to post
Share on other sites
I still need to brush on my maths lol.. The question "How do I know if a point is within an eclipse?" comes up there. Unlike a circle I can't just check the distance to the centre.

The real problem I'm having is how to get a nonuniform distibution. All the things I found on google just provide code with various copywrite notices over them :(

Share this post


Link to post
Share on other sites

This topic is 3591 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this