带有移位孔的环形空间内的随机点

Question

首先，如果有人能给我一个 "annulus with a shifted hole" 的正确术语，我将不胜感激，看看我在下面的图片中到底指的是什么形状。

回到正题：我想在橙色区域随机取一个点，不需要均匀分布。对于通常的环形，我会选择 (r:R) 范围内的随机点和随机角度，然后将它们转换为 x,y 就完成了。但是对于这种不寻常的形状...是否有 "simple" 公式，或者我应该通过对形状进行某种多边形近似来接近它？

我对通用方法很感兴趣，但希望能在 python、javascript 或您选择的任何编码语言中举一个例子。

Answer 1

由于您没有展示自己的方程式、算法或代码，而只是展示了中心对齐圆的算法大纲，因此我也将在此处给出更一般情况下的算法大纲.

小圆是大圆经过相似变换后的图像。 IE。在较大的圆上有一个固定点和一个比率（R/r，大于 1），这样您就可以在较小的圆上取任何一点，检查从固定点到该点的向量，然后乘以该向量按比率，然后该向量从固定点开始时的末端是较大圆上的一个点。这种转换是一对一的。

所以你可以在较小的圆上随机选择一个点（在0到2-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

Answer 2

您真的需要精确抽样吗？因为使用 acceptance/rejection 它应该可以正常工作。我假设大橙色圆圈位于 (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)

Answer 3

Severin Pappadeux 描述的 acceptance/rejection 方法可能是最简单的方法。

对于直接接近，您也可以在极坐标中工作，以孔的中心为极点。

外圆的极坐标方程(Θ, σ)（抱歉，没有rho）将是

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

这是一个 σ 的二次方程，你可以很容易地用 Θ 求解。然后你可以在 0, 2π 中画一个角，在 r 和 σ 之间画一个半径。

这不会为您提供均匀分布，因为 σ 的范围是 Θ 的函数，并且由于极性偏差。这可以通过计算合适的传递函数来解决，但这有点技术性，可能难以分析。

Answer 4

这里有一个简单的方法，可以在不重新采样的情况下给出均匀分布。

为简单起见，假设外边界圆（半径r_outer）的中心位于(0, 0)，内圆边界（半径r_inner）的中心位于(x_inner, y_inner).

外盘写D，偏心内孔给出的平面子集写H1，中心写H2 半径为 r_inner 的圆盘，以 (0, 0).

为中心

现在假设我们忽略内圈不在中心的事实，而不是从 D-H1 采样，我们从 D-H2 采样（这很容易统一）。然后我们犯了两个错误：

有一个区域 A = H1 - H2 我们可以从中采样，即使这些样本不应该出现在结果中。
有一个区域 B = H2 - H1 我们从未从中采样，尽管我们应该

但事情是这样的：区域 A 和 B 是全等的：给定平面中的 any 点 (x, y)，[=当且仅当 (x_inner - x, y_inner - y) 在 H1 中时，27=] 在 H2 中，并且当且仅当 [=30] 时，(x, y) 在 A 中=] 在 B 中！地图 (x, y) -> (x_inner - x, y_inner - y) 表示围绕点 (0.5*x_inner, 0.5*y_inner) 旋转 180 度。所以有一个简单的技巧：从 D - H2 生成，如果我们最终在 H1 - H2 中得到某些东西，则旋转以获取 H2 - H1 的对应点。

这是代码。注意使用均匀分布的平方根来选择半径：这是一个标准技巧。例如，参见 this article。

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()

带有移位孔的环形空间内的随机点

Random point inside annulus with a shifted hole

python

random

math

geometry

point