best method of evenly distributing points on a quad
Author
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
Why not something like this?
/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]
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);} /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]
Quote:Original post by zedzeekSplit 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.
im wanting to evenly distribute points on a quad but without any visable pattern
whats the best method?
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.---
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)
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)
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.
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.
Quote:Original post by someusernameThe OP was asking for the points to be evenly distributed in the quad. What you suggest does not give a uniform distribution of points.
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
Quote:Original post by ReitaThis 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).
Split the quad into N smaller quads [...] Within each of those sub-quads you pick a randomly generated point.
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
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
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).
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
