[LeetCode]Generate Random Point in a Circle

这道题我们首先可以想到的就是在长度为圆形直径的正方形内不断generate random point，如果其在圆形内，那么我们就返回，否则我们重新generate。这就是所谓的rejection sampling，那么需要call random的期望是area(square) / area(circle) = 1 / (PI * 0.25) = 4 / PI。代码如下：


另外一种方法，我们需要用到概率分布函数的方法。首先，我们可以知道当距离圆心为r的地方，周长为2 * PI * r，那么对于x1和x2，如果x2 = 2 * x1，那么x2所在圆环的周长也是x1所在周长的两倍，对应的点数也是两倍。所以我们知道点的分布是随着半径r的增加而线性增加的。对于单位圆的情况，给定的r为1，由于PDF(概率分布函数)和x轴围成的面积一定是1，所以PDF为y = 2 * x。对应的CDF(累积分布函数)就是对PDF求积分，为y = x^2。如下如所示：

我们可以看到，如果要求generate出来的y是均匀分布的话，x应该满足x轴上面的疏密度分布。如果要求x对应的分布的话，我们需要运用Inverse Transform Sampling。具体来讲，需要进行以下骤求：

• 把对应CDF的y和x互换，得到y ^ 2= x
• y = sqrt(x)，就是我们要求的inverse CDF

也就是说，x满足CDF = sqrt(x)分布的情况下，生成的点在圆形内才是满足均匀分布的。生成点的时候我们用极坐标表示，随机生成半径和与X轴的夹角即可，每次call两次random。代码如下：