在圆内生成一个随机点（统一） [英] Generate a random point within a circle (uniformly)

问题描述

我需要在半径为圆的圆圈内产生一个均匀的随机点。

我知道，只要选取一个均匀的随机角度在区间[0 ...2π）和区间内的均匀随机半径（0 ... R ）中，最终会有更多的点朝向中心，因为对于给定的两个半径，

我在这个在这里，但我不明白他的推理。我想这是正确的，但我真的很想从他从哪里得到（2 / R ² ）× r 以及他如何得出最终解决方案。 可以一次又一次地在 R &次; R 方块内产生一个随机点，直到我在圆圈内找到一个点。这种方法有一个显而易见的缺点，即它不提供终止保证（即使它很可能不会终止）。 方案

让我们来看看阿基米德会有的。

我们如何在三角形ABC中生成一个点，其中| AB | = | BC |？让我们通过扩展到平行四边形ABCD来简化它。在ABCD中统一生成点很容易。我们在AB上一致地选择一个随机点X，在BC上选择Y，并选择Z，使得XBYZ是平行四边形。为了在原始三角形中获得统一选择的点，我们只需将出现在ADC中的任意点折回到沿着AC的ABC。现在考虑一个圆。在极限中，我们可以将它看作无限多的等角三角形ABC，其中B在原点，圆周上的A和C彼此消失得很近。我们可以简单地通过选择一个角度θ来挑选其中一个三角形。所以我们现在需要通过挑选条子ABC中的一个点来从中心产生一个距离。再次延伸到ABCD，其中D现在是圆心的两倍半径。

使用上述方法在ABCD中选取一个随机点很容易。在AB上选择一个随机点。在BC上统一挑选一个随机点。 IE浏览器。在[0，R]上统一挑选一对随机数x和y，给出距中心的距离。我们的三角形是一条很薄的条子，所以AB和BC基本平行。所以Z点只是距离原点的距离x + y。如果x + y> R，我们将向下折叠。

以下是R = 1的完整算法。我希望你同意这很简单。它使用了trig，但你可以保证它需要多长时间，以及它需要多少次 random（）调用，这与排除抽样不同。

  t = 2 * pi * random（）
u = random（）+ random（）
r = if u> 1 then 2-u else u 
 [r * cos（t），r * sin（t）] 
  

  f []：= Block [{u，t，r}，$ b在Mathematica中。 $ bu = Random [] + Random []; 
 t =随机[] 2 Pi; 
 r = If [u> 1，2  -  u，u]; 
 {r Cos [t]，r Sin [t]} 
] 
 
 ListPlot [Table [f []，{10000}]，AspectRatio  - >自动] 
  

I need to generate a uniformly random point within a circle of radius R.

I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... R) I would end up with more points towards the center, since for two given radii, the points in the smaller radius will be closer to each other than for the points in the larger radius.

I found a blog entry on this over here but I don't understand his reasoning. I suppose it is correct, but I would really like to understand from where he gets (2/R²)×r and how he derives the final solution.

---

Regarding rejection sampling: I could generate a random point within the R×R square over and over again until I get one within the circle. This approach has the obvious draw-back that it doesn't provide a guarantee for termination (even though it is highly unlikely that it goes on for long).

解决方案

Let's approach this like Archimedes would have.

How can we generate a point uniformly in a triangle ABC, where |AB|=|BC|? Let's make this easier by extending to a parallelogram ABCD. It's easy to generate points uniformly in ABCD. We uniformly pick a random point X on AB and Y on BC and choose Z such that XBYZ is a parallelogram. To get a uniformly chosen point in the original triangle we just fold any points that appear in ADC back down to ABC along AC.

Now consider a circle. In the limit we can think of it as infinitely many isoceles triangles ABC with B at the origin and A and C on the circumference vanishingly close to each other. We can pick one of these triangles simply by picking an angle theta. So we now need to generate a distance from the center by picking a point in the sliver ABC. Again, extend to ABCD, where D is now twice the radius from the circle center.

Picking a random point in ABCD is easy using the above method. Pick a random point on AB. Uniformly pick a random point on BC. Ie. pick a pair of random numbers x and y uniformly on [0,R] giving distances from the center. Our triangle is a thin sliver so AB and BC are essentially parallel. So the point Z is simply a distance x+y from the origin. If x+y>R we fold back down.

Here's the complete algorithm for R=1. I hope you agree it's pretty simple. It uses trig, but you can give a guarantee on how long it'll take, and how many random() calls it needs, unlike rejection sampling.

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

Here it is in Mathematica.

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]

这篇关于在圆内生成一个随机点（统一）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！