math - 两个圆盘相交区域的均匀采样

Question

给定二维均匀变量，我们可以在单元盘中生成均匀分布，如here 所述。 .

我的问题是相似的，因为我希望对两个相交磁盘的交叉区域进行均匀采样，其中一个磁盘始终是单位磁盘，另一个可以像 here 一样自由移动和调整大小。



我试图将该区域分成两个区域(如上所示)并根据受尊重的磁盘对每个区域进行采样。我的方法基于上面引用的统一磁盘算法。为了对中心线右侧的第一个区域进行采样，我会将 theta 限制在两个交点内。下一个 r 将需要基于该 theta 进行投影
使得这些点被插入我们的中线和圆盘半径之间的区域。 python示例代码可以在here找到.

u = unifrom2D()
A;B; // Intersection points
for p in allPoints
    theta = u.x * (getTheta(A) - getTheta(B)) + getTheta(B)
    r = sqrt(u.y + (1- u.y)*length2(lineIntersection(theta)))  
    p = (r * cos(theta), r * sin(theta))

然而，这种方法相当昂贵并且进一步不能保持均匀性。只是为了澄清我不想使用拒绝抽样。

Answer 1

我不确定这是否比拒绝采样更好，但这里有一个圆段(中心角 <= pi)均匀采样的解决方案，涉及反函数的数值计算。 (两个圆的交点的均匀采样可以由线段、扇区和三角形的采样组成——这取决于如何将交点分割成更简单的图形。)

首先我们需要知道如何生成一个随机值Z给定分布 F ，即我们想要

P(Z < x) = F(x)                   <=>  (x = F^-1(y))
P(Z < F^-1(y)) = F(F^-1(y)) = y   <=>  (F is monotonous)
P(F(Z) < y) = y

这意味着:如果 Z具有请求的分发 F ，然后 F(Z)是均匀分布的。反过来说:

Z = F^-1(Y), 

哪里 Y均匀分布于 [0,1] , 具有请求的分布。

如 F是形式

       / 0,                             x < a
F(x) = | (F0(x)-F0(a)) / (F0(b)-F0(a)), a <= x <= b
       \ 1,                             b < x

那么我们可以选择一个 Y0统一在 [F(a),F(b)]并设置 Z = F0^-1(Y0) .

我们选择通过 (theta,r) 参数化该段，其中中心角 theta从一个段侧测量。当线段的中心角为 alpha 时，线段的面积与角度为 theta 的扇区相交从线段开始的地方开始(对于单位圆， theta in [0,alpha/2] )

F0_theta(theta) = 0.5*(theta - d*(s - d*tan(alpha/2-theta)))

哪里 s = AB/2 = sin(alpha/2)和 d = dist(M,AB) = cos(alpha/2) (圆心到线段的距离)。 (案例 alpha/2 <= theta <= alpha 是对称的，这里不考虑。)
我们需要一个随机 theta与 P(theta < x) = F_theta(x) . F_theta的倒数不能以符号方式计算 - 它必须由某些优化算法(例如 Newton-Raphson)确定。

曾经 theta是固定的，我们需要一个随机半径 r在范围内

[r_min, 1], r_min = d/cos(alpha/2-theta).

对于 x在 [0, 1-r_min]分布必须是

F0_r(x) = (x+r_min)^2 - r_min^2 = x^2 + 2*x*r_min.

这里可以象征性地计算逆:

F0_r^-1(y) = -r_min + sqrt(r_min^2+y)

这是 Python 中用于概念验证的实现:

from math import sin,cos,tan,sqrt
from scipy.optimize import newton

# area of segment of unit circle
# alpha: center angle of segment (0 <= alpha <= pi)
def segmentArea(alpha):
  return 0.5*(alpha - sin(alpha))

# generate a function that gives the area of a segment of a unit circle
# intersected with a sector of given angle, where the sector starts at one end of the segment. 
# The returned function is valid for [0,alpha/2].
# For theta=alpha/2 the returned function gives half of the segment area.
# alpha: center angle of segment (0 <= alpha <= pi)
def segmentAreaByAngle_gen(alpha):
  alpha_2 = 0.5*alpha
  s,d = sin(alpha_2),cos(alpha_2)
  return lambda theta: 0.5*(theta - d*(s - d*tan(alpha_2-theta)))

# generate derivative function generated by segmentAreaByAngle_gen
def segmentAreaByAngleDeriv_gen(alpha):
  alpha_2 = 0.5*alpha
  d = cos(alpha_2)
  return lambda theta: (lambda dr = d/cos(alpha_2-theta): 0.5*(1 - dr*dr))()

# generate inverse of function generated by segmentAreaByAngle_gen
def segmentAreaByAngleInv_gen(alpha):
  x0 = sqrt(0.5*segmentArea(alpha)) # initial guess by approximating half of segment with right-angled triangle
  return lambda area: newton(lambda theta: segmentAreaByAngle_gen(alpha)(theta) - area, x0, segmentAreaByAngleDeriv_gen(alpha))

# for a segment of the unit circle in canonical position
# (i.e. symmetric to x-axis, on positive side of x-axis)
# generate uniformly distributed random point in upper half
def randomPointInSegmentHalf(alpha):
  FInv = segmentAreaByAngleInv_gen(alpha)
  areaRandom = random.uniform(0,0.5*segmentArea(alpha))
  thetaRandom = FInv(areaRandom)
  alpha_2 = 0.5*alpha
  d = cos(alpha_2)
  rMin = d/cos(alpha_2-thetaRandom)
  secAreaRandom = random.uniform(0, 1-rMin*rMin)
  rRandom = sqrt(rMin*rMin + secAreaRandom)
  return rRandom*cos(alpha_2-thetaRandom), rRandom*sin(alpha_2-thetaRandom)

可视化似乎验证了均匀分布(中心角为 pi/2 的线段的上半部分):

import matplotlib.pyplot as plot
segmentPoints = [randomPointInSegmentHalf(pi/2) for _ in range(500)]
plot.scatter(*zip(*segmentPoints))
plot.show()