Generate random points inside a rectangle (uniformly)?

Question

I am trying to generate a certain amount of random uniform points inside a rectangle (I know the pair of coordinates for each corner).

Let our rectangle be ABCD

My idea is: Divide the rectangle into two triangles by the AC diagonal. Find the slope and the intercept of the diagonal. Then, generate two random numbers from [0,1] interval, let them be a,b. Evaluate x = aAB and y = bAD (AB, AD, distances). If A is not (0,0), then we can add to x and y A's coordinates. Now we have a point (x,y). If it is not in the lower triangle (ABC), skip to the next step. Else, add the point to our plot and also add the symmetric of (x,y) vs. the AC diagonal so that we can fill the upper triangle (ADC) too.

I have implemented this, but I highly doubt that the points are uniformly generated (judging from the plot). How should I modify my algorithm? I guess that the issue is related to how I pick the triangle and the symmetric thing.

Fern

Can you expand on what you mean by "random uniform". These are not complimentary ideas, and I can envision a few ways to define "uniformly random". Also, reformatting your prose explanation of your algorithm into psuedo code would help clarify what you're doing a bit. – Pigskin

Beware of random distributions : The Illusion of Randomness ! You can plot the histograms of coordinates to verify the randomness of your data. – Grassland

By "random uniform" I mean that I should generate random numbers that must uniformly distributed in the area of the rectangle. – Fern

What issue do you have with your plot, specifically? I'm still not clear on how you define uniform... Uniform, in statistics/probability usually simply refers to the likelyhood of something occurring, not the resulting distribution of selected values. A non-uniform distribution, for example, would have higher probabilities of points in the upper left corner, but you could still get results that look like you have, they would just be less "probable", as there isn't a high density of points in that corner. – Pigskin

That being said, the fact that your algorithm includes the word "symmetric" and "if" and "the idea placing same point in two places based on reflection over AC diagonal" makes me believe that you are attempting to manipulate your points to more evenly fill the space, which is not random. So, how about you just specifically say what you believe the problem to be with your results. – Pigskin

img195.imageshack.us/img195/4723/screenshotfrom201305150.png The points here look "more" following the uniform distribution than the ones in my plot. – Fern

Let MATLAB determine the "uniformity" of your pseudo random distribution. If anything, the uniformity of the distribution takes away from the "random" part. Don't try an manipulate your values. Take a bunch of random points and plot them. Groupings, empty spaces, and such are aborations of pseudo random tables, and if anything, they are evidence of quality pseudo random distributions. Even in uniform distributions, if we pick from them randomly, we would expect to see groupings, emptiness, and even perhaps the same point show up consecutively occasionally. – Pigskin

Saying your plot isn't a uniform distribution is like saying we expect every flip of a coin to alternate heads->tails, no matter what. Is this random? No, sometimes we're going to get 10 heads in a row, not very often, but it happens. Get rid of the part of your algorithm that does the symmetry, and just plot random points. You're over thinking this. – Pigskin

How do you know how many statistics courses I've taken, are you with the NSA? I was not questioning my understanding of a uniform distribution, but the OPs, because the way he phrased it was not the way someone familiar with statistics would, and made it sounde like he misundestood his homework assignment. AKA: uniform distribution vs generating random points in a rectangle uniformly? It sounded like his expecatation was a set of points in a grid. If you actually read all the comments this becomes clear. If you have something productive to add 9 months later(place math joke here), go for it. – Pigskin

Answer 1

This is referred to as point picking and other similar terms. You seem to be on the right track in that the points should come from the uniform distribution. Your plot looks reasonably random to me.

What are you doing with upper and lower triangles? They seem unnecessary and would certainly make things less random. Is this some form variance reduction along the lines of antithetic variates? If @Paddy3118 is right an you really just need random-ish points to fill the space, then you should look into low-discrepancy sequences. The Halton sequence generalizes the van der Corput sequence to multiple dimensions. If you have Matlab's Statistics Toolbox check out the sobolset and haltonset functions or qrandstream and qrand.

Chalcis

Answer 2

Why not just generate x=random([A.x, B.x]) and y=random([B.y, C.y]) and put them together as (x,y)? A n-dimensional uniform distribution is simply the product of the n uniform distributions of the components.

Whin

Answer 3

This approach (from @Xipan Xiao & @bonanova.) should be reproducible in many languages. MATLAB code below.

a = 0; b = 1;
n = 2000;
X = a + (b-a)*rand(n,1);
Y = a + (b-a)*rand(n,1);

Newer versions of MATLAB can make use of the makedist and random commands.

pdX = makedist('Uniform',a,b);
pdY = makedist('Uniform',a,b);
X = random(pdX,n,1);
Y = random(pdY,n,1);

The points (X,Y) will be uniformly in the rectangle with corner points (a,a), (a,b), (b,a), (b,b).

For verification, we can observe the marginal distributions for X and Y and see that those are uniform as well.

scatterhist(X,Y,'Marker','.','Direction','out')  

Update: Using haltonset (suggested by @horchler)

p = haltonset(2);
XY = net(p,2000);
scatterhist(XY(:,1),XY(:,2),'Marker','.','Direction','out')  

Swizzle

Answer 4

If you are after a more uniform density then you might consider a Van der Corput sequence. The sequence finds use in Monte-Carlo simulations and Wolfram Mathworld calls them a quasi-random sequence.

Saccharate

Answer 5

There is just my thought, i haven't test with code yet.

1.Divide the rectangle to grid with N x M cells, depends on variable density.

2.loop through the cell and pick a random point in the cell until it reached your target point quantity.

Jarlathus

Answer 6

Generate two random numbers in the interval [0,1] translate and scale them to your rectangle as x and y.

Marchal

Give some example in answer about what SO is asking, otherwise make this as a comment. – Waynewayolle