如何在一个正方形内生成一个随机点，但不在正方形内切圆内部生成？

Question

参考图片：

红色圆的半径为 r

蓝色正方形的边长为 s

目标是在蓝色区域内随机生成一个点，但不能在红色区域内生成 我已经有了解决方案，但它涉及试错，这不是我首选的方法，是否有某种数学方法来解决这个问题？

这是我的方法

设 rx 和 ry 为随机变量

rx = random number between 0 and s
ry = random number between 0 and s
while (distance(rx,ry,0,0) < r)
{
   rx = random number between 0 and s
   ry = random number between 0 and s
}
return rx ry;

- Swololol

---

这是为了地图生成而不是“数学作业”，如果我没有表述清楚，对不起，我只想得到一些伪代码来帮助我理解如何完成这个任务。 - Swololol

您需要创建一个转换函数，将正方形或圆形转换为所需的形状。这是一个基本想法。如果您使用初始圆形接近，将生成两个随机值：第一个是角度，第二个是半径。然后，您需要拉伸半径以保证最终点适合您的区域。不幸的是，您无法通过这种方式获得正常分布。 - Epsiloncool

我认为这个问题与编程有关，因为它涉及到点的计算生成。我认为除了你可能已经使用的基于拒绝的方法，没有更简单的方法了。你觉得这种方法太慢了吗？ - eigenchris

@eigenchris 是的，我注意到当（显然）使用大尺寸时它可能会变慢。 - Swololol

@eigenchris 更偏向于等概率，但任何解决方案都会受到赞赏。维度可能是任何范围。 - Swololol

Answer 1

我建议您继续使用现有的想法，这被正式称为拒绝抽样，是一种使用仅均匀随机数生成器从任意概率分布中采样的常见技术。

随着维度数量的增加，减速问题是不可避免的 - 这通常被称为维度灾难。

虽然一些人建议将最终落在圆形内的点“推”到可接受/蓝色区域内的点，但很难做到这一点而不牺牲完全均匀的概率分布。（例如，我可以将圆形内的所有点推到圆形边界上最近的点，但这会使分布变得不均匀，因为圆形边界将更经常地被采样。）

---

为了使您的代码尽可能高效，如果可能的话，您应该计算 (distance(rx,ry,0,0) 而不调用任何函数，并使用原始运算符，如 + 和 *，而不是任何库函数，如 exp(x,2)。换句话说，在 if 语句中直接使用 x*x + y*y < r2（其中 r2 = r*r; 在某个地方预定义）。

- eigenchris

---

@Teepeemm 很好的发现。假设 r 是常数，我会定义 r2 = r*r; 并使用它。 - eigenchris

Answer 2

我能看到两种可能性。如果圆比正方形小很多，那么在正方形内生成一个点，并检查它是否在圆内或圆外。如果圆占据了正方形的大部分空间，那么找到距离圆心最远的正方形角落的最大可能半径。生成一个半径，它在给定圆的外面，但不大于到最远角落的距离。同时生成一个theta值。如果生成的(r, theta)点在正方形内，则接受它。这种构造方法确保了该点在圆外。

- rossum

Answer 3

我不会讨论数学与编程的问题。对我来说，这个问题两者都有涉及。下面是我的解释。

您可以尝试将在[0,1]区间生成的点映射到蓝色区域。如果两个形状是同心圆，这应该会给出正态分布。当你有一个正方形时，越靠近对角线的点越稀疏。

这个想法是以极坐标为基础：

1.假设您的图片中心位于笛卡尔坐标系（x，y）位置（0,0）。

2.生成一个在[0,1]区间内的数字a。

3.将此数字转换为角度w = 2 * pi * a。这将是您的极角。方程y = x * tan(w)定义了一条穿过图片中心的直线。

4.现在是棘手的部分：计算允许的径向部分(rho)的极限。它必须大于圆的半径r，并且小于第3步所定义的直线截断正方形的点。

5.会有四种情况，每个正方形边界各一种。 "顶部"边缘是指w值从pi/4到3pi/4的情况；"左侧"是指w值从3pi/4到5pi/4；"底部"的w值在5pi/4到7pi/4之间；而"右侧"的w值从7pi/4到2pi和0到pi/4之间。

6.以顶部直线为例：它位于位置y = s / 2。定义在步骤3中的线与顶边相交的位置是xi tan(w)。

7.笛卡尔点(xi，s / 2)定义了rho的最大值：R = sqrt（xi ^ 2 +（s / 2）^ 2）

8.现在生成另一个在[0,1]区间内的值b

9.将此值映射到[r,R]区间：rho = r + b * R

10.最后得到您的数字X = rho * cos（w）和Y = rho * sin（w），这应该在蓝色区域内。

请注意，从第5步开始，您必须检查应考虑哪个正方形边界（哪个w值）。

如上所述，问题在于对角线比沿着主轴方向更长，导致分布更稀疏。由您来判断这是否是一个问题。请注意，映射不会将点堆积在圆边附近。同时，请自行判断方向检查是否实用（我假设正方形和圆形形状是对您真正想要的内容的粗略近似）。

- rpsml

Answer 4

尽管如@Marc所说，从技术上讲这是数学问题而非编程问题。然而，答案是生成一个随机点，然后确定从正方形中心到该点绘制的线段长度是否小于或等于圆的半径。如果是，则拒绝该点并生成另一个随机点。

- John Kuhns

---

我希望它是代码，但我更感兴趣的是是否存在数学解决方案，而不是试错拒绝方法。 - Swololol

你已经有了答案。我想不出任何种子随机数的方法，只包括圆形外部的区域。 - John Kuhns

Answer 5

你可以在[0..1]范围内生成两个数字，然后定义一个函数，将x映射到圆外的某个点，以便于确定y。

- Cecilio Pardo

Answer 6

好的，如果rx和ry不是我们要找的，为什么要拒绝它们呢？任何在[-s，s]范围内的rx都可以成为我们的选择。因此；

rx = -s + 2*s*rand();

if(rx<-R || rx>R) % if rx is outside the critical area, you are free on ry
    ry = -s + 2*s*rand();
else % if rx is critical, we are restricted about choosing ry not within [-sqrt(R^2-rx^2),sqrt(R^2-rx^2)]
{
    rand_inst = rand();
    if(rand_inst<0.5) % for the first possible interval [-s, -sqrt(R^2-rx^2)]
        ry = -s + 2*(s-sqrt(R^2-rx^2))*rand_inst;
    else % for the second possible interval [sqrt(R^2-rx^2), s]
        ry = (sqrt(R^2-rx^2) - (s-sqrt(R^2-rx^2)) ) + 2*(s-sqrt(R^2-rx^2))*rand_inst;
}

- crbah