1.题目基本信息

1.1.题目描述

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象

• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

1.2.题目地址

https://leetcode.cn/problems/generate-random-point-in-a-circle/description/

2.解题方法

2.1.解题思路

思路1：拒绝采样。在一个正方形中随机采样，对于不在圆中点进行拒绝

思路2：概率分布。将一个单位圆微分成无数个圈组成，对于半径为r的圈的周长为l=2pir，由于需要在圆上均匀随机的采样，所以取的点的半径为r的概率P{R=r}=kr，则取得的点的距离圆心距离小于等于r的概率F(r)=∫_0^r(kx)dx，F(1)=k/2=1，所以k=2，F(r)=r*2；设M=F(r)，易知M符合U(0,1)均匀分布，所以均匀随机的取m，进而r=sqrt(m)也是均匀随机取到的。r随机取完后，可以从[0,2pi)中独立的随机取\theta。通过r和\theta即可随机在圆内取得一个点。

• 证明：F(r)符合U(0,1)均匀分布。P{M<=m}=P{F(r)<=m}=P{r<=F^(-1)(m)}=F(F^(-1)(m))=m，所以M=F(r)符合U(0,1)均匀分布

3.解题代码

python3代码-拒绝采样

class Solution:
    # 思路2：概率分布。将一个单位圆微分成无数个圈组成，对于半径为r的圈的周长为l=2*pi*r，由于需要在圆上均匀随机的采样，所以取的点的半径为r的概率P{R=r}=k*r，则取得的点的距离圆心距离小于等于r的概率F(r)=∫_0^r(k*x)dx，F(1)=k/2=1，所以k=2，F(r)=r**2；设M=F(r)，易知M符合U(0,1)均匀分布，所以均匀随机的取m，进而r=sqrt(m)也是均匀随机取到的。r随机取完后，可以从[0,2*pi)中独立的随机取\theta。通过r和\theta即可随机在圆内取得一个点。
    # 证明：F(r)符合U(0,1)均匀分布。P{M<=m}=P{F(r)<=m}=P{r<=F^(-1)(m)}=F(F^(-1)(m))=m，所以M=F(r)符合U(0,1)均匀分布
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.xc = x_center
        self.yc = y_center

    def randPoint(self) -> List[float]:
        m = random.random()
        r1 = sqrt(m)
        theta = random.uniform(0, 2 * math.pi)
        return [self.xc + r1 * math.cos(theta) * self.r, self.yc + r1 * math.sin(theta) * self.r]


class Solution1:
    # 思路1：拒绝采样。在一个正方形中随机采样，对于不在圆中点进行拒绝
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.xc = x_center
        self.yc = y_center

    def randPoint(self) -> List[float]:
        while True:
            x = random.uniform(-1, 1)
            y = random.uniform(-1, 1)
            if x * x + y * y < 1:
                return (self.xc + x * self.r, self.yc + y * self.r)

# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()

python3代码-概率分布

class Solution:
    # 思路2：概率分布。将一个单位圆微分成无数个圈组成，对于半径为r的圈的周长为l=2*pi*r，由于需要在圆上均匀随机的采样，所以取的点的半径为r的概率P{R=r}=k*r，则取得的点的距离圆心距离小于等于r的概率F(r)=∫_0^r(k*x)dx，F(1)=k/2=1，所以k=2，F(r)=r**2；设M=F(r)，易知M符合U(0,1)均匀分布，所以均匀随机的取m，进而r=sqrt(m)也是均匀随机取到的。r随机取完后，可以从[0,2*pi)中独立的随机取\theta。通过r和\theta即可随机在圆内取得一个点。
    # 证明：F(r)符合U(0,1)均匀分布。P{M<=m}=P{F(r)<=m}=P{r<=F^(-1)(m)}=F(F^(-1)(m))=m，所以M=F(r)符合U(0,1)均匀分布
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.xc = x_center
        self.yc = y_center

    def randPoint(self) -> List[float]:
        m = random.random()
        r1 = sqrt(m)
        theta = random.uniform(0, 2 * math.pi)
        return [self.xc + r1 * math.cos(theta) * self.r, self.yc + r1 * math.sin(theta) * self.r]


class Solution1:
    # 思路1：拒绝采样。在一个正方形中随机采样，对于不在圆中点进行拒绝
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.xc = x_center
        self.yc = y_center

    def randPoint(self) -> List[float]:
        while True:
            x = random.uniform(-1, 1)
            y = random.uniform(-1, 1)
            if x * x + y * y < 1:
                return (self.xc + x * self.r, self.yc + y * self.r)

# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()

4.执行结果