0028 원 내 랜 덤 생 성 점

원 내 랜 덤 생 성 점
번호: 0028
시험 문제 출처: leetcode 나의 블 로그: Something
제목 설명
원 의 반지름 과 원심 의 xy 좌 표를 정 하고 원 에서 균일 한 랜 덤 점 을 만 드 는 함수 randPoint 를 쓴다.
설명:
  • 입력 값 과 출력 값 은 모두 부동 소수점
  • 이 될 것 이다.
  • 원 의 반지름 과 원심 의 x, y 좌 표 는 매개 변수 로 클래스 에 전달 하 는 구조 함수
  • 원주 상의 점도 원 중
  • 에 있다 고 생각한다.
  • randPoint 무 작위 점 을 포함 하 는 x 좌표 와 y 좌표 의 크기 가 2 인 배열
  • 을 되 돌려 줍 니 다.
    풀이 알고리즘
    사고의 방향 을 풀다.
    이 문 제 는 두 가지 풀이 방향 이 있 는데 첫 번 째 는 샘플링 을 거부 하 는 것 이다. 바로 무 작위 로 생 성 되 기 쉬 운 도형 을 선택 하 는 것 이다. 예 를 들 어 정사각형 을 선택 하여 변 의 길 이 를 반지름 으로 만 들 면 정사각형 에서 무 작위 로 점 을 만 든 다음 에 이 점 이 원 안에 있 는 지 판단 하면 된다.
    정사각형 중 무 작위 생 성 점
    double x = r * (double)rand() / RAND_MAX;  //  rand()        RAND_MAX,         0~1      
    double y = r * (double)rand() / RNAD_MAX;
    

    이 점 이 원 안에 있 는 지 아 닌 지 를 판단 하 다.
    while(x * x + y * y > r * r)//        
    

    또 다른 방법 은 극좌 표 의 사고방식 으로 원 안에서 무 작위 로 점 을 찍 는 것 이다.
    여기 서 우 리 는 먼저 각도 theta 를 취하 고 반경 tmpR 을 취 하 는 방법 을 선택한다.
    우선 각도 theta, 각도 360, 선 택 된 것 등 가능 한 것 을 먼저 취하 기 때문에 간단하게 랜 덤 수 를 취하 면 됩 니 다.
    double theta = 360 * (double)rand() / RAND_MAX;
    

    그리고 반경 tmpR 을 선택 하면 여기에 구덩이 가 하나 있다.나 는 처음에 모든 반지름 도 가능 하 다 고 생각 했 지만 사실은 그렇지 않 았 다.수학의 공식 으로 알 수 있 듯 이 면적 은 8747 ° 2 * 8727 ° p i * 8727 ° x \ int 2 * pi * x * 8747 ° 2 * 8727 ° pi * 8727 ° x 이 고 확률 밀도 공식 을 구 할 수 있 으 면 f (x) = 2 * 8727 ° x f (x) = 2 * x f (x) = 2 * 8727 ° x x 이 며 여 기 는 pi \ pi pi 를 무시 합 니 다. 아무런 영향 이 없 기 때 문 입 니 다.
    그 다음 에 알 수 있 듯 이 임의의 한 변 의 길이 에 대해 점 이 이 변 의 길 이 를 반지름 으로 하 는 원 안에 떨 어 질 확률 은 F (x) = x 2 F (x) = x ^ 2 F (x) = x2 이 고 이런 확률 은 균일 하 게 분포 되 어야 하기 때문에 모든 확률 이 하나의 반지름 에 대응 할 수 있 기 때문에 우 리 는
    double tmpR = r * sqrt((double)rand() / RAND_MAX); //    sqrt       x2    
    

    그리고 이 두 개의 양 으로 정확 한 결 과 를 구 할 수 있 습 니 다.
    코드 구현
    class Solution {
    private:
    	double r;
    	double x;
    	double y;
    public:
        Solution(double radius, double x_center, double y_center) {
        	srand((unsigned) time(NULL));
        	r = radius;
        	x = x_center;
        	y = y_center;
        }
        
        vector<double> randPoint() {
        	double theta = 2 * M_PI * (double)rand() / RAND_MAX;
        	double tmpR = r * sqrt((double)rand() / RAND_MAX);
        	vector<double> result;
        	result.push_back(x + tmpR * cos(theta));
        	result.push_back(y + tmpR * sin(theta));
        	return result;
        }
    };
    

    좋은 웹페이지 즐겨찾기