Closest points on two line segments I am looking for a general formulation to find the closest points on two line segments.
What I was thinking about is to define our lines as:
$$ P1 + s  (P2-P1)$$
$$ Q1 + t  (Q2-Q1)$$
Where $P1 , P2, Q1$ and $Q2$ are the beginning and the end points on each segment.
Now we should go through an optimization problem as: $\min f(s,t)$ such that $0<s<1$ and $0<t<1$.  Where $f(s,t)$ is the point-to-point distance function.
Is there any straight forward solution?
 A: Since the thing you are minimizing is an everywhere-positive quadratic function of $t$ and $s$, it is convex in each variable. So, we need its critical point, and failing that, something close to it. 
The function has a critical point when the vector connecting points on two lines is orthogonal to each line. At this point, 
the vector $$v = P1 + s(P2-P1) - Q1- t(Q2−Q1)$$ satisfies $$v\perp (P2-P1) \quad \text{ and} \quad v\perp (Q2-Q1)$$
This is a system of two linear equations with two unknowns $s,t$. Having solved it, you may find that either:   


*

*Both $t$ and $s$ are between $0$ and $1$. Then they give the minimum 

*One or both of $t,s$ are outside of the interval $[0,1]$. Then replace the outlying number with the nearest point of the    interval $[0,1]$.

A: Here's an implementation using NumPy
def closest_line_seg_line_seg(p1, p2, p3, p4):
    P1 = p1
    P2 = p3
    V1 = p2 - p1
    V2 = p4 - p3
    V21 = P2 - P1

    v22 = np.dot(V2, V2)
    v11 = np.dot(V1, V1)
    v21 = np.dot(V2, V1)
    v21_1 = np.dot(V21, V1)
    v21_2 = np.dot(V21, V2)
    denom = v21 * v21 - v22 * v11

    if np.isclose(denom, 0.):
        s = 0.
        t = (v11 * s - v21_1) / v21
    else:
        s = (v21_2 * v21 - v22 * v21_1) / denom
        t = (-v21_1 * v21 + v11 * v21_2) / denom

    s = max(min(s, 1.), 0.)
    t = max(min(t, 1.), 0.)

    p_a = P1 + s * V1
    p_b = P2 + t * V2

    return p_a, p_b


