# How to place points on a line and quad?

This topic is 4324 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm working on a particle system and in that system I want to be able to put particles randomly on a line or on a quad. How do I do that? :) I know how to place points on a line, I just don't know how to figure out which point of the line should be subtracted by which...err..
// need to know how to figure out which of these should be on the left side:
Vector3f v = vLine2 - vLine1;
float len = v.length();
v.normalize();

rnd = random(); // random number between 0.0 - 1.0

// position of point
p = vLine1 + v * rnd * len;

edit: Think i've figured out how to know which point is the starting point of the line, simply by:
Vector3f v, start;
if( (vLine1.x*vLine1.x+vLine1.y*vLine1.y+vLine1.z*vLine1.z) <=
(vLine2.x*vLine2.x+vLine2.y*vLine2.y+vLine2.z*vLine2.z) ) {
start = vLine1;
v     = vLine2 - vLine1;
} else {
start = vLine2;
v     = vLine1 - vLine2;
}

Basically a non-square length thingy, err whatever it's called.. to see which point is furthest away from the origin.. Think it should work, right? [Edited by - angry on October 14, 2006 11:45:11 PM]

##### Share on other sites
Your code for picking a random point on the line segment looks fine, but I'm not sure what you mean about figuring out which point is the 'start point' of the segment, nor what the significance of choosing the point closest to the origin is. With no context, which endpoint of a segment is the 'start' and which is the 'end' is completely arbitrary.

As for the quad, is it rectangular, or irregular?

##### Share on other sites
Quote:
 Original post by jykYour code for picking a random point on the line segment looks fine, but I'm not sure what you mean about figuring out which point is the 'start point' of the segment, nor what the significance of choosing the point closest to the origin is. With no context, which endpoint of a segment is the 'start' and which is the 'end' is completely arbitrary.As for the quad, is it rectangular, or irregular?

I think I want the quad to be irregular, but if that's to complicated I can probably go with a rectangular one.

As for finding the start and end of the line, it's because if I don't subtract the "end" of the line with the "start" of the line, i will get a line which is negative, err. which is pointing in the opposite direction, so my points will be on the mirrored position of where they're supposed to be at..

##### Share on other sites
For a line, assuming you want an even distribution of points, it doesn't matter which end is which. The code you first posted should be fine, though the normalisation and multiplication by the length is wasting cycles (as all normalisation does is takes out the length). You can just do:
float rnd = random(); // 0 to 1Vector3 point = line.p1 + rnd * (line.p2 - line.p1);

For a general quad, I don't believe there is a way of obtaining a uniform distribution of points. There are two ways you can deal with this:

1. Make a 'bounding parallelogram' by choosing two edges as basis vectors, and create a random point within the parallelogram. Then try again if you missed your quad. I.e.:
Vector3 point;do { float rnd1 = random(), rnd2 = random(); point = quad.p1 + rnd1*(quad.p2 - quad.p1) + rnd2*(quad.p4 - quad.p1);} while(!IsInside(point,quad));

This is probably what you want, and for the worst case convex quad (a triangle) you'd only have an average of two tries.
2. Create a transform matrix from your four points such that your quad is a square under that transformation, generate random points within the square and invert the transformation. This results in a more dense distribution of points on short sides of the quad. I also can't do it just off the top of my head so you'll have to ask for more if you want to use this method.

##### Share on other sites
Quote:
 Original post by Bob JanovaMake a 'bounding parallelogram' by choosing two edges as basis vectors, and create a random point within the parallelogram. Then try again if you missed your quad.

Just make sure your "bounding parallelogram" contains the quad, I think if you take the two sides opposite the greatest angle it'll be fine there are two neighbouring sides of the quad where the sum of the angles at the ends of the side is at most \pi, those are the ones that need to be taken.

In general, to get a uniform distribution on a polygon, cut it into triangles, first select a triangle with probability proportional to its area (for a quad with two triangles measuring s1 and s2, it's an if (random()*(s1+s2) < s1) statement), then get a point in the triangle with uniform distribution (take a point in the parallelogram spanned by two sides of the triangle, and "mirror" the resulting point by substracting both its affine coordinates from 1 if it's over the {x+y <= .5} line).

edit: the <strike> tag eludes me for some reason.

1. 1
2. 2
3. 3
4. 4
frob
13
5. 5

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632169
• Total Posts
3004545

×