我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
我需要在半径为R的圆内生成一个均匀随机点。
我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
这可能会帮助那些对选择速度算法感兴趣的人;最快的方法是(可能?)拒绝抽样。
只需在单位正方形内生成一个点,并拒绝它,直到它在圆内。如(伪代码),
def sample(r=1):
while True:
x = random(-1, 1)
y = random(-1, 1)
if x*x + y*y <= 1:
return (x, y) * r
虽然有时它可能运行不止一次或两次(而且它不是常量时间,也不适合并行执行),但它要快得多,因为它不使用像sin或cos这样复杂的公式。
其他回答
半径和“靠近”该半径的点的数量之间存在线性关系,因此他需要使用半径分布,这也使得半径r附近的数据点的数量与r成正比。
你也可以用你的直觉。
圆的面积是*r^2
为r = 1
得到的面积是。让我们假设我们有某种函数f,它将N=10个点均匀分布在一个圆内。这个比值是10 /
现在我们把面积和点数翻倍
对于r=2和N=20
面积是4,比值是20/4或10/2。半径越大,比值就越小,因为它的增长是二次的,N是线性的。
为了解决这个问题,我们可以说
x = r^2
sqrt(x) = r
如果在极坐标下生成一个向量
length = random_0_1();
angle = random_0_2pi();
更多的点会落在中心周围。
length = sqrt(random_0_1());
angle = random_0_2pi();
长度不再是均匀分布的,但是向量现在是均匀分布的。
Java解决方案和分发示例(2000分)
public void getRandomPointInCircle() {
double t = 2 * Math.PI * Math.random();
double r = Math.sqrt(Math.random());
double x = r * Math.cos(t);
double y = r * Math.sin(t);
System.out.println(x);
System.out.println(y);
}
基于以前的解决方案https://stackoverflow.com/a/5838055/5224246从@sigfpe
设ρ(半径)和φ(方位角)是两个随机变量,对应于圆内任意一点的极坐标。如果这些点是均匀分布的,那么ρ和φ的分布函数是什么?
对于任意r: 0 < r < r,半径坐标ρ小于r的概率为
P[ρ < r] = P[点在半径r的圆内]= S1 / S0 =(r/ r)2
其中S1和S0分别是半径为r和r的圆的面积。 因此,CDF可表示为:
0 if r<=0
CDF = (r/R)**2 if 0 < r <= R
1 if r > R
和PDF格式:
PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).
请注意,对于R=1随机变量根号(X),其中X在[0,1]上是一致的,有这个确切的CDF(因为P[根号(X) < y] = P[X < y**2] = y**2对于0 < y <= 1)。
φ在0 ~ 2*π范围内分布明显均匀。现在你可以创建随机极坐标,并使用三角方程将其转换为笛卡尔坐标:
x = ρ * cos(φ)
y = ρ * sin(φ)
忍不住要发布R=1的python代码。
from matplotlib import pyplot as plt
import numpy as np
rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)
x = rho * np.cos(phi)
y = rho * np.sin(phi)
plt.scatter(x, y, s = 4)
你会得到
这里有一个快速而简单的解决方案。
在(0,1)范围内选择两个随机数,即a和b。如果b < a,则交换它们。你的观点是(b * R * cos(2 *π* a / b), b * R * sin(2 *π* a / b))。
您可以这样考虑这个解决方案。如果你把圆切开,然后把它拉直,你会得到一个直角三角形。把这个三角形缩小,你会得到一个从(0,0)到(1,0)到(1,1)再回到(0,0)的三角形,所有这些变换都会均匀地改变密度。你所做的就是在三角形中随机取一个点然后反过来得到圆中的一个点。