c++ random point in circle - where did I go wrong?

Question

class Solution {
private:
double c_radius;
double xcenter;
double ycenter;

public:
    Solution(double radius, double x_center, double y_center) {
    c_radius = radius;
    xcenter = x_center;
    ycenter = y_center;  
}

vector<double> randPoint() {
    double randomradius= (sqrt((double)rand()) / RAND_MAX) * c_radius;
    double randomangle= ((double)rand() / RAND_MAX) * 360.0;
    double yp= sin(randomangle)*randomradius;
    double xp= cos(randomangle)*randomradius;
    std::vector<double> point= {xp+xcenter, yp+ycenter};
    return point; 
}
};

Hi everyone, I was doing a Leet Code question about finding a random point within a circle. It all goes well until following test: Inputs: [[0.01,-73839.1,-3289891.3]

It is essentially generating a random point within a circle however my result seems to be rounded off and I am not sure why.

My Output after generating point:

[null,[-73839.10**000**,-3289891.30**000**],[-73839.10**000**,-3289891.30000],[-73839.10000,-3289891.30000],[-73839.10000,-3289891.30000],[-73839.10000,-3289891.30000]...

Expected Output

[null,[-73839.10**006**,-3289891.30**228**],[-73839.10**541**,-3289891.30660],[-73839.10634,-3289891.30124],[-73839.10256,-3289891.30684],[-73839.09825,-3289891.29962]...

Now my question is where is the error? Is there a fault in my math? The results are close but not close enough. I cannot seem to pinpoint where this error occurs. Any help is greatly appreciated.

You *do* know that the trigonometric functions uses *radians* for its angles? — Some programmer dude, Mar 01 '23 at 09:37
By the way, a `std::vector` for two values? Seems a little excessive. Either create your own `point` structure (or a `vector2` structure, or similar), or use e.g. `std::pair` (or possibly `std::tuple`). — Some programmer dude, Mar 01 '23 at 09:39
ot: https://stackoverflow.com/questions/1711990/what-is-this-weird-colon-member-syntax-in-the-constructor — 463035818_is_not_an_ai, Mar 01 '23 at 09:40
Why the `sqrt`? I'd say that's the reason why you're generating points closer to the center than you wanted. — teapot418, Mar 01 '23 at 09:44
Also why are you taking the square root of the result of `rand()`, especially before dividing by `RAND_MAX`? — chrysante, Mar 01 '23 at 09:44
@someprogrammerdude I did not choose the return type. I made a object because I was going crazy, but other than that I was given the return type. Also, I used degree angles as calculated above in the function. 6/7 tests are passed successfully. Only this one gives me trouble. — MP3D, Mar 01 '23 at 09:44
What did you plan to do with `(sqrt((double)rand()) / RAND_MAX)`? `sqrt((double)rand())` gives you a value between `0` and `181.01933...`, dividing by `32768` (the most common value for `RAND_MAX`) gives you a value between `0` and `0.00552427...`, not a very good range. — mch, Mar 01 '23 at 09:45
using sqrt on random will distribute the points more evenly and not close to the centre. — MP3D, Mar 01 '23 at 09:46
No, it will distribute the values very close to the center, only 0.55% away from the center at the maximum. — mch, Mar 01 '23 at 09:47
Let's say RAND_MAX is 100, compare: `64/100` vs. `8/100` vs. `8/10` - did you want to apply sqrt to RAND_MAX as well? — teapot418, Mar 01 '23 at 09:47
actually saw a graph that was showing the opposite. I will remove it and test again but It did not help, its still throwing an error. Testing again: unfortunately, removing sqrt still didnt help. Still throwing an error: output: -73839.09962 expected: -73839.09086. Not sure where this error appears still. — MP3D, Mar 01 '23 at 09:50
You would have to take the square root **after** dividing by `RAND_MAX` — chrysante, Mar 01 '23 at 09:50
@chrysante that pretty much fixed it, it works now. Thank you very much! :) I have edited the post and pasted the "fixed" version even if its just some minor differences. — MP3D, Mar 01 '23 at 09:54
Also for anything serious consider using the C++ `` library instead of the C function `rand()`. — chrysante, Mar 01 '23 at 09:54
You should roll-back the edit you made to your question (i.e. remove the answer and the fix); otherwise, it will be closed as "not reproducible". If you like, you can post the 'answer' given in the comments as an *actual* answer. — Adrian Mole, Mar 01 '23 at 10:08
@MP3D I don't get why you use a square root to compute a random value between 0 and c_radius. Shouldn't you do something like : `double randomradius = ( (double) rand() / RAND_MAX) * c_radius;` ? — Thibault Cimic, Mar 01 '23 at 10:50
@MP3D add a full example of your code so that we can reproduce your problem pls — Thibault Cimic, Mar 01 '23 at 10:51
May be more efficient (and less biased) to generate points uniformly over the bounding square and simply reject the ones outside the circle. — lastchance, Mar 01 '23 at 11:00

Marek R · Accepted Answer · 2023-03-01T11:36:07.277

0

With your current approach you will not get uniform distribution (even when radians are fixed). Points will be focused in a center.

Task description says points distribution suppose to be uniform, but I have doubts if proper statistical test for it is written.

Instead making this complicated, just randomly pick coordinates in square containing a circle and keep generating this point until it fits inside a circle.

class Solution {
    std::mt19937 gen;
    std::uniform_real_distribution<> dis;
    double xc;
    double yc;
    double r2;

public:
    Solution(double radius, double x_center, double y_center) 
        : dis{-radius, radius}
        , xc{x_center}
        , yc{y_center}
        , r2{radius * radius}
    {
    }
    
    std::vector<double> randPoint() {
        double dx, dy;
        do {
            dx = dis(gen);
            dy = dis(gen);
        } while (dx*dx + dy*dy > r2);
        return {xc + dx, yc + dy};
    }
};

edited Mar 01 '23 at 11:36

answered Mar 01 '23 at 11:30

Marek R

32,568
6
55
140

isnt this extremely inefficient considering the function will be called 3 * 10^4 times at most.. – MP3D Mar 01 '23 at 12:22
quite opposite. Areas which are rejected are really small comparing to circle. 78% of this area is a circle. `sin` `cos` and `sqrt` are much slower then just retrying and check point is inside a circle. – Marek R Mar 01 '23 at 12:30
cool, learnt something! I am however really unsure what std::mt19937 gen; std::uniform_real_distribution<> are and how to work with them. Thanks for the answer. – MP3D Mar 01 '23 at 12:40
To prove point with performance: https://quick-bench.com/q/4YLsNRGjt5kd-IfRtizk99Cf0u4 – Marek R Mar 01 '23 at 13:42

score 0 · Answer 2 · edited Mar 06 '23 at 23:31

Seems like I had the sqrt() operation in the wrong place. Using sqrt() after I computed the result of the rand()/RAND_MAX passes the test. (thanks chrysante) full code:

class Solution {
private:
double c_radius;
double xcenter;
double ycenter;

public:
Solution(double radius, double x_center, double y_center) {
    c_radius = radius;
    xcenter = x_center;
    ycenter = y_center;  
}

vector<double> randPoint() {
    double randomradius= sqrt(((double)rand() / RAND_MAX)) * c_radius;
    double randomangle= ((double)rand() / RAND_MAX) * 360.0;
    double yp= sin(randomangle)*randomradius;
    double xp= cos(randomangle)*randomradius;
    return {xp+xcenter, yp+ycenter};
}
};

This code passes all Leetcode tests. Square rooting the result of rand()/RAND_MAX is neccessary, otherwise it will throw the same error as in the original post.

you have copied 360 bug, see comments under question. – Marek R Mar 01 '23 at 13:49 — Marek R, Mar 01 '23 at 13:49

c++ random point in circle - where did I go wrong?

2 Answers2