## gdalgorithms-list

 Re: [Algorithms] How to check if 3 points form a line? From: Christer_Ericson@Playstation.sony.com - 2001-01-03 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 floating-point 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 | | | Sent by: | | | gdalgorithms-list-admin@...| | | eforge.net | | | | | | | | | 01/03/2001 01:09 PM | | | Please respond to gdalgorithms-list| | | | |--------+---------------------------------------------> >--------------------------------------------------------------------------------------------------| | | | To: gdalgorithms-list@... | | 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 _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list ```
 Re: [Algorithms] How to check if 3 points form a line? From: Christer_Ericson@Playstation.sony.com - 2001-01-03 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" | | | Sent by: | | | gdalgorithms-list-admin@...| | | eforge.net | | | | | | | | | 01/03/2001 01:36 PM | | | Please respond to gdalgorithms-list| | | | |--------+---------------------------------------------> >--------------------------------------------------------------------------------------------------| | | | To: | | 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" To: 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 > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list ```
 Re: [Algorithms] How to check if 3 points form a line? From: Doug Chism - 2001-01-03 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: To: 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" | > | | Sent by: | > | | gdalgorithms-list-admin@...| > | | eforge.net | > | | | > | | | > | | 01/03/2001 01:36 PM | > | | Please respond to gdalgorithms-list| > | | | > |--------+---------------------------------------------> > >--------------------------------------------------------------------------- -----------------------| > | | > | To: | > | 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" > To: > 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 > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > ```
 Re: [Algorithms] How to check if 3 points form a line? From: Russ Williams - 2001-01-03 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: To: 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" | > | | Sent by: | > | | gdalgorithms-list-admin@...| > | | eforge.net | > | | | > | | | > | | 01/03/2001 01:36 PM | > | | Please respond to gdalgorithms-list| > | | | > |--------+---------------------------------------------> > >--------------------------------------------------------------------------- -----------------------| > | | > | To: | > | 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" > To: > 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 > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list ```