具有偏移孔的环形区域内的随机点

Question

具有偏移孔的环形区域内的随机点

4

首先，如果有人能给我一个“带移位孔”的正确术语，我将不胜感激，请参见下图所示的形状。

回到主要问题：我想在橙色区域中选择一个随机点，不需要均匀分布。对于通常的环形，我会在（r：R）范围内选择随机点和随机角度，然后将其转换为x，y就行了。但对于这种不寻常的形状……是否有“简单”的公式，或者应该通过对形状进行多边形逼近来处理它？

我对一般方法很感兴趣，但会欣赏您用Python、JavaScript或其他编程语言提供示例。

- Max Yari

4个回答

3

您真的需要精确取样吗？因为使用接受/拒绝算法应该可以正常工作。我假设大橙色圆位于（0,0）。

import math
import random

def sample_2_circles(xr, yr, r, R):
    """
    R - big radius
    r, xr, yr - small radius and its position
    """
    x = xr
    y = yr
    cnd = True
    while cnd:
        # sample uniformly in whole orange circle
        phi = 2.0 * math.pi * random.random()
        rad = R * math.sqrt(random.random())
        x = rad * math.cos(phi)
        y = rad * math.sin(phi)

        # check condition - if True we continue in the loop with sampling
        cnd = ( (x-xr)**2 + (y-yr)**2 < r*r )

    return (x,y)

- Severin Pappadeux

我不能说我“需要”它，但肯定更喜欢它，因为在内圆的大小接近外圆的情况下，这个循环可能会运行大量迭代（缓慢，会使一切都卡住），直到最终在可接受的点上跌倒。 - Max Yari

@MaxYari，没错，一旦内部循环增加，效率就会降低。另一方面，任何类型的均匀/非均匀采样依赖性都很容易实现和证明。 - Severin Pappadeux

2

由于您没有提供自己的方程式、算法或代码，而只是给出了一个中心对齐圆形的算法概述，因此我在这里也只会给出更通用情况下的算法概述。

较小的圆是较大的圆在相似变换下的图像。即，在较大的圆中有一个固定点和一个比例（它是R/r，大于一），你可以取小圆上的任意点，检查从固定点到该点的向量，并将该向量乘以该比例，然后当它从固定点开始时，向量的末尾是较大圆上的一个点。该变换是一对一的。

因此，您可以选择小圆上的一个随机点（在0到两倍pi之间随机选择角度），并且在1和圆之间的比例关系R/r之间随机选择一个比率。然后使用与随机比率相同的固定点的相似变换来获得已选择的小圆上的点的图像点。这是你所需区域的一个随机点。

这种方法非常简单。事实上，最难的数学部分是找到相似变换的固定点。但是，考虑到两个圆的中心和半径，这很容易。提示：变换将较小圆的中心点变换到较大圆的中心点。

如果需要更多细节，请询问。我的算法不能产生均匀分布：点将在圆相互靠近的地方更紧密地包裹，而在圆相互远离的地方则不那么紧密地包裹。

以下是一些未经测试的Python 3.6.2代码，用于执行上述操作。我会在能够时测试它并显示其图形。

import math
import random

def rand_pt_between_circles(x_inner, 
                            y_inner,
                            r_inner, 
                            x_outer,
                            y_outer,
                            r_outer):
    """Return a random floating-point 2D point located between the 
    inner and the outer circles given by their center coordinates and 
    radii. No error checking is done on the parameters."""
    # Find the fixed point of the similarity transformation from the
    #   inner circle to the outer circle.
    x_fixed = x_inner - (x_outer - x_inner) / (r_outer - r_inner) * r_inner 
    y_fixed = y_inner - (y_outer - y_inner) / (r_outer - r_inner) * r_inner 

    # Find a a random transformation ratio between 1 and r_outer / r_inner
    #   and a random point on the inner circle
    ratio = 1 + (r_outer - r_inner) * random.random()
    theta = 2 * math.pi * random.random()
    x_start = x_inner + r_inner * math.cos(theta)
    y_start = y_inner + r_inner * math.sin(theta)

    # Apply the similarity transformation to the random point.
    x_result = x_fixed + (x_start - x_fixed) * ratio
    y_result = y_fixed + (y_start - y_fixed) * ratio

    return x_result, y_result

- Rory Daulton

说实话，我真的很困惑。什么是比例系数？R/r？这个在1和比例之间的随机数有什么用？我想我明天需要清醒地思考一下。不过，如果有任何适合新手的额外提示，我会非常感激。 - Max Yari

@MaxYari：在你发表评论之前，我改进了关于总比例R/r的解释，所以我不能为那个快速回复负责。但是，在你的评论后，我改进了有关随机比率的解释。现在清楚了吗？ - Rory Daulton

你能和我一起走一遍吗？例如 R = 6，r = 2; 1. 我选择一个随机角度（a）和沿着 r 的一个点（l）：a = Pi，l = 1; 2. 接下来是一个随机比率：rt = 2; 3. ??? - Max Yari

@MaxYari：请查看我回答中添加的代码。我现在太忙了，无法测试代码或包含图形。 - Rory Daulton

使用以下参数运行程序：x_inner = 10，y_inner = 10，r_inner = 10，x_outer = 0，y_outer = 0，r_outer = 50; 结果得到的 x_result 和 y_result 超过了50的范围（甚至达到200+）。 - Max Yari

显示剩余2条评论

1

Severin Pappadeux所描述的接受/拒绝方法可能是最简单的方法。

对于直接的方法，您还可以使用极坐标，以孔的中心为极点。

外圆的极坐标方程（Θ，σ）（抱歉，没有ρ）将是

(σ cosΘ - xc)² + (σ sinΘ - yc)² = σ² - 2(cosΘ xc + sinΘ yc)σ + xc² + yc² = R²

这是一个关于 σ 的二次方程，可以轻松用 Θ 求解。然后您可以在 0, 2π 中绘制一个角，并在 r 和 σ 之间绘制半径。

但是这样做并不能得到均匀分布，因为 σ 的范围是 Θ 的函数，并且存在极向偏差。通过计算适当的转移函数可能可以解决这个问题，但这需要一些技术支持，可能无法在分析上处理。

- user1196549

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Dickinson · Accepted Answer

这里有一个简单的方法，可以得到均匀分布而不需要重新抽样。

为了简化问题，假设外边界圆（半径为r_outer）的中心位于(0, 0)，内圆边界（半径为r_inner）的中心位于(x_inner, y_inner)。

用D表示外部圆盘，H1表示平面上的非中心内孔，H2表示半径为r_inner、以(0, 0)为中心的中心圆盘。

现在假设我们忽略内圆不是中心的事实，而是从D-H2中取样（这很容易均匀地进行）。然后我们犯了两个错误：

有一个区域A=H1-H2，我们可能会从中取样，但这些样本不应该在结果中。
有一个区域B=H2-H1，我们永远不会从中取样，尽管我们应该取样。

但是这里有一件事情：区域A和B是全等的：给定平面上的任何点(x, y)，如果且仅当(x_inner-x, y_inner-y)在H1中时，(x, y)在H2中。因此，如果(x, y)在A中，则(x_inner-x, y_inner-y)在B中。映射(x, y) -> (x_inner-x, y_inner-y)表示围绕点(0.5*x_inner, 0.5*y_inner)旋转180度。所以有一个简单的技巧：从D-H2生成，如果我们最终得到了H1-H2中的某些东西，则旋转以获取相应的H2-H1点。

以下是代码。请注意使用均匀分布的平方根来选择半径：这是一种标准技巧。例如，请参见这篇文章。

import math
import random

def sample(r_outer, r_inner, x_inner, y_inner):
    """
    Sample uniformly from (x, y) satisfiying:

       x**2 + y**2 <= r_outer**2

       (x-x_inner)**2 + (y-y_inner)**2 > r_inner**2

    Assumes that the inner circle lies inside the outer circle;
    i.e., that hypot(x_inner, y_inner) <= r_outer - r_inner.
    """
    # Sample from a normal annulus with radii r_inner and r_outer.
    rad = math.sqrt(random.uniform(r_inner**2, r_outer**2))
    angle = random.uniform(-math.pi, math.pi)
    x, y = rad*math.cos(angle),rad*math.sin(angle)

    # If we're inside the forbidden hole, reflect.
    if math.hypot(x - x_inner, y - y_inner) < r_inner:
        x, y = x_inner - x, y_inner - y

    return x, y

以下是生成示例图的代码：

import matplotlib.pyplot as plt
samples = [sample(5, 2, 1.0, 2.0) for _ in range(10000)]
xs, ys = zip(*samples)

plt.scatter(xs, ys, s=0.1)
plt.axis("equal")
plt.show()