math - 在椭圆内均匀分布 n 个点

Question

给定 n 及其短轴长度（可以假设长轴为 x 轴且大小为 1），如何在椭圆内均匀分布 n 个点？或者如果这是不可能的，你如何选择 n 个点以使任意两个点之间的最小距离最大化？

现在我对运行昂贵的电子排斥模拟器感到不安（希望有更好的解决方案，比如这个问题中的向日葵函数，将 n 个点分布在一个圆圈中）。n 很可能在 10 到 100 分之间，但如果它对所有 n 都有效，那就太好了

Answer 1

相当简单的方法：

为 D 距离近似值设置初始值，例如D=Sqrt(Pi*b/N )b 是短轴长度。

生成单元格大小为 D 的点的三角形网格（具有等边三角形以提供最密集的包装）。计算位于给定椭圆内的点数。

如果它小于 N，则减小距离 D，或增大 D。重复直到正好有 N 个点在里面。

CountInside <=> D对于固定起点，依赖是单调的，因此您可以使用二进制搜索来更快地获得结果。

边界附近可能有 2-4 个对称点的复杂情况——当它们同时向外或向内时。如果您发现这种情况，请稍微改变起点。

Answer 2

如果椭圆以 为中心(0,0)，如果a=1是大半径，b是小半径，并且长轴是水平的，则椭圆有方程x' A x = 1其中A是矩阵

 /      \
| 1  0   |
| 0 1/b² |
 \      /

现在，这是一种使用 equation 在椭圆内均匀采样的方法x' A x = r。以 的上三角 Cholesky 因子A为例U。这里，U简直

 /     \
| 1  0  |
| 0 1/b |
 \     /

y在以 为中心(0,0)并以 为半径的圆中随机均匀地选取一个点r。然后x = U^{-1}y是椭圆中均匀随机选取的一个点。

此方法适用于任意维度，不仅适用于二维情况（将“圆”替换为“超球面”）。

因此，对于我们目前的情况，这里是伪代码，假设random()统一生成一个介于 0 和 1 之间的数字：

R = sqrt(random())
theta = random() * 2 * pi
x1 = R * cos(theta)
x2 = b * R * sin(theta)

这是生成n点的R代码：

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)