find which two points an arbitrary point is nearest to

Question

I have a line segment of connected points (a path in 2D), and a point $P$ that is not calculated based on this segment, although I can guarantee that the point will be placed along the path.

Based on this, I would like to calculate which line segment $P$ resides within. In the attached example, we assume three points in the segment (theoretically there could be much more), and hopefully the calculation will tell us that $P = (x_P,y_P)$ is between $B = (x_B,y_B)$ and $C = (x_C,y_C)$, rather than between $A = (x_A,y_A)$ and $C$.

Answer 1

Here's a solution.

If you're given a set of points $S = \{p_1, p_2, \ldots, p_n\}$, then there are $n \choose 2$ segments made of pairs of points from $S$. If all the points in $S$, as well as $P$, are in $\mathbb{R}^2$ then you can compute the cross product of the vector $\vec{u}_{ij} := p_j - p_i$ and the vector $\vec{v}_i := P - p_i$, for every $i > j$ and $1 \le i,j \le n$. The segment $P$ belongs to will be the one for which that cross product (which is just a real number for vectors in $\mathbb{R}^2$) is zero (because the segments $\overline{p_ip_j}$ and $\overline{p_iP}$ will then be parallel).

The cross product is, of course, defined by $\vec{u} \times \vec{v} = u_x\,v_y - u_y\,v_x$.

Answer 2

From wikipedia:

In a metric space M with metric d, the triangle inequality is a requirement upon distance: $$ d(x, z) \le d(x, y) + d(y, z) $$

Intuitively we find that $ d(B, C) = d(B, P) + d(P, C) $ happens if and only if $P$ forms a straight line with $B$ and $C$, or in more proper terms:

$P \in \{v\in V : v = k(C - B) + C\}, k \in R$

I hope this clears some doubts. This answer'd need some proof to back it up, however.