Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: Christer_Ericson@Playstation.sony.com  20010103 22:52:07

Three points A, B, and C, are collinear if and only if the triangle ABC has zero area. Since e.g. AB cross AC = 1/2*Area(ABC) you can indeed compute the cross product and see if its magnitude is zero. Of course, you don't actually need to find the magnitude to find out if it's zero, you can just check that all components are zero instead, just as you suggest. The only problem is that since there will inevitably be floatingpoint rounding errors, they won't be exactly zero, so you want to compare with some small epsilon value, eg: const float EPSILON = 0.00001f; // or some other small value v = CrossProduct(vec0  vec1, vec2  vec1); if (fabs(v.x) > EPSILON  fabs(v.y) > EPSILON  fabs(v.z) > EPSILON) // not collinear (triangle) else // collinear (line, or point) If fabs() is expensive on your platform (unlikely) you can write this as: if (v.x*v.x > EPSILON ...) Christer Ericson SCEA, Santa Monica +>   Kasper <k.j.wessing@...>    Sent by:    gdalgorithmslistadmin@...   eforge.net          01/03/2001 01:09 PM    Please respond to gdalgorithmslist    +> >    To: gdalgorithmslist@...   cc:   Subject: [Algorithms] How to check if 3 points form a line?  > Hi all, I'm trying to making a convex hull (based on a quick hull algorithm by Tim Lambert). Instead of using triangles I use polygons, every thing was ok until I tried a simple cube where every side is contains 4 squares. I know that the all the points have different locations. So I wand to check if 3 point (in three space) forms a line? On this moment I do: if (CrossProduct(vec0  vec1, vec2  vec1) != Vector3(0,0,0)) // line else // triangle. Is this the right way? And if someone know a place where I can get information about creating a mesh out of planes that will be mostly helpful(maybe portals). Thx, Kas  Kasper J. Wessing  k.j.wessing@... http://members.ams.chello.nl/k.j.wessing REMEMBER: IF IT LOOKS LIKE A LOT OF WORK  AVOID IT. TERRY GILLIAM _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: Christer_Ericson@Playstation.sony.com  20010103 22:58:05

No, that is not correct. Let A=(0,0,0), B=(1,1,1) and C=(1,0,0). AB=(1,1,1), AC=(1,0,0), and AB dot AC = 1, but A, B, and C are not collinear. So, you cannot use a dot product (alone) to test for collinearity. Christer Ericson SCEA, Santa Monica +>   "Doug Chism" <dchism@...>    Sent by:    gdalgorithmslistadmin@...   eforge.net          01/03/2001 01:36 PM    Please respond to gdalgorithmslist    +> >    To: <gdalgorithmslist@...>   cc:   Subject: Re: [Algorithms] How to check if 3 points form a line?  > You could use a dot product to save cycles over a cross product. Also you should probably compare the dot to some epsilon value since you may get some roundoff error. The dot of the two vectors will be one or negative one if they lie on the same line. Doug Chism  Original Message  From: "Kasper" <k.j.wessing@...> To: <gdalgorithmslist@...> Sent: Wednesday, January 03, 2001 4:09 PM Subject: [Algorithms] How to check if 3 points form a line? > Hi all, > > I'm trying to making a convex hull (based on a quick hull algorithm by > Tim Lambert). > Instead of using triangles I use polygons, every thing was ok until I > tried a simple cube where every side is contains 4 squares. > > I know that the all the points have different locations. > > So I wand to check if 3 point (in three space) forms a line? > > On this moment I do: > > if (CrossProduct(vec0  vec1, vec2  vec1) != Vector3(0,0,0)) > // line > else > // triangle. > > Is this the right way? > > And if someone know a place where I can get information about creating a > mesh out of planes that will be mostly helpful(maybe portals). > > Thx, > Kas > >  > Kasper J. Wessing  k.j.wessing@... > http://members.ams.chello.nl/k.j.wessing > > REMEMBER: IF IT LOOKS LIKE A LOT OF WORK  AVOID IT. > TERRY GILLIAM > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: Doug Chism <dchism@d...>  20010103 23:07:35

Whoops, I guess they would have to be normals for that dot product to work sorry. Its expensive to normalize vectors so forget doing it that way. Doug Chism  Original Message  From: <Christer_Ericson@...> To: <gdalgorithmslist@...> Sent: Wednesday, January 03, 2001 5:54 PM Subject: Re: [Algorithms] How to check if 3 points form a line? > > > No, that is not correct. > > Let A=(0,0,0), B=(1,1,1) and C=(1,0,0). AB=(1,1,1), AC=(1,0,0), and > AB dot AC = 1, but A, B, and C are not collinear. So, you cannot > use a dot product (alone) to test for collinearity. > > > Christer Ericson > SCEA, Santa Monica > > > > > +> >   "Doug Chism" <dchism@...>  >   Sent by:  >   gdalgorithmslistadmin@... >   eforge.net  >    >    >   01/03/2001 01:36 PM  >   Please respond to gdalgorithmslist >    > +> > >  >   >  To: <gdalgorithmslist@...>  >  cc:  >  Subject: Re: [Algorithms] How to check if 3 points form a line?  > >  > > > > > You could use a dot product to save cycles over a cross product. Also you > should probably compare the dot to some epsilon value since you may get > some > roundoff error. The dot of the two vectors will be one or negative one if > they lie on the same line. > > Doug Chism > >  Original Message  > From: "Kasper" <k.j.wessing@...> > To: <gdalgorithmslist@...> > Sent: Wednesday, January 03, 2001 4:09 PM > Subject: [Algorithms] How to check if 3 points form a line? > > > > Hi all, > > > > I'm trying to making a convex hull (based on a quick hull algorithm by > > Tim Lambert). > > Instead of using triangles I use polygons, every thing was ok until I > > tried a simple cube where every side is contains 4 squares. > > > > I know that the all the points have different locations. > > > > So I wand to check if 3 point (in three space) forms a line? > > > > On this moment I do: > > > > if (CrossProduct(vec0  vec1, vec2  vec1) != Vector3(0,0,0)) > > // line > > else > > // triangle. > > > > Is this the right way? > > > > And if someone know a place where I can get information about creating a > > mesh out of planes that will be mostly helpful(maybe portals). > > > > Thx, > > Kas > > > >  > > Kasper J. Wessing  k.j.wessing@... > > http://members.ams.chello.nl/k.j.wessing > > > > REMEMBER: IF IT LOOKS LIKE A LOT OF WORK  AVOID IT. > > TERRY GILLIAM > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > 
From: Russ Williams <russ@al...>  20010103 23:15:59

In that example, though, AB is sqrt(3). With unit vectors, the dot will be +/ 1.0 if the vectors are (anti)parallel and hence the points are collinear. Of course, finding AB and AC makes it rather expensive for an arbitrary set of points. The cross product is a much better way, and the test for the result being close to zero can be done conveniently with integer instructions  mask off the top bit (to remove the sign) and then compare the exponent to a threshold magnitude. You end up having to use (1 / 2^n) as epsilon, but it might be a win on some systems.  Russ  Original Message  From: <Christer_Ericson@...> To: <gdalgorithmslist@...> Sent: Wednesday, January 03, 2001 10:54 PM Subject: Re: [Algorithms] How to check if 3 points form a line? > > > No, that is not correct. > > Let A=(0,0,0), B=(1,1,1) and C=(1,0,0). AB=(1,1,1), AC=(1,0,0), and > AB dot AC = 1, but A, B, and C are not collinear. So, you cannot > use a dot product (alone) to test for collinearity. > > > Christer Ericson > SCEA, Santa Monica > > > > > +> >   "Doug Chism" <dchism@...>  >   Sent by:  >   gdalgorithmslistadmin@... >   eforge.net  >    >    >   01/03/2001 01:36 PM  >   Please respond to gdalgorithmslist >    > +> > >  >   >  To: <gdalgorithmslist@...>  >  cc:  >  Subject: Re: [Algorithms] How to check if 3 points form a line?  > >  > > > > > You could use a dot product to save cycles over a cross product. Also you > should probably compare the dot to some epsilon value since you may get > some > roundoff error. The dot of the two vectors will be one or negative one if > they lie on the same line. > > Doug Chism > >  Original Message  > From: "Kasper" <k.j.wessing@...> > To: <gdalgorithmslist@...> > Sent: Wednesday, January 03, 2001 4:09 PM > Subject: [Algorithms] How to check if 3 points form a line? > > > > Hi all, > > > > I'm trying to making a convex hull (based on a quick hull algorithm by > > Tim Lambert). > > Instead of using triangles I use polygons, every thing was ok until I > > tried a simple cube where every side is contains 4 squares. > > > > I know that the all the points have different locations. > > > > So I wand to check if 3 point (in three space) forms a line? > > > > On this moment I do: > > > > if (CrossProduct(vec0  vec1, vec2  vec1) != Vector3(0,0,0)) > > // line > > else > > // triangle. > > > > Is this the right way? > > > > And if someone know a place where I can get information about creating a > > mesh out of planes that will be mostly helpful(maybe portals). > > > > Thx, > > Kas > > > >  > > Kasper J. Wessing  k.j.wessing@... > > http://members.ams.chello.nl/k.j.wessing > > > > REMEMBER: IF IT LOOKS LIKE A LOT OF WORK  AVOID IT. > > TERRY GILLIAM > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
Sign up for the SourceForge newsletter:
No, thanks