19
\$\begingroup\$

I have an image that contains a circles at a specific location, and of a specific diameter. What I need to do is to be able to calculate random points within the circle, and then manipulate the pixels said points correlate to. I have the following code already:

private Point CalculatePoint()
{
    var angle = _random.NextDouble() * ( Math.PI * 2 );
    var x = _originX + ( _radius * Math.Cos( angle ) );
    var y = _originY + ( _radius * Math.Sin( angle ) );
    return new Point( ( int )x, ( int )y );
}

And that works fine for finding all the points at the circumference of the circle, but I need all points from anywhere in the circle. If this doesn't make sense let me know and I will do my best to clarify.

\$\endgroup\$
2
  • \$\begingroup\$ Check the update. \$\endgroup\$ Apr 3, 2012 at 20:34
  • 3
    \$\begingroup\$ Good question in the sense that inadvertently creating a weighted distribution is a common error. \$\endgroup\$
    – Tim Holt
    Apr 3, 2012 at 20:54

5 Answers 5

35
\$\begingroup\$

If you want a simple solution just randomize the radius too:

private Point CalculatePoint()
{
    var angle = _random.NextDouble() * Math.PI * 2;
    var radius = _random.NextDouble() * _radius;
    var x = _originX + radius * Math.Cos(angle);
    var y = _originY + radius * Math.Sin(angle);
    return new Point((int)x,(int)y);
}

That however results in your points being more concentrated towards the center of the circle:

enter image description here

In order to get an uniform distribution make the following change to the algorithm:

var radius = Math.Sqrt(_random.NextDouble()) * _radius;

Which will give the following result:

enter image description here

For more information check the following link: MathWorld - Disk Point Picking.

And finally here's a simple JsFiddle demonstration comparing both version of the algorithm.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Excellent answer. Just one thing to add: don't forget to seed the random number generator :) \$\endgroup\$ Apr 3, 2012 at 20:40
  • \$\begingroup\$ Oop you beat met to it - didn't see this post when I posted mine. The wolfram site is an awesome resource for this kind of thing. \$\endgroup\$
    – Tim Holt
    Apr 3, 2012 at 20:54
  • 1
    \$\begingroup\$ @TimHolt Happens all the time :) \$\endgroup\$ Apr 3, 2012 at 21:05
  • \$\begingroup\$ Is this assuming the circle center is at 0,0 ? \$\endgroup\$
    – jjxtra
    Sep 29, 2013 at 18:06
  • \$\begingroup\$ @PsychoDad The center of the circle would be (_originX, _originY) \$\endgroup\$ Oct 1, 2013 at 10:12
5
\$\begingroup\$

DO NOT just use random r and theta! This creates a weighted distribution with more points in the center. This page illustrates it well...

http://mathworld.wolfram.com/DiskPointPicking.html

Here's the method that creates a non-weighted distribution...

var r = rand(0,1)
var theta = rand(0,360)

var x = sqrt(r) * cos(theta)
var y = sqrt(r) * sin(theta)
\$\endgroup\$
4
  • \$\begingroup\$ Oops duplicate of selected answer :P \$\endgroup\$
    – Tim Holt
    Apr 3, 2012 at 20:56
  • \$\begingroup\$ I'm confused because you say not to use random r and theta as it creates a weighted distribution then the code you show that you claim creates a non-weighted distribution generates r within range [0,1]. Did you intend to square root the random number? \$\endgroup\$
    – PeteUK
    Dec 16, 2016 at 20:59
  • \$\begingroup\$ Yes doing the square root of the radius (as long as it's 0-1) reduces the unexpected concentration of points in the middle. See the Wolfram link I posted, which illustrates it and explains it with the mathematics better than I can. \$\endgroup\$
    – Tim Holt
    Dec 17, 2016 at 0:10
  • \$\begingroup\$ My bad. I see you do sqrt(r) when calculating x and y. \$\endgroup\$
    – PeteUK
    Dec 17, 2016 at 0:26
4
\$\begingroup\$

You’re halfway there. In addition to generating a random angle, just generate a random distance, less than or equal to the radius, weighted so that you get a uniform distribution:

private Point CalculatePoint()
{
    var angle = _random.NextDouble() * Math.PI * 2;
    var distance = Math.Sqrt(_random.NextDouble()) * _radius;
    var x = _originX + (distance * Math.Cos(angle));
    var y = _originY + (distance * Math.Sin(angle));
    return new Point((int)x, (int)y);
}

Now you’re thinking with polar.

You can also weight the distance like so to avoid a square root:

var distance = _random.NextDouble() + _random.NextDouble();
distance = (distance <= 1 ? distance : 2 - distance) * _radius;
\$\endgroup\$
5
  • \$\begingroup\$ Okay, so we gave exactly the same answer within seconds of difference. Now what? :) \$\endgroup\$ Apr 3, 2012 at 20:23
  • \$\begingroup\$ @DavidGouveia We both get upvotes for both being right. Everybody wins! :D \$\endgroup\$
    – Jon Purdy
    Apr 3, 2012 at 20:24
  • \$\begingroup\$ Both answers very much appreciated (and the link too!). Man I am an idiot for not seeing that myself though, -1 to me :( Thanks again to you both! \$\endgroup\$
    – DMills
    Apr 3, 2012 at 20:29
  • \$\begingroup\$ This will generate random points, but they'll not be uniformly distributed over the disk, right? Rather they'll be weighted towards the centre. Just checking I'm not missing something. \$\endgroup\$
    – PeteUK
    Dec 16, 2016 at 21:00
  • 1
    \$\begingroup\$ @PeteUK: You’re right, the distance should be weighted. Let me update. \$\endgroup\$
    – Jon Purdy
    Dec 16, 2016 at 21:05
3
\$\begingroup\$

If performance is an issue then one alternative solution is to generate a random position in a box with the width/height of your circle and then throw away any points that are not in the area of the circle.

The advantage of this method is that you are doing no cos/sin/sqrt functions, which depending on your platform may be a big speed saving.

var x = _random.NextDouble();
var y = _random.NextDouble();
if (x*x + y*y < 1.0f)
{
    // we have a usable point inside a circle
    x = x * diameter - _radius + _OriginX;
    y = y * diameter - _radius + _OriginY;
    // use the point(x,y)
}
\$\endgroup\$
1
  • \$\begingroup\$ I'm going to try that out and see if it speeds things up. I'm not sure I have a performance problem, but I'll try this anyway, thanks! \$\endgroup\$
    – DMills
    Apr 11, 2012 at 1:51
0
\$\begingroup\$

I have taken the approach of one of the listed comments, and extended the functionality to create a donut shaped point generation system.

            private Vector2 CalculatePosition()
            {
                double angle = _rnd.NextDouble() * Math.PI * 2;
                double radius = InnerCircleRadius + (Math.Sqrt(_rnd.NextDouble()) * (OuterCircleRadius - InnerCircleRadius));
                double x = (_context.ScreenLayout.Width * 0.5f) + (radius * Math.Cos(angle));
                double y = (_context.ScreenLayout.Height * 0.5f) + (radius * Math.Sin(angle));
                return new Vector2((int)x, (int)y);
            }

It is a similar approach as previously mentioned but provided different results. The inner part of the circle will be left blank with no points.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .