My question is in the context of a line segment and not in the context of a line which has infinite length.
Lets say I have two points in 2d which represent for me a line segment and I got another point which is not on the line segment. How do I find the point on the line segment which is the closest to the point that is not on the line segment.
P.S. I have seen couple of similar questions about that but all in the context of line and not line segment.
Thank you in advance.
$\endgroup$ 24 Answers
$\begingroup$Let the two endpoints of the segment be $A$ and $B$, and let $P$ be your point.
Write
$$ f(t) = (1-t)A + t B - P $$That's the vector between $P$ and a point that's $t$ of the way from $A$ to $B$. (When $t = 0$, you're at $A$; when $t = 1$, you're at $B$.)
Now let$g(t) = \| f(t) \|^2$, which is the squared length of that vector. You're looking for the value of $t$ that minimizes this. I use the squared length because it makes the algebra nicer.
Do algebra:\begin{align} g(t) & = \|f(t)\|^2 \\ &= ((1-t)A + t B - P)^T \cdot (1-t)A + t B - P \\ &= (t (B-A) + A-P)^T \cdot (t (B-A) + (A-P)) \end{align}Let $v = B-A$ and $u = A - P$ to get\begin{align} g(t) & = \|f(t)\|^2 \\ &= (t (B-A) + A-P)^T \cdot (t (B-A) + (A-P))\\ &= (t v + u)^T \cdot (t v + u)\\ &= t^2 \|v\|^2 + 2t (v \cdot u) + \|u\|^2 \end{align}so\begin{align} g'(t) & = 2t \|v\|^2 + 2 (v \cdot u) = 2t (v \cdot v) + 2 (v \cdot u). \end{align}Set to zero and solve to get$$ t = -\frac{v \cdot u}{v \cdot v}. $$
You compute this value $t$, and if it's between $0$ and $1$, then the closest point is $(1-t)A + t B$. If it's not, you compute $g(0)$ and $g(1)$, and if $g(0)$ is smaller, the answer is $A$; otherwise it's $B$.
The key idea here is that "squared distance to $P$" is a nice function of position along the segment $AB$ (i.e., of the value $t$). You now have a smooth real-valued function $g$ of a real argument $t$ in the unit interval. The min of such a function either occurs at a value $t$ with $g'(t) = 0$ or at one of the two endpoints, $t = 0$ or $t = 1$.
Because this particular function has only one min, you know that if you find a critical point, it's a min, and if it's in the unit interval, you're done -- the values at the endpoints WILL be larger, so you don't need to check them. On the other hand, if the min lies outside the interval, then you have to check whether your function's smaller at one end than at the other.
$\endgroup$ 3 $\begingroup$I know this is a math exchange but since I implemented John Hughes's answer in javascript here it is:
const _zero2D = [0, 0]
function closestPointBetween2D(P, A, B) { const v = [B[0] - A[0], B[1] - A[1]] const u = [A[0] - P[0], A[1] - P[1]] const vu = v[0] * u[0] + v[1] * u[1] const vv = v[0] ** 2 + v[1] ** 2 const t = -vu / vv if (t >= 0 && t <= 1) return _vectorToSegment2D(t, _zero2D, A, B) const g0 = _sqDiag2D(_vectorToSegment2D(0, P, A, B)) const g1 = _sqDiag2D(_vectorToSegment2D(1, P, A, B)) return g0 <= g1 ? A : B
}
function _vectorToSegment2D(t, P, A, B) { return [ (1 - t) * A[0] + t * B[0] - P[0], (1 - t) * A[1] + t * B[1] - P[1], ]
}
function _sqDiag2D(P) { return P[0] ** 2 + P[1] ** 2 }Suppose the line segment is on the $x$-axis with endpoints at $(0,0)$ and $(d,0)$. Let $(x,y)$ be the arbitrary point. It is easy to see that if $0\le x \le d$ then the point closest is the projection down onto the segment. Suppose that $x>d$ then you should be able to convince yourself that the point $(d,0)$ is closest. A similar argument for $x<0$ can be made.
This problem is not typically asked because the infinite line is slightly more involved.
$\endgroup$ $\begingroup$Let Q be the outside point and (A,B) be the end-points of the given line segment.
Find projection point P. This is intersection of AB and a line perpendicular to AB through Q having negative reciprocal slope of AB.
Project the three points on x-axis and let $(xA,xB,xP)$ be their x-coordinates.
Arrange the three coordinates in an ascending order with their respective labels.
If $(xP< xA < xB)$ then A is nearest to Q;
If $(xA< xP < xB)$ then P is nearest to Q;
If $(xA< xB < xP)$ then B is nearest to Q.
$\endgroup$ 1
