CODEWITHSUNDEEP
mathgeometryuniform-distribution
Acreol
Acreol

Reputation: 77

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

Upvotes: 1

Views: 1566

Answers (2)

Stéphane Laurent
Stéphane Laurent

Reputation: 84709

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)

enter image description here

Upvotes: 2

MBo
MBo

Reputation: 80327

Rather simple approach:

Make initial value for D distance approximation like D=Sqrt(Pi*b/N ) where b is minor axis length.

Generate triangular grid (with equilateral triangles to provide the most dense packing) of points with cell size D. Count number of points lying inside given ellipse.

If it is smaller than N, diminish distance D, of larger - increase D. Repeat until exactly N points are inside.

Dependence CountInside <=> D is monotone for fixed starting point, so you can use binary search to get result faster.

There might be complex cases with 2-4 symmetric points near the border - when they go out or inside simultaneously. If you catch this case, shift starting point a bit.

Upvotes: 1

Related Questions