Unreliable algorithm for determine if points lie along a line?

346 Views Asked by At

So lets say I have some points $A,B,C$.

A method I have been shown for determining if the lie along a straight line is thus:
$\mathrm{If}\space|AC|=|AB|+|BC| \space\mathrm{then\space A,B\space and\space C\space lie\space on\space a\space straight\space line. }$

However, this doesn't seem like a very reliable method to me. It seems like a situation such as this would create a false positive. enter image description here

If this is not the case, how do you prove that $|AB|+|BC|\neq|AC|$ in all cases if they points are not on a straight line?

If this case will indeed cause the algorithm to fail, what reliable algorithm can I use?

Thanks...

EDIT:: Whenever I built a triangle that would cause this algorithm to fail, (ie, a=10,b=5,c=5 and others) I get $cos{C}=1$, implying a straight, line? How can one prove this is always the case?

2

There are 2 best solutions below

0
On

A little extension makes the algorithm work :

Consider $|AB|$ , $|AC|$ and $|BC|$. Then, C is on the line AB , if and only if the greatest of the three numbers is the sum of the others. In Particular, if C = A or C = B, then C is trivially always on the line AB.

1
On

The equality $|AB| + |BC| = |AC|$ holds if and only if point $B$ lies on the segment $AC$.

Still, this is a bad basis for a practical algorithm. If you implement this, you'll have to calculate three square roots, which is slow. Not to mention that this just looks bad.

A good way to determine whether or not points $A$, $B$ and $C$ are collinear is purely linear. It goes like this.

Calculate coordinates of vectors $\vec{AB}$ and $\vec{BC}$: $\vec{AB} = (x_1, y_1, z_1)$ and $\vec{AC} = (x_2, y_2, z_2)$. Now, points $A$, $B$ and $C$ are collinear if and only if all the equalities below are true: $$ \begin{align*} x_1 y_2 &= x_2 y_1 \\ y_1 z_2 &= y_2 z_1 \\ z_1 x_2 &= z_2 x_1 \end{align*} $$