478. 在圆内随机生成点（Python）

题目

难度：★★☆☆☆
类型：几何
方法：拒绝采样

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

输入值和输出值都将是浮点数。
圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
圆周上的点也认为是在圆中。
randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。
示例 1：

输入:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：

输入:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

解答

方法1：拒绝采样

我们在以圆心为中心，以二倍半径为边长的正方形内部进行随机选点，当点落在圆内或者圆上时，满足条件，返回该点。

import random


class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self):
        while True:
            x = self.x_center + (random.random() - 0.5) * self.radius * 2
            y = self.y_center + (random.random() - 0.5) * self.radius * 2
            if (x - self.x_center) ** 2 + (y - self.y_center) ** 2 <= self.radius ** 2:
                return x, y

方法2：极坐标

我们可以把上面的直角坐标变换为极坐标，随机的选取角度和半径，生成的点一定在圆上或者圆内。这里需要注意，由于在平面维度是均匀采样的，生成随机半径时需要对结果开方。


import math
import random


class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self):

        theta = random.random() * 2 * math.pi
        r = random.random() ** 0.5 * self.radius

        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)

        return x, y

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析