Sample(1. Basic)

Sample

已知条件

我们只有一个产生 [0, 1] 随机数的函数，名为func。现在，我想让你根据这个函数来对很多形状的图形进行均匀采样。

假设1：稠密性

如果我们可以得到[0, 1]的随机数。那么我们就可以得到[a, b]的随机数，我们只需要

x' = x * (b - a) + a

正方形采样

对于 $a \times a$ 大小的正方形采样，我们只需要

x = a \cdot x\\ y = a \cdot x

出来的效果很好

矩形采样

我们沿用简单的正方形采样方式对 $a \times b$ 大小的矩形进行采样的话，即

x = a \cdot x\\ y = b \cdot x

这样出来的效果如下所示：

Width:
Height:
Number of points:

Inverse Transform Sampling

ITS是一个传统的方法，它是从U(0, 1)生成任意想要的概率密度函数的随机数的方法。

看看它是如何做的。我们如果想得到一个分布的函数，那么我们可以对我们想要的pdf积分得到CDF

$F( x ) = \int_{-\infty}^{x}f(u)du$

那么我们就得到了符合该pdf的随机数产生函数了

$G(x) = F^{-1}(rad(x))$

拒绝采样

拒绝采样的原理就更简单了，如果我们要均匀采样一个圆，我们不知道怎么做。

但是我们知道采样正方形的办法了。那么我们只需要采样正方形，如果落在内接圆内就输出，否则重新采样。

伪代码是这样的。

function sample_square(r)
    return math.random(0, r), math.random(0, r)
end

function sample_circle(r)
    local x, y
    while true do
        x, y = sample_square(2 * r)
        x = x - r
        y = y - r
        if (x * x + y * y) < (r * r) then
            break
        end
    end
    return x, y
end

圆形采样

和之前的采样方式不同，圆形你如果使用极角和极轴来直接采样的话，会导致采样点集中分布到圆心。

Radius:
Number of points:

那么我们就可以使用非拒绝采样的ITS做法。不过这次是二维的。

对于圆形，我们想要的分布肯定是这样的

$1 = \iint _{\Omega} \frac{1}{\pi} d\sigma \\ pdf(x, y) = \frac{1}{\pi}$

那么把这个分布转换成极坐标下的分布给，根据雅可比矩阵，我们得到

$1 = \iint _{\Omega} \frac{1}{\pi} d\sigma = \iint_\Omega{}\frac{1}{\pi} \frac{\partial(x, y)}{\partial(\theta, r)}d\theta dr = \iint_\Omega \frac{r}{\pi} d\theta dr$

那么我们可以得到 $\theta$ 和 $r$ 的偏概率密度

$pdf(r) = 2r \\ pdf(\theta) = \frac{1}{2\pi}$

那么我们有

$F(r) = r^2 \Rightarrow F^{-1}(r) = \sqrt{r} \\ F(\theta) = \frac{\theta}{2\pi} \Rightarrow F^{-1}(\theta) = {2\pi\theta}$

根据变换公式，我们得到

$a, b \sim U(0, 1) \\ x = \sqrt{a} \space cos(2\pi b) \\ y = \sqrt{a} \space sin(2\pi b)$