CODEWITHSUNDEEP
algorithm
jordan
jordan

Reputation: 187

Random point within oval with higher probability for a point closer to the centre?

I feel like the question is quite descriptive but to illustrate it in words.

Picture a radial gradient (black in centre, white on edge) I want to generate a random point that is more likely to fall in the black, less likely to fall in the grey, and even less likely to fall in the white.

Could someone point me in the right direction? I'm quite stumped :/

Upvotes: 1

Views: 137

Answers (2)

Edward Doolittle
Edward Doolittle

Reputation: 4100

If B is a matrix such that y = c + Bx is an affine transformation which maps the unit circle to your ellipse (which is what I assume you mean by an "oval"), then a probability distribution that looks something like what you seem to want is given by y ~ N(c, BB^T) where B^T is the transpose of B.

You can sample from the distribution by generating a column vector x of two normally distributed variables and applying the transformation y = c + Bx. There are many libraries for generating a pair of normally distributed variables; in Java, x0=rand.nextGaussian(); x1=rand.nextGaussian() will work.

This will occasionally generate points outside the ellipse. You can avoid that by simply rejecting such points. Just test whether x0*x0 + x1*x1 > 1 and reject if true.

One more thing: if you want "more white" near the edge of your ellipse, you can change the standard deviation of the gaussians you generate to a number less than 1:

sd = 0.5; 
do 
  x0 = sd * rand.nextGaussian(); 
  x1 = sd * rand.nextGaussian();
while (x0*x0 + x1*x1 > 1);
y0 = c0 + B[0][0] * x0 + B[0][1] * x1
y1 = c1 + B[1][0] * x0 + B[1][1] * x1

If you want "less white", set sd to some number greater than 1.

Upvotes: 1

Gene
Gene

Reputation: 46960

A way to get what you want is to generate truncated normally distributed random radii r with \sigma=1 in a range +-R and uniformly distributed random values \theta in 0..pi for the polar angle. If A and B are the major and minor axes aligned with x and y, then the points with respect to the origin are

x = r A/R cos \theta,   y = r B/R sin \theta

When you choose parameter R to be large, the values will be concentrated toward the center of the ellipse. When it's small, they'll be evenly distributed across it.

Generating pseudo random values that are truncated-normally distributed is not trivial, but not too hard either. See e.g. Chopin's paper for a good discussion. This C++ implementation looks useful.

If you don't care about all the points lying inside the ellipse, you can use the full normal distribution. The Box Muller algorithm for this is very simple to implement, and it's built into many libraries including Java's.

Upvotes: 1

Related Questions