Random (but with constraints) generated points in 2D

I need an algorithm to generate a set of random points in 2D, with very specific constraints.

1. First of all, all points should be inside a geometric shape, that can be as simple as an ellipse or as difficult as a 2D pinwheel. I can accept a very small number of points going over the edges (see next point);
2. Attached to this shape there is a density function: points generated should be more or less dense accordingly. This allows a broader interpretation of "edges" from the previous point, since you can think of edges like an area of very low density;
3. The algortihm doesn't need to be superefficient (I don't have to call it multiple times every seconds) but can't even take days, not even minutes, to produce results. Around 30 seconds for a few thousands point is the max execution time I can allow.