Uniformly distribute n points inside an ellipse
How do you uniformly distribute n points inside an ellipse given n and its minor axis length (major axis can be assumed to be the x axis and size 1)? Or if that is impossible, how do you pick n points such that the smallest distance between any two is maximized?
Right now I am uneasy about running expensive electron repulsion simulators (in hopes that there is a better solution like the sunflower function in this question to distribute n points in a circle). n will most likely be between 10 and 100 points, but it would be nice if it worked great for all n
If the ellipse is centered at (0,0), if a=1 is the major radius, b is the minor radius, and the major axis is horizontal, then the ellipse has equation x' A x = 1 where A is the matrix
/ \
| 1 0 |
| 0 1/b² |
\ /
Now, here is a way to uniformly sample inside an ellipse with equation x' A x = r. Take the upper triangular Cholesky factor of A, say U. Here, U is simply
/ \
| 1 0 |
| 0 1/b |
\ /
Pick a point y at random, uniformly, in the circle centered at (0,0) and with radius r. Then x = U^{-1}y is a point uniformly picked at random in the ellipse.
This method works in arbitrary dimension, not only in the two-dimensional case (replacing "circle" with "hypersphere").
So, for our present case, here is the pseudo-code, assuming random() uniformly generates a number between 0 and 1:
R = sqrt(random())
theta = random() * 2 * pi
x1 = R * cos(theta)
x2 = b * R * sin(theta)
Here is a R code to generate n points:
runif_ellipse <- function(n, b){
R <- sqrt(runif(n))
theta <- runif(n) * 2*pi
cbind(R*cos(theta), b*R*sin(theta))
}
points <- runif_ellipse(n = 1000, b = 0.7)
plot(points, asp = 1, pch = 19)
