CODEWITHSUNDEEP
algorithmrandomgeometry2ddistribution
Lior Kogan
Lior Kogan

Reputation: 20658

Generate a random point within a rectangle (uniformly)

Generate a random point within a rectangle (uniformly)

This suppose to be a simple problem.

However, in RANDOM_DATA homepage I found the following note:

However, we will not achieve uniform distribution in the simple case of a rectangle of nonequal sides [0,A] x [0,B], if we naively scale the random values (u1,u2) to (A*u1,B*u2). In that case, the expected point density of a wide, short region will differ from that of a narrow tall region. The absence of uniformity is most obvious if the points are plotted.

I found it quite of strange... I can't figure out why such scaling will affect the uniformity.

What am I missing?

Edit:

Thank you Patrick87 and missingno. I was searching for a theoretical reason for the statement. I now understand that the reason is not theoretical, but practical - the granularity of floating-point values.

If I'll generate two uniform floating-points between 0 and 1 (which is an issue by itself due to the nature of floating-point value representation. Look here for an algorithm) - the granularity will be limited.

Suppose that there are X different values between 0 and 1. By scaling (u1,u2) to (u1,2*u2) we'll have X different values in the range [0,u1] and X different values in the range [0,2*u2]. For area uniformity we should have twice as many different values in [0,2*u2] than in [0,u1].

Given that, Allow me to change my question:

How should I generate a random point within a rectangle (with uniform distribution by area)?

Upvotes: 6

Views: 14162

Answers (4)

D3C34C34D
D3C34C34D

Reputation: 417

The most straightforward way to handle this is through rejection sampling:

http://en.wikipedia.org/wiki/Rejection_sampling

// Given dimensions of the rectangle A, B where A <= B
boolean flag = true
while (flag) do:
  double a = NextRandomDouble(0,B)
  double b = NextRandomDouble(0,B)
  if (a <= A)
    return(a, b)
  else
    next

You essentially generate uniform numbers from a square that fits the original rectangle (of length B, in this example). If the number falls in the rectangle, keep the pair. If it does not, throw it away and try again!

Upvotes: 1

Patrick87
Patrick87

Reputation: 28312

How should I generate a random point within a rectangle (with uniform distribution by area)?

This should work:

  // given A, B, dimensions of rectangle
  // given g, granularity of shorter side

  if A > B then
     bm := g
     am := floor(g * A / B)
  else then
     am := g
     bm := floor(g * B / A)

  for i := 1 to n do
     av := A * RandomInt(0..am) / am
     bv := B * RandomInt(0..bm) / bm
     print (av, bb)

EDIT: A simpler alternative would be to simply scale random floating point values by the same factor, choose points at random, and throw away points that fall outside your rectangle. However, you don't know how many trials you'd need before you got N points in the rectangle...

Upvotes: 2

unkulunkulu
unkulunkulu

Reputation: 11922

That statement is incorrect, direct product of two independent uniform measures is a uniform measure. This can be shown as follows:

A probability for a random point to hit a rectangle with sides a and b is equal to probability for the first coordinate to hit the segment with the length a and the second coordinate to hit the segment with the length b. (We are talking about projections of a rectangle to axes).

First probability is a / A, the second one is b / B. As these variables are independent, the probabilities multiply, so the resulting probability is ab / AB, so we have a uniform 2D distribution as the probability is proportional to the area of the rectangle. This formula is symmetric with respect to a and b, so the observation in the quote is wrong about narrow and wide rectangles.

Upvotes: 5

hugomg
hugomg

Reputation: 69964

Ascii art:

Take a 3x3 rectangle:

***
***
***

And spread one of the sides by 3x:

*..*..*..*
*..*..*..*
*..*..*..*

You can kind of see here that the points are more densely packed vertically than they are horizontaly. What you actually want instead is uniform distribution by area

Upvotes: 2

Related Questions