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? ;)

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();

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

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. :)

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

...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

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

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 ;)

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.

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

(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!

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

Hah, and a great new vbulletin version with a nice code box :)

me likes!;

Cheers,

Mike

Powered by vBulletin® Version 4.2.3 Copyright © 2019 vBulletin Solutions, Inc. All rights reserved.