Picking a random point inside a shape

Factual Questions
1

I was coding something when this problem came up and it looks deceptively simple yet I can’t figure out a clever algorithm for it:

Can you come up with an algorithm that picks a random point inside a circle such that you have an equal chance of picking any single point in the circle?

For example, choosing a random theta and a random r wouldn’t work since you’re more likely to pick a point closer to the centre.

I managed to come up with a generalised one for polygons that involves decomposing them into right triangles but I can’t seem to do the same for circles. The closest I can come up with is to draw a polygon that completely covers the circle and pick a random point from that, if it falls outside of the circle, then repeat until you find a point inside the circle. But thats really lame and I’m sure theres a better method.

Any thoughts?

2

This is awkwardly worded, since there are infinitely many points inside the circle. On the other hand, using a computer to implement any algorithm you might have effectively makes the number of points inside the circle finite, of course. At any rate, I believe I see what you mean. I would phrase what you want (a uniform disribution) as follows:

The probability of picking a point from any particular region of a circle is proportional to the area of that region. In other words, if the circle has area A, and you’re looking at a subregion of the circle with area R, the probability of picking a point from that subregion should be R/A.

Actually, you’re not more likely to pick a point closer to the center, if your r is picked from a uniform distribution. You’re just as likely to pick a point “close” to the center as you are to pick a point “close” to the edge of the circle.

Again, however, I believe I understand what you mean. There is more area in the region “close” to the edge of the circle than there is “close” to the center of the circle, and so we want to weight it so that points close to the edge are more likely to be picked, correct?

Anyway, here’s my first thought. I have a strong intuition that this will give you what you want, but I’m not 100% sure off the top of my head, and I don’t have a lot of time to think on it at the moment:

Pick theta from 0 to 2pi.

Suppose R is the radius of the circle. Pick a number from the interval [0,R[sup]2[/sup]] using a uniform distribution, then take the square root of that. That’s your r, giving you the point (r,theta).

Does that seem to work?

3

What if you choose R such that the probability of choosing a particular R is proportional to R? In other words, the PDF is a ramp starting at zero and linearly increasing. Then you could choose the angle from a uniform distribution.

4

You didn’t try google first?

http://mathworld.wolfram.com/DiskPointPicking.html
Basically,
Still random theta, but use x = r^1/2 cos theta, y = r^1/2 sin theta, r between 0,1

Good luck!

(also, this is my second and last post… my trial membership expires in 10 minutes. damn)

5

“randomness” isd a strange concept to work on, because very often what seems to be logically correct isn’t, and subtleties can come back to bite you.

A different way to choose random points is to select two random numbers between -(radius) and +(radius), and reject all cases where the sum of the squares of these two numbers exceed the square of the radius. Use the first number as the x-coordinate and the second as the y-coordinate. that’s different than choosing radius and angle as your variables, and ought to evenly cover the entire area. I think you may be right about choosing r and theta as your random figures will result in skewing, because this will make the region between o and delta r as likely as the region between some r and r plus delta r as likely to receive the point, even though the areas are pi (delta r) ^2 and 2pi ® (delta r), which are very different.

Years ago, Martin Gardner had a column on the likelihood of a chord of a circle having a lelgth less than the side of an inscribed equilateral triangle. Depending upon how you chose your “random chord”, the answer was 1/4, 1/3, or 1/2. All three answers were correct – it all depended upon how you randomized your choice of chords.

6

If you have a method you’re happy with to pick a random point within a rectangle, then here’s a rather simple way to deal with a circle:

  1. Pick a random point within the square that encloses the circle
  2. Decide whether the point is within the circle
  3. If the answer to step 2 is yes, you are done; if no, go to step 1 and repeat
7

Xema – is this not what I said?

8

Upon review, I’d say it is.

9

No, this method wouldn’t fulfill your definition for randomness. Consider a circle with center C and radius R. Now imagine another smaller circle inside it with center C and radius R/2. If you divide the main circle into the areas of the inner circle and the outer ring, the ratio in areas is 1:3, but you’d get an equal number of “random” points in each.

10

I think that to be precise, what we want is to impose a grid on the circle and devise a method that is equally like to pick a poin within any square of that grid (and deal adequately with grid squares that are only partially in the circle). In that case, CalMeacham’s methd works. Certain people might argue that his method is not a proper algorithm since it’s not guaranteed to terminate in a finite number of steps. But as time goes to infinity, the probability of Cal’s algorithm not getting finished approaches zero.

11

Unless your random number generator runs very slowly, this method (also mentioned by many other posters) is probably actually your best choice. For your enclosing polygon, just choose a square, as that’s the simplest. The overhead from using any other shape would probably be more than you’d gain from wasting fewer points. It’s then very simple to determine if your point is inside of the circle (just take (x-x[sub]0[/sub][sup]2[/sup] + y-y[sub]0[/sub][sup]2[/sup], and see if it’s less than r[sup]2[/sup]).

12

I already thought of the pick inside a square method (except I can pick inside any arbitrary polygon so it would have less chance of missing the circle). However, it seems so ugly and inelegant to me.

Anyway, I think the method of biasing R is a winner. Thanks everyone.

13

Did you even read the rest of my post? That’s exactly what I said the problem with it was! I then amended it (in the same post) to picking a number from a uniform distribution on [0,R[sup]2[/sup]], then take the square root of that to get the distance our randomly chosen point is from the center of the circle.
This is exactly what the Mathworld link in spacepope’s post, so I think it’s pretty much settled.

Admittedly, I probably could’ve worded my post a bit better. When I said

what I meant was that you’re just as likely to pick R/2 as R (R being the radius of the circle). This much is certainly true, it’s just that it becomes a problem when we try to translate it back to the circle.

The reason these points “cluster” in the center of the circle is because there is “less area” there. To compensate, you have to alter the way you pick from the interval [0,R] so that points closer to R are more likely to be picked than points close to 0, which is what I did.

In other words we agree, just looking at it from a slightly different perspective (due in part to my poor wording, admittedly).

14

I’ll admit my ignorance here. I assumed the distribution of random points from the set 0 to x would be the same as those from the set /0 to x2. (Sorry about the bad notation but you know what I mean.) I take it this isn’t true?

15

Little Nemo, what I had in mind is that we’re using the same (uniform) distribution, whether we’re picking the number from [0,R] (using the incorrect method) or [0,R[sup]2[/sup]] (using the correct method). What “skews” it so that it’s appropriate for picking a random point in the circle is taking the square root.

For example, say we have a circle of radius 2. Consider another (concentric) circle inside this one with radius 1.

If we pick a number at random (using a uniform distribution) from the interval [0,2], there’s a 50% chance of our number being between 0 and 1. So there’s a 50% chance of our randomly picked point being inside the inner circle of radius 1.

This shouldn’t be, since that inner circle has area pi, exactly 1/4 of the area of the whole circle (4pi).

The idea I had was to pick a number at random (uniform distribution again) from the interval [0,2[sup]2[/sup]]. Then take the square root to get the distance our chosen point is from the center of the circle.

With this method, I think it’s clear there’s a 1/4 chance of initially picking a number between 0 and 1. Then we take the square root, but these numbers are exactly the numbers whose square roots are between 0 and 1, so once we’ve chosen our point, there’s a 1/4 chance it will lie within the inner circle, as it should be.

In other words, if we pick at random from [0,2], there’s a 50% chance of our number being between 0 and 1. On the other hand, if we pick a random number from [0,2] by

  1. Picking from [0,4], then
  2. Taking the square root of that,

then there’s a 25% chance of our picked number being between 0 and 1.

16

I’m completely with you so far.

In other words, if we pick at random from [0,2], there’s a 50% chance of our number being between 0 and 1. On the other hand, if we pick a random number from [0,2] by

  1. Picking from [0,4], then
  2. Taking the square root of that,

then there’s a 25% chance of our picked number being between 0 and 1.
[/quote]

This was the part where you lost me. I agree that it’s obvious that the square roots of a series of random numbers between 0 and 4 will give you a series of numbers between 0 and 2. But my initial guess would have been that the series would have been no different than a series of random numbers between 0 and 2. In other words, you would have just used a more complicated method to achieve a result we had already disproved.

But then I did a little figuring. I figured that a quarter of the circle’s area was contained in a circle with a radius of .5 of the total radius; that half of the circle’s area was in a radius of .707; that three quarters was in .866 radius; and the total was obviously in 1.000. And then (and you’re probably ahead of me by now) I saw that if you doubled these figues, you had radii of 1, 1.414, 1.732, and 2 - in other words, the square roots of 1, 2, 3, and 4.

So I now see that my initial assumption was wrong. Your method of using square roots does change the results and creates a series of radii that are randomly distributed.

17

If it runs faster and requires less code or explanation to following programmers than any other solution, it is the most beautiful and elegant solution.

If you want a solution than doesn’t require any multiplication, one is count how many pixels are in your circle (say counting from the leftmost pixel on the topmost line), then you just pick a random number between zero and (count - 1).Of course keeping a translation table to convert it back into x,y coordinates is going to use a bit of memory. But this solution would work for any shape.

18

There’s one reason I’d prefer the method I gave to the “weighted r” version – although it probably wouldn’t make a difference on a decent system. There are only so many decimal places you keep in calculations, and any such transformations you do will effectively change the “area” into which each random point falls. With the “random x/random y/throw out anything outside thecircle” all such areas are equal (except maybe at the edge of the circle), whereas with the “random r/square root/random theta/sin or cosine” the regions will be squished near the origin and elongated away from it. With sifficient resolution on your computer/math software that shouldn’t be a problem, but it will stil be a small bias on your results.