算法：计算椭圆内的伪随机点

Question

对于我正在制作的简单粒子系统，我需要给定一个具有宽度和高度的椭圆，计算位于该椭圆内的随机点 X, Y。

现在我的数学不是最好的，所以我想在这里问是否有人可以给我指出正确的方向。

也许正确的方法是在宽度范围内选择一个随机浮点，将其作为 X 并从中计算 Y 值？

Answer 1

1. 在半径为 1 的圆内生成一个随机点。这可以通过在区间 [0, 2*pi) 中取随机角度 phi 和区间[0, 1)内的随机值rho并计算

   <前><代码>x = sqrt(rho) * cos(phi)
   y = sqrt(rho) * sin(phi)

   公式中的平方根确保圆内均匀分布。

2. 将x和y缩放到椭圆的尺寸

   <前><代码>x = x * 宽度/2.0
   y = y * 高度/2.0

Answer 2

使用拒绝采样：在椭圆周围的矩形中选择一个随机点。通过检查 (x-x0)^2/a^2+(y-y0)^2/b^2-1 的符号来测试该点是否在椭圆内部。如果该点不在内部，则重复此操作。 （这假设椭圆与坐标轴对齐。类似的解决方案适用于一般情况，但当然更复杂。）

Answer 3

通过仔细考虑极坐标形式的定义，也可以在不使用拒绝采样的情况下生成椭圆内的点。来自 wikipedia 椭圆的极坐标形式由

直观上一般来说，半径越大，我们应该更频繁地采样极角θ。用更数学的方式来说，随机变量 θ 的 PDF 应该是 p(θ) dθ = dA / A，其中 dA 是角度 θ 且宽度为 dθ 的单个线段的面积。使用极角面积方程 dA = 1/2 r² dθ 且椭圆面积为 π ab，则 PDF 变为

要从此 PDF 中随机采样，请直接方法是逆CDF技术。这需要计算累积密度函数（CDF），然后对该函数求逆。使用 Wolfram Alpha 获得不定积分，然后对其求逆，得到

其中 u 在 0 和 1 之间运行。因此，要采样随机角度 θ，只需生成一个在 0 和 1 之间的均匀随机数 u，并将其代入该方程以获得逆 CDF。

要获得随机半径，可以使用适用于圆的相同技术（参见示例 在圆内生成一个随机点（均匀））。

以下是实现此算法的一些示例 Python 代码：

import numpy
import matplotlib.pyplot as plt
import random

# Returns theta in [-pi/2, 3pi/2]
def generate_theta(a, b):
    u = random.random() / 4.0
    theta = numpy.arctan(b/a * numpy.tan(2*numpy.pi*u))

    v = random.random()
    if v < 0.25:
        return theta
    elif v < 0.5:
        return numpy.pi - theta
    elif v < 0.75:
        return numpy.pi + theta
    else:
        return -theta

def radius(a, b, theta):
    return a * b / numpy.sqrt((b*numpy.cos(theta))**2 + (a*numpy.sin(theta))**2)

def random_point(a, b):
    random_theta = generate_theta(a, b)
    max_radius = radius(a, b, random_theta)
    random_radius = max_radius * numpy.sqrt(random.random())

    return numpy.array([
        random_radius * numpy.cos(random_theta),
        random_radius * numpy.sin(random_theta)
    ])

a = 2
b = 1

points = numpy.array([random_point(a, b) for _ in range(2000)])

plt.scatter(points[:,0], points[:,1])
plt.show()

Answer 4

我知道这是一个老问题，但我认为现有的答案都不够好。

我正在寻找完全相同问题的解决方案，并在 Google 的指导下找到了这里，发现所有现有答案都不是我想要的，所以我完全自己实现了自己的解决方案，使用此处找到的信息： https://en.wikipedia.org/wiki/Ellipse

那么椭圆上的任何点都必须满足该方程，如何在椭圆内制作一个点？

只需用 0 和 1 之间的两个随机数缩放 a 和 b 即可。

我将在这里发布我的代码，我只是想提供帮助。

import math
import matplotlib.pyplot as plt
import random
from matplotlib.patches import Ellipse

a = 4
b = a*math.tan(math.radians((random.random()+0.5)/2*45))

def random_point(a, b):
    d = math.radians(random.random()*360)
    return (a * math.cos(d) * random.random(), b * math.sin(d) * random.random())

points = [random_point(a, b) for i in range(360)]

x, y = zip(*points)

fig = plt.figure(frameon=False)
ax = fig.add_subplot(111)
ax.set_axis_off()
ax.add_patch(Ellipse((0, 0), 2*a, 2*b, edgecolor='k', fc='None', lw=2))
ax.scatter(x, y)
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
plt.axis('scaled')
plt.box(False)
ax = plt.gca()
ax.set_xlim([-a, a])
ax.set_ylim([-b, b])
plt.set_cmap('rainbow')
plt.show()