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?

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

Can someone explain that in more simple terms? Ive got no idea how to do the maths behind that...

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

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?

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

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?

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 :(