PDA

View Full Version : How to test if three vertices are Co-Linear



GregMalick
08-22-2004, 03:03 AM
The title says it all... What's the simplest way to test if 3 vertices are in a straight line? ;)

faulknermano
08-22-2004, 05:46 AM
maybe this will work but not sure:



a = pointinfo(points[1]);
b = pointinfo(points[2]);
c = pointinfo(points[3]);

vec1 = b - a;
vec2 = c - a;

vec1 = normalize(vec1);
vec2 = normalize(vec2);

if(vec1 == vec2)
itiscolinear();
else
itisNotcolinear();

Lightwolf
08-22-2004, 06:09 AM
faulknermano, your code will only check if vec1 and vec2 are parallel direction vectors.

Try this:



a = pointinfo(points[1]);
b = pointinfo(points[2]);
c = pointinfo(points[3]);

// a is the origin, b the second point on the line, c is being tested

dir = b - a;
dir = normalize(dir);

//d_vec = c - a;
//distance = sqrt(d_vec[0] * d_vec[0] + d_vec[1] * d_vec[1] + d_vec[2] * d_vec[2]);
distance = vmag(c - a); // much nicer than the stuff above :)

ext_point = a + dir * distance;

if(c == ext_point)
itiscolinear();
else
itisNotcolinear();

I'm not sure about the syntax though, I ain't much of an LScripter.

Basically:
a is the "origin" of the line
dir the direction vector of the line.
distance is the scalar distance of any point on the line to the origin.
This, any point on the line conforms to:
any_point = a + dir * distance;

You might have to add a bit of a tolerance for your == checking though, due to the nature of floating point variabales.

Cheers,
Mike

faulknermano
08-22-2004, 06:41 AM
Originally posted by Lightwolf
faulknermano, your code will only check if vec1 and vec2 are parallel direction vectors.


thanks for the correction. it was a shot in dark. :)

Lightwolf
08-22-2004, 06:42 AM
No probs, I had to think a bit about it as well, especially how to make it understandable ;)

...now I just hope it works ;)

Cheers,
Mike

Lightwolf
08-22-2004, 06:46 AM
Just to make this a bit easier to read:



a = pointinfo(points[1]);
b = pointinfo(points[2]);
c = pointinfo(points[3]);

dir = normalize(b- a);
distance = vmag(c - a);

ext_point = a + dir * distance;

if(c == ext_point)
itiscolinear();
else
itisNotcolinear();

SCNR ;)

Cheers,
mike

Lynx3d
08-22-2004, 08:36 AM
May i suggest yet another possibility? :D

Basically Gram-Schmidth-Orthogonalization...
i'll use generic terms:

again a and b form a line, c is tested to be on that line.
v1 = b-a
e1 = normalize(v1)
v2 = c-a
f2 = v2 - e1*VDOT(e1, v2) // VDOT = scalar product

f2 is now perpendicular to v1.
its length (vmag() apparently in LScript?) is the distance to the line so you can check one number against a tolerance...

you could also do it based on the angle, like
v1 = b-a
v2 = c-a
e1 = normalize(v1)
e2 = normalize(v2)
cosine = ABS( VDOT(e1, e2) ) //ABS is the absolute value, i.e. removed sign
if (cosine > cos(tolerance angle) ) => colinear

-edit-
note that can always come into troubles if two points have the same coordinates, because normalization on a zero-vector will fail
-edit2-
oops, the cosine of course has to be greater than the tolerance value :D

Lightwolf
08-22-2004, 08:41 AM
I guess that would be close to evaluation the angle between b->a and b->c or something like that.

vmag() in LScript s basically sqrt(x*x + y*y + z*z) or sqrt(vdot(a,a))

The nice thing about the first approach you posted is that it can return the closest distance of the point to the line as well, shich is quite useful in cases...

cheers,
Mike - who should really read up his math again ;)

GregMalick
08-22-2004, 10:58 AM
Wow... I wake up and see all this great stuff! Great and useful code! I'm sure I won't be the only LScripter who learns from this.

Thanks for the great help! :D :D :D

I'll post the plugin I'm making when I'm done.

GregMalick
08-25-2004, 10:11 AM
As promised, you can get my plugin here. (http://www.spinquad.com/forums/showthread.php?s=&threadid=2792) :)

Lightwolf
08-25-2004, 10:20 AM
Hi Greg,
(as I said on SpinQuad...) very cool, and very useful. Thanks for sharing it.

Cheers,
Mike

GregMalick
08-25-2004, 10:30 AM
Originally posted by Lightwolf
Thanks for sharing it.
It's all a result of you guys sharing your knowledge on co-linear points. :D


GREAT COMMUNITY!

Lightwolf
08-26-2004, 09:06 PM
GREAT COMMUNITY!
Hah, and a great new vbulletin version with a nice code box :)

me likes!;
Cheers,
Mike