Efficient way to which is the point in between of three points

Question

I have three points $(x_1, y_1),~ (x_2, y_2),~ (x_3, y_3)$ that are on the same line. How to efficiently find which is the point in between.

Example

Also, is there any efficient way to check if 3 random points are on the same line and then find the point in between?

Answer 1

Find three distances and use the fact that the distance between end points is the greatest. You have points $A(x_1,y_1), B(x_2, y_2), C(x_3, y_3)$. The square of distance between $A$ and $B$ is $$(x_1-x_2)^2+(y_1-y_2)^2$$ You can use squared distance to simplify calculations.

To check if three points are on one line, there is a simple formula derived from area of a triangle formed by three points.: $$(y_3-y_1)(x_2-x_1)-(x_3-x_1)(y_2-y_1)$$ This is double of the area. If it's zero, the points are on one line.

Answer 2

Once you know that the three points are aligned, compute $$ t={x_3-x_2\over x_1-x_2}\quad \text{(or}\quad t={y_3-y_2\over y_1-y_2}\quad \text{if $x_1-x_2\approx0$).} $$ Then:

• if $t>1$ then $P_2$ lies between $P_1$ and $P_3$;
• if $t<0$ then $P_1$ lies between $P_2$ and $P_3$;
• if $0<t<1$ then $P_3$ lies between $P_1$ and $P_2$.

Answer 3

Sort the $x$ and sort the $y$ (sorting three items takes three comparisons). Consider the axis on which the difference between the extremes is the largest, and return the point with the intermediate coordinate.

Both axis need to be compared to avoid degenerate cases. This method is the most numerically robust.

---

Finding if points are aligned is more challenging because the analytical criterion, $$P_1P_2\times P_2P_3=0$$ will fail in virtually all cases for numerical reasons. A more reasonable approach is to set a tolerance on the distance of one point to the line of support of the two others. And for best accuracy, the line should be built on the most far apart points, as found above.

A better formula is $$\|P_1P_2\times P_2P_3\|\le\|P_1P_2\|\,\delta.$$