我需要在半径为R的圆内生成一个均匀随机点。
我意识到，只要在区间[0…2π)，且在区间(0…R)我最终会有更多的点指向中心，因为对于两个给定的半径，小半径内的点会比大半径内的点彼此更接近。
我在这里找到了一篇关于这个的博客文章，但我不明白他的推理。我认为这是正确的，但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。
更新:在发布这个问题7年之后，关于平方根算法背后的数学问题，我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。
当前回答
程序员解决方案:
创建一个位图(布尔值的矩阵)。你想要多大就有多大。 在位图中画一个圆。 创建一个圆的点查找表。 在这个查找表中选择一个随机索引。
const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;
bool matrix[MATRIX_SIZE][MATRIX_SIZE] = {0};
struct Point { int x; int y; };
Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];
void init()
{
int numberOfOnBits = 0;
for (int x = 0 ; x < MATRIX_SIZE ; ++x)
{
for (int y = 0 ; y < MATRIX_SIZE ; ++y)
{
if (x * x + y * y < RADIUS * RADIUS)
{
matrix[x][y] = true;
loopUpTable[numberOfOnBits].x = x;
loopUpTable[numberOfOnBits].y = y;
++numberOfOnBits;
} // if
} // for
} // for
} // ()
Point choose()
{
int randomIndex = randomInt(numberOfBits);
return loopUpTable[randomIndex];
} // ()
位图仅用于解释逻辑。这是没有位图的代码:
const int RADIUS = 64;
const int MATRIX_SIZE = RADIUS * 2;
struct Point { int x; int y; };
Point lookupTable[MATRIX_SIZE * MATRIX_SIZE];
void init()
{
int numberOfOnBits = 0;
for (int x = 0 ; x < MATRIX_SIZE ; ++x)
{
for (int y = 0 ; y < MATRIX_SIZE ; ++y)
{
if (x * x + y * y < RADIUS * RADIUS)
{
loopUpTable[numberOfOnBits].x = x;
loopUpTable[numberOfOnBits].y = y;
++numberOfOnBits;
} // if
} // for
} // for
} // ()
Point choose()
{
int randomIndex = randomInt(numberOfBits);
return loopUpTable[randomIndex];
} // ()
其他回答
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
让我们像阿基米德那样处理这个问题。
我们如何在三角形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的完整算法。我希望你同意这很简单。它使用三角函数，但您可以保证它需要多长时间，以及需要多少次random()调用，这与拒绝抽样不同。
t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]
这里是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]
我不知道这个问题是否还有新的答案，但我自己碰巧也遇到过同样的问题。我试着跟自己“讲道理”寻找解决办法，我找到了一个。这可能和一些人在这里提出的建议是一样的，但不管怎样，它是这样的:
in order for two elements of the circle's surface to be equal, assuming equal dr's, we must have dtheta1/dtheta2 = r2/r1. Writing expression of the probability for that element as P(r, theta) = P{ r1< r< r1 + dr, theta1< theta< theta + dtheta1} = f(r,theta)*dr*dtheta1, and setting the two probabilities (for r1 and r2) equal, we arrive to (assuming r and theta are independent) f(r1)/r1 = f(r2)/r2 = constant, which gives f(r) = c*r. And the rest, determining the constant c follows from the condition on f(r) being a PDF.
这样一个有趣的问题。 一个点被选择的概率随着距离轴原点的增加而降低的基本原理在上面已经解释了多次。我们通过取U[0,1]的根来解释这一点。 下面是Python 3中正r的通解。
import numpy
import math
import matplotlib.pyplot as plt
def sq_point_in_circle(r):
"""
Generate a random point in an r radius circle
centered around the start of the axis
"""
t = 2*math.pi*numpy.random.uniform()
R = (numpy.random.uniform(0,1) ** 0.5) * r
return(R*math.cos(t), R*math.sin(t))
R = 200 # Radius
N = 1000 # Samples
points = numpy.array([sq_point_in_circle(R) for i in range(N)])
plt.scatter(points[:, 0], points[:,1])
注意点密度与半径的平方反比成正比，因此不是从[0,r_max]中选择r，而是从[0,r_max^2]中选择r，然后计算你的坐标:
x = sqrt(r) * cos(angle)
y = sqrt(r) * sin(angle)
这就得到了圆盘上均匀的点分布。
http://mathworld.wolfram.com/DiskPointPicking.html
