CODEWITHSUNDEEP
javascriptmathrandomshapes
Rob Evans
Rob Evans

Reputation: 6978

Generate Random Points Within the Area of Two Overlapping Ellipse Shapes

Using JavaScript, PHP or pseudo-code, can someone show how to generate random points inside the area between two overlapping ellipse shapes? If you take a look at the image below, the area marked in black would be the area to fill.

If you assume that both ellipse shapes are aligned with their centre at 0, 0 and we give the inner ellipse an x-axis size of 200 and y axis of 150, the larger ellipse (the outer edge of the black area) has an x-axis size of 300 and y-axis of 250.

An ellipse shape showing the area in black to generate points inside

I know I can just take a rectangular area and generate random points then check their distance from the centre to see if they fall into the black area but I want a more sophisticated, less wasteful way to do it using some nice maths if possible!

Upvotes: 2

Views: 1441

Answers (1)

davin
davin

Reputation: 45555

It's 4am so I suggest double checking everything I write. That said, it appears the Jacobian in the transform,

x = √r * cosθ
y = √r * sinθ

is det( cosθ / 2√r, - √r * sinθ ; sinθ / 2√r, √r * cosθ ) = (cosθ)^2 / 2 + (sinθ)^2 /2 = 1/2. Which means it's constant. So any region of area A in Cartesian coordinates is mapped to a region of "deformed area" A/2 in the new coordinate system. Since there is total independence of the location of the original area, we conclude that this (and uniform stretches) must be a uniform distribution if the original one is. This means you need simply sample uniformly to match your region:

var r = 80,
    R = 120,
    _r = Math.sqrt(Math.random()*(R*R-r*r)+r*r),
    theta = Math.random()*2*Math.PI;
plot(_r*Math.cos(theta),_r*Math.sin(theta)/4);

http://jsfiddle.net/SQERh/

This differs slightly from your description, since your inner ellipse isn't a uniform stretch of the outer one, which makes a similar polar transform much more complication because the radius becomes a function of the angle.

Upvotes: 2

Related Questions