Find a point on a line segment which is the closest to other point not on the line segment

Question

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.

If you understood the technique for the point-line case, here it is just the same. Write down a parametrization of the segment, minimize a squared distance got from the Pythagorean theorem. — Jack D'Aurizio, Mar 19 '17 at 16:16
Project the third point $P$ onto the line formed by continuing the line segment $AB$, call the resulting point $P'$. The closest point is either $A, B,$ or $P'$. Compare the distances to see which is the closest. — Eman Yalpsid, Mar 19 '17 at 16:16

score 15 · Answer 1 · edited Jul 01 '20 at 21:23

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.

I think you have two mistakes here. t should be -(vu)/(vv) and there should be additional function d(t)=(1-t)A+tB, because d(t) is the answer, not f(t) — sheerun, Oct 29 '18 at 16:58
thanks I added an answer with a javascript implementation of this answer. All cases seem to work! — Rivenfall, Feb 27 '19 at 14:12

Rivenfall · Answer 2 · 2020-02-11T17:16:49.543

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 }

You don't need the g0, g1 variables. just check if t is smaller than 0 or greater than 1 and return either a or b, in each case. — YoTengoUnLCD, Mar 01 '21 at 04:01

score 1 · Answer 3 · answered Mar 19 '17 at 16:17

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.

Narasimham · Answer 4 · 2020-07-02T06:04:56.127

0

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.

edited Jul 02 '20 at 06:04

answered Jul 01 '20 at 22:20

Narasimham

40,495

Nice, but it doesn't handle the case of vertical lines (and indeed, as lines get close to vertical, numerical errors are likely to accumulate if you're doing this on a computer). – John Hughes Feb 22 '21 at 20:58

Find a point on a line segment which is the closest to other point not on the line segment

4 Answers4