将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² |
 \      /

现在，这里有一种方法可以使用等式 x' A x = r 在椭圆内均匀采样。取 A 的上三角 Cholesky 因子，比如 U。这里，U 就是

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

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

此方法适用于任意维度，不仅适用于二维情况（将 "circle" 替换为 "hypersphere"）。

因此，对于我们目前的情况，这里是伪代码，假设 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)

将n个点均匀分布在一个椭圆内

Uniformly distribute n points inside an ellipse

math

geometry

uniform-distribution