Linear independence of three points

Question

What is the best way to prove if three points are linear dependent?

This is my current way to do it:

$$\mathbf{v_a} = \mathbf{b}-\mathbf{a} \\ \mathbf{v_b} = \mathbf{c}-\mathbf{a} \\ \mathbf{v_c} = \begin{pmatrix} -\mathbf{v_{a,y}} \\ \mathbf{v_{a,x}} \end{pmatrix} \\ \phi = \mathbf{\hat{v}_c} \cdot \mathbf{\hat{v}_b} \\ \phi < 10^{-3} $$

$\phi$ is the $arccos$ of the real angle between the two vectors. This works good if the polygon or the three points of the polygon have well defined distances. But what if the polygon looks like this:

The distance between $P_0$ and $P_1$ is much bigger than between $P_1$ and $P_2$. $P_0$, $P_1$ and $P_2$ are of clearly not linear dependent.

I'm searching for a scale-independent algorithm for that.

Do you have any ideas or a reference to a paper I can read about it?

Answer 1

Normalize $v_a$ and $v_b$ and your algorithm should no longer depend on the length of the edges, unless you consider numerical stability.

As for the "best way", I'm not sure there's a much better algorithm but I would try a better definition of the tolerance. Instead of a fixed value, I would use differentials to compute the change in the angle for a change of the inputs of a few ulps. If the resulting range overlaps 0, then I think the points are colinear within available precision.

Whether that complexity is justified depends on what you're doing with this, which you did not specify. A constant could be fine or even the best choice for some uses.