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

<p>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 <a href="https://en.wikipedia.org/wiki/Unit_in_the_last_place" rel="nofollow noreferrer">ulps</a>. If the resulting range overlaps 0, then I think the points are colinear within available precision.</p>

<p>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.</p>

CC BY-SA 4.0
2018-06-30T23:47:55.377Z
2018-06-30T23:47:55.377Z
Olivier
<p>What is the best way to prove if three points are linear dependent?</p>

<p>This is my current way to do it:</p>

<p>$$\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 &lt; 10^{-3}
$$</p>

<p>$\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:</p>

<p><a href="https://i.sstatic.net/SrXqi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SrXqi.png" alt="enter image description here"></a></p>

<p>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.</p>

<p>I'm searching for a scale-independent algorithm for that. </p>

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

<mathematics><2d>
Linear independence of three points
rr84
# Linear independence of three points

(Asked by: username_0 on 2018-06-30)

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:

[![enter image description here](https://i.sstatic.net/SrXqi.png)](https://i.sstatic.net/SrXqi.png)

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?

**Tags:** mathematics, 2d


---

## 1 answers

### Answer by username_1 on 2018-06-30. Score: 3

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](https://en.wikipedia.org/wiki/Unit_in_the_last_place). 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.


---

