Sign in to follow this  
zedzeek

best method of evenly distributing points on a quad

Recommended Posts

im wanting to evenly distribute points on a quad but without any visable pattern whats the best method? ie the following is not acceptable for ( i=0; i<width; i++ ) for ( j=0; j<width; j++ ) pointI = i + random(); pointJ = j + random(); ta zed

Share this post


Link to post
Share on other sites
Why not something like this?
for (int i = 0; i < numpoints; ++i)
{
int x = random (origin_x, origin_x + width);
int y = random (origin_y, origin_y + height);

plot_point (x, y);
}
random (...) returns a random number in the given range.

/edit: Note that I am not saying this is the best method.
/edit2: I fixed a silly error in the code.

[Edited by - deavik on November 27, 2005 8:40:24 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by zedzeek
im wanting to evenly distribute points on a quad but without any visable pattern
whats the best method?
Split the quad ABCD into two triangles ABC and BDC. Pick one of the triangles randomly, but biased by triangle area (i.e. if ABC has twice the area of BDC, it is twice as likely to be picked). Lets say you picked ABC. Now you have a reduced problem: that of finding a point evenly distributed in the triangle ABC.

The following entry from the comp.graphics.algorithms FAQ describes how you go about solving the reduced problem:

---
Subject 6.05: How can I generate a random point inside a triangle?

Use barycentric coordinates (see item 53) . Let A, B, C be the
three vertices of your triangle. Any point P inside can be expressed
uniquely as P = aA + bB + cC, where a+b+c=1 and a,b,c are each >= 0.
Knowing a and b permits you to calculate c=1-a-b. So if you can
generate two random numbers a and b, each in [0,1], such that
their sum <=1, you've got a random point in your triangle.
Generate random a and b independently and uniformly in [0,1]
(just divide the standard C rand() by its max value to get such a
random number.) If a+b>1, replace a by 1-a, b by 1-b. Let c=1-a-b.
Then aA + bB + cC is uniformly distributed in triangle ABC: the reflection
step a=1-a; b=1-b gives a point (a,b) uniformly distributed in the triangle
(0,0)(1,0)(0,1), which is then mapped affinely to ABC.
Now you have barycentric coordinates a,b,c. Compute your point
P = aA + bB + cC.

Reference: [Gems I], Turk, pp. 24-28.
---

Share this post


Link to post
Share on other sites
to be honest, I've never noticed any visible patterns in pseudorandom generated sequences... (not that I ever tried to find any...) Of course, I don't know what implementation of random() you're using but is it imperative that you use some other way?

I suggest you make a loop in which you'll be generating random numbers, say around 20000~30000 and find their statistical mean and variance. If these numbers seem to vary a lot and they don't match up with their equivalents of a uniform distribution, then look for some other way to generate numbers.

The variance of your list can be calculated by: SUM(i=1...n){ (x(i)-mean)^2 }/(n-1). This should be around 0.0833 (that's what I'm getting)

[edit: the numerical examples are for random numbers in the range {0,...,1}]

The mean of your list of numbers (of course) is (1/n)*(their sum) and it should be as close to .5 as possible

As for the barycentric coordinates suggested in the previous post, I think it is indeed the best approach, however you don't have to split into two trianges.
Find 4 numbers w1,w2,w3,w4 (imagine these a 'weight' for each vertex of the quad) that are all positive, in the range {0., 1.} with sum == 1. Then, if v1,v2,v3,v4 are vectors representing the positions of the vertices of the quad, the point v is guaranteed to be a point IN the quad:
v = w1*v1 + w2*v2 + w3*v3 + w4*v4

The numbers (w1,w2,w3,w4) are V's barycentric coordinates for that quad.
(this works for any number of vertices with the assumption -of course- that the restrictions on w(i) hold true)

Share this post


Link to post
Share on other sites
Let's say you have a quad with a given side-length of A units. You want to evenly distribute N points on its surface.

Split the quad into N smaller quads, e.g. by splitting each side of the original quad into sqrt(N) parts and then forming a raster. After this you get N quads with side-lengths of A / sqrt(N) (if sqrt(N) is a whole number).

Within each of those sub-quads you pick a randomly generated point.

This method is known as "stratified sampling" of an area and google should give you more information on the subject.

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
As for the barycentric coordinates suggested in the previous post, I think it is indeed the best approach, however you don't have to split into two trianges.
Find 4 numbers w1,w2,w3,w4 (imagine these a 'weight' for each vertex of the quad) that are all positive, in the range {0., 1.} with sum == 1. Then, if v1,v2,v3,v4 are vectors representing the positions of the vertices of the quad, the point v is guaranteed to be a point IN the quad:
v = w1*v1 + w2*v2 + w3*v3 + w4*v4
The OP was asking for the points to be evenly distributed in the quad. What you suggest does not give a uniform distribution of points.

Share this post


Link to post
Share on other sites
Quote:
Original post by Reita
Split the quad into N smaller quads [...] Within each of those sub-quads you pick a randomly generated point.
This too doesn't work, because it also does not produce a uniform distribution of the points (in that a larger "sub-quad" should have proportionally more points in it, which this approach does not provide).

Share this post


Link to post
Share on other sites
either pick random points or better, use stratified sampling like this

given
p1,...,p4 points of quad in cc order

Vector3d side1 = p2 - p1;
Vector3d side2 = p4 - p1;


//stratify strat1 along side1 and strat2 along side2
//total number of samples strat1*strat2

dSide1 = magnitude(side1)/strat1;
dSide2 = magnitude(side2)/strat2;

for(i = 0; i < strat1; i++) {
for(j = 0; j < strat2; j++) {
random_point = p1 + (i + random())*dSide1 + (j + random())*dSide2;
}
}


where random() returns a random variable from 0 to 1.

the basic thing is if you have n samples dubdivide into n subrectangles with equal area and place one sample in each. the obove method is common but requires n to be a perfect square. if you didn't want this, the best way in my opinion is simply sample like above until the nearest perfect square to n. then sample the rest of the points using a random(unstratified) sampling. this method should give no visible patterns. for basic random sampling it's obvious:

Vector3d side1 = p2 - p1;
Vector3d side2 = p4 - p1;

for(i = 0; i < numberofsamples; i ++)
random_point = p1 + random()*side1 + random()*side2;
}

but stratified sampling is the way to go for many problems, what do you need it for?

Tim

Share this post


Link to post
Share on other sites
Quote:
Original post by zedzeek
im wanting to evenly distribute points on a quad but without any visable pattern


That all depends on the balance between "evenly distributed" and "visible pattern", and computation time etc.

A different way to what's been written before is to first distribute the points as evenly as possible (e.g. use some iterative approach where you dump all the points in at random and then incrementally move them apart from each other until things settle down). Then after that's done apply some random offsets to the positions (wrapping around the edges) - the amount depends on your application - of course the more randomness you apply the less even will be the distribution (up to a point).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You may also want to look into quasi-random number generators. Psuedo-random number sequences (the sequences calculated by usual random number generators) try to maintain independence between numbers generated in the sequence. For evenly covering an area this can be undesirable since it means there is a chance of sample points clustering around certain areas and not being placed in other areas. A quasi-random sequence allows numbers in the sequence to not be independent of each other, to attempt to more evenly cover the sample space.

Share this post


Link to post
Share on other sites
Quote:
A different way to what's been written before is to first distribute the points as evenly as possible (e.g. use some iterative approach where you dump all the points in at random and then incrementally move them apart from each other until things settle down). Then after that's done apply some random offsets to the positions (wrapping around the edges) - the amount depends on your application - of course the more randomness you apply the less even will be the distribution (up to a point).


this is what i have at present but its not the quickest (esp with large point sets)
ill look further into barycentric coordinates (as im comfortable with them) as Christer Ericson suggested.
i'll try out a couple of the other suggestions as well
thanks everyone anyways much appreciated

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this