[algogeeks] Re: Testing if 3 points form a triangle
On Jun 4, 10:56 pm, Feng [EMAIL PROTECTED] wrote: Hi Kunzmilan, thanks for your idea of using distance matrices. But one of my friends came up with a seemly counter-example: Take 3 collinear points in 2D: (0,0), (1,0), (2,0). The distance matrix is: 0 1 4 1 0 1 4 1 0, whose eigenvalues are -4, -0.4495, 4.4495. It means that they form a 2D shape, but they make a line (1D shape). Is there anything wrong in it? I tried to answer the question five days ago, but my answer did not appeared. The eigenvalue a at straight chains is produced by the reflexion plane (elements of the of the eigenvector are symmetrical to the center of the chain) and its rotation tensor b = (a + W/2) = [\sum d^4 - 3/4 W^2]^1/2, where W is The Wiener index (half of the sum of distance matrix elements. The sum of squared eigenvalues must be equal to the trace of the squared matrix. Solving the quadratic equation gives four eigenvalues (including zero) as W/2 +/- (b or W/2). kunzmilan --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
On Jun 5, 1:45 am, Feng [EMAIL PROTECTED] wrote: Hi BiGYaN, triangle is a 2D object which can be formed by any 3 non- collinear points. It can exist in 4D, just like a point existing in 3D. On May 31, 2:11 am, Victor Carvalho [EMAIL PROTECTED] wrote: Feng, how can form a triangle in four dimensions??? 2007/5/29, BiGYaN [EMAIL PROTECTED]: Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger -- Victor Carvalho Computação - UFC GELSoL - Grupo de Estudos de Linux e Software Livre E-Jr Empresa Júnior de Computação I never had a problem with a triangle in 4D !! You probably aimed it @ Victor. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
Hi BiGYaN, triangle is a 2D object which can be formed by any 3 non- collinear points. It can exist in 4D, just like a point existing in 3D. On May 31, 2:11 am, Victor Carvalho [EMAIL PROTECTED] wrote: Feng, how can form a triangle in four dimensions??? 2007/5/29, BiGYaN [EMAIL PROTECTED]: Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger -- Victor Carvalho Computação - UFC GELSoL - Grupo de Estudos de Linux e Software Livre E-Jr Empresa Júnior de Computação --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
use the cross product to examine whether they're collinear. points A,B,C: AB*BC =? 0 On 5/27/07, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
Feng, how can form a triangle in four dimensions??? 2007/5/29, BiGYaN [EMAIL PROTECTED]: Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger -- Victor Carvalho Computação - UFC GELSoL - Grupo de Estudos de Linux e Software Livre E-Jr Empresa Júnior de Computação --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
Just test whether they are collinear or not i.e. get the slopes, m1 from 1st and 2nd point m2 from 2nd and 3rd point if m1==m2 then they do not form a triangle else they do Computing the area of the triangle and testing for 0 might also work but I feel that the computation will be bigger --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
In 3D, we can test |(p2-p1)*(p3-p1)|==0, where p1,p2 and p3 are vectors. On 5月27日, 上午7时22分, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
in 3D,we can test |(p2-p1)*(p3-p1)|==0,where p1,p2,p3 are 3D-vectors that represent the three points. in n-dimension,i think we can let A=(a1,a2,...,an)=p2-p1, and B=(b1,b2,...,bn)=p3-p1, and test every elements of the matrix (ATB- BTA). That is ai*bj-aj*bi. On 5月27日, 上午7时22分, Feng [EMAIL PROTECTED] wrote: Hi all! Given 3 points in 3D, what is the fast and numerically stable way to test if they form a triangle? I am thinking computing the determinant of the square matrix formed by the 3 points and testing if the determinant is nonzero. But I am not sure. What about the case for high dimensions, i.e. 4D, 5D ... Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
