솔루션: 원 안에 임의의 점 생성

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #478(중간): 원 안에 임의의 점 생성

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

• input and output values are in floating-point.
• radius and x-y position of the center of the circle is passed into the class constructor.
• a point on the circumference of the circle is considered to be in the circle.
• randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

예:

Example 1:
Input:	["Solution","randPoint","randPoint","randPoint"] [[1,0,0],[],[],[]]
Output:	[null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
Explanation:	The input is two lists: the subroutines called and their arguments. Solution's constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Example 2:
Input:	["Solution","randPoint","randPoint","randPoint"] [[10,5,-7.5],[],[],[]]
Output:	[null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

원에서 임의의 점을 얻는 가장 쉬운 방법은 극좌표 표기법을 사용하는 것입니다. 극좌표 표기법을 사용하면 극좌표 각도(ang)와 빗변 길이(hyp)로 원의 모든 점을 정의할 수 있습니다.

둘 다에 대해 난수 생성기를 적용하여 사용 가능한 범위의 값을 제공할 수 있습니다. 극각은 [0, 2 * pi] 범위에 있고 빗변은 [0, 반지름] 범위에 있습니다.

빗변에 대한 임의의 값을 찾을 때 상황이 까다로울 수 있습니다. 왜냐하면 전체 허용 범위를 균등하게 선호하면 포인트가 원의 중심으로 더 밀집되는 경향이 있기 때문입니다.

예를 들어 반지름이 1인 원을 생각해보자. 반지름을 반으로 나누면 작은 반쪽이 빗변([0, 0.5])인 점들이 흩어질 면적은 반지름이 0.5인 원이다. 면적은 pi * (0.5)^2 또는 0.25 * pi로 정의됩니다. 더 큰 절반([0.5, 1])에 빗변이 있는 점이 분산되는 영역은 pi * 1^2 - 0.25 * pi 또는 0.75 * pi로 정의되는 더 큰 원의 나머지 차이입니다.



따라서 두 개의 반쪽이 균등하더라도 두 개의 반쪽을 중심으로 회전하여 설명하는 영역은 크게 다릅니다. 고른 분포를 허용하려면 중심에서 멀리 떨어진 값을 기하급수적으로 선호할 수 있도록 빗변을 얻기 위해 반지름을 곱하기 전에 난수의 제곱근을 취해야 합니다.

ang 및 hyp에 대한 값이 있으면 사인과 코사인을 사용하여 직각 삼각형의 반대쪽(opp) 및 인접(adj) 다리에 대한 값을 얻을 수 있습니다. 중심점(XC, YC)의 x 및 y 좌표.

구현:

네 가지 언어 모두의 코드는 거의 동일합니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    constructor(radius, x_center, y_center) {
        this.RAD = radius
        this.XC = x_center
        this.YC = y_center
    }
    randPoint() {
        let ang = Math.random() * 2 * Math.PI,
            hyp = Math.sqrt(Math.random()) * this.RAD,
            adj = Math.cos(ang) * hyp,
            opp = Math.sin(ang) * hyp
        return [this.XC + adj, this.YC + opp]
    }
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.RAD = radius
        self.XC = x_center
        self.YC = y_center
    def randPoint(self) -> List[float]:
        ang = random.uniform(0, 1) * 2 * math.pi
        hyp = sqrt(random.uniform(0, 1)) * self.RAD
        adj = cos(ang) * hyp
        opp = sin(ang) * hyp
        return [self.XC + adj, self.YC + opp]

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    double RAD, XC, YC;
    public Solution(double radius, double x_center, double y_center) {
        RAD = radius;
        XC = x_center;
        YC = y_center;
    }
    public double[] randPoint() {
        double ang = Math.random() * 2 * Math.PI,
            hyp = Math.sqrt(Math.random()) * RAD,
            adj = Math.cos(ang) * hyp,
            opp = Math.sin(ang) * hyp;
        return new double[]{XC + adj, YC + opp};
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    double RAD, XC, YC;
    Solution(double radius, double x_center, double y_center) {
        RAD = radius;
        XC = x_center;
        YC = y_center;
    }   
    vector<double> randPoint() {
        double ang = (double)rand() / RAND_MAX * 2 * M_PI,
            hyp = sqrt((double)rand() / RAND_MAX) * RAD,
            adj = cos(ang) * hyp,
            opp = sin(ang) * hyp;
        return vector<double>{XC + adj, YC + opp};
    }
};