[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。代码如下：

	class Solution {
	public:
	double rad, xc, yc;
	//c++11 random floating point number generation
	mt19937 rng{random_device{}()};
	uniform_real_distribution<double> uni{0, 1};
	Solution(double radius, double x_center, double y_center) {
	rad = radius, xc = x_center, yc = y_center;
	}
	vector<double> randPoint() {
	double x0 = xc - rad;
	double y0 = yc - rad;
	while(true) {
	double xg = x0 + uni(rng) * 2 * rad;
	double yg = y0 + uni(rng) * 2 * rad;
	if (sqrt(pow((xg - xc), 2) + pow((yg - yc), 2)) <= rad)
	return {xg, yg};
	}
	}
	};

view raw Generate Random Point in a Circle_2.cpp hosted with ❤ by GitHub

另外一种方法，我们需要用到概率分布函数的方法。首先，我们可以知道当距离圆心为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。代码如下：

	class Solution {
	public:
	Solution(double radius, double x_center, double y_center) {
	r = radius;
	x = x_center;
	y = y_center;
	}
	vector<double> randPoint() {
	double r0 = sqrt(dis(rng)) * r, theta = dis(rng) * PI * 2;
	double x0 = x + r0 * cos(theta), y0 = y + r0 * sin(theta);
	return {x0, y0};
	}
	private:
	const double PI = 3.14159265359;
	double x, y, r;
	mt19937 rng{random_device{}()};
	uniform_real_distribution<double> dis{0, 1.0};
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(radius, x_center, y_center);
	* vector<double> param_1 = obj.randPoint();
	*/

view raw Generate Random Point in a Circle.cpp hosted with ❤ by GitHub