2
$\begingroup$

Okay, I know what you're thinking : this question has been asked a billion times before. But I have done my research, and sadly, the only answers I have found were presented in computer code, which I never learned, or involve too many vectors and constants that might seem a bit redundant (I'm sorry if I'm offending anybody. I'm a bit rusty on geometry, since it's been a while).

Basically, you have 3 coordinates that you know: 1) (px,py) is the coordinate of the point 2) (vx1, vy1) is the coordinate of one end of the line segment 3) (vx2, vy2) is the coordinate of the other end

Is there a way to find the shortest distance between this point and that segment? Please give me an answer that's relatively simple, using basic geometry/ algebra to explain. I love you all!

$\endgroup$
  • $\begingroup$ I'll come back to answer this question more fully, perhaps, but one reason why computer code answers are likely to appear is that there are some conditionals of the type "If the point $(px, py)$ is in [some region], then the nearest point is $(vx_1, vy_1)$; otherwise, if it's in [some other region], then the nearest point is $(vx_2, vy_2)$; otherwise, it's this point given by [some expression]." It's just easier to convey that structure using computer code, or its equivalent. What's more, the regions and expressions that I've conveniently left out are ungainly without temporary variables. $\endgroup$ – Brian Tung Apr 23 '17 at 20:42
  • $\begingroup$ Did you look at MathWorld's explanation? $\endgroup$ – Joseph O'Rourke Apr 23 '17 at 23:45
2
$\begingroup$

The basic idea is to determine whether the line through the point $(px,py)$ perpendicular to the line through the points $(vx1,vy1)$ and $(vx2,vy2)$ intersects the line segment between those points or not. If yes, then the shortest distance is the perpendicular distance from that point to the line, otherwise the shortest distance is the smaller of the distances calculated from the point to the two endpoints of the segment.

enter image description here

The two scenarios are illustrated in the figure above. For $(px,py)$ the shortest distance is the perpendicular distance to the line. For $(px',py')$ the shortest distance is the smaller of the distances from that point to the endpoints of the segment.

Using the link suggested by @Joseph O'Rourke in the comments above and setting the $z$ component to $0$, we can write the equation of the line through the two points as: $$v= \begin{bmatrix} vx1+(vx2-vx1)t \\ vy1+(vy2-vy1)t \\ 0 \\ \end{bmatrix}$$ From the link we see that the minimum distance to the point $(px,py,0)$ occurs when: $$t=-\frac{\begin{bmatrix} vx1-px \\ vy1-py \\ 0 \\ \end{bmatrix}\cdot\begin{bmatrix} vx2-vx1 \\ vy2-vy1 \\ 0 \\ \end{bmatrix}}{{\left\lvert\begin{bmatrix} vx2-vx1 \\ vy2-vy1 \\ 0 \\ \end{bmatrix}\right\rvert}^2}$$ or when $$t=-\frac{(vx1-px)(vx2-vx1)+(vy1-py)(vy2-vy1)}{(vx2-vx1)^2+(vy2-vy1)^2}$$ If $0\le\ t \le 1$ then the perpendicular line intersects the line segment and the minimum distance is: $$d=\frac{\left\lvert\begin{bmatrix} vx2-vx1 \\ vy2-vy1 \\ 0 \\ \end{bmatrix}\times\begin{bmatrix} vx1-px \\ vy1-py \\ 0 \\ \end{bmatrix}\right\rvert}{\left\lvert\begin{bmatrix} vx2-vx1 \\ vy2-vy1 \\ 0 \\ \end{bmatrix}\right\rvert}$$ or $$d=\frac{\left\lvert(vx2-vx1)(vy1-py)-(vy2-vy1)(vx1-px)\right\rvert}{\sqrt{(vx2-vx1)^2+(vy2-vy1)^2}}$$ If $t$ is not in that interval, then calculate: $$d_1 = \sqrt{(vx2-px)^2+(vy2-py)^2}$$ and $$d_2 = \sqrt{(vx1-px)^2+(vy1-py)^2}$$ and find the smaller of $d_1$ and $d_2$.

$\endgroup$
2
$\begingroup$

I was never all that good with linear algebra, so someone please tell me if this is incorrect, but here goes...

First, note that if we have a line segment defined by vectors $\mathbf{P_0}$ and $\mathbf{P_1}$, then let $\mathbf{M} = \mathbf{P_1} - \mathbf{P_0}$. Then every point on the line can be represented as $\mathbf{P_0} + \mathbf{M}t$ for some $t$. If we restrict $0 \leq t \leq 1$ then we get all of the points on the line segment.

Going back to your problem, we have points $\mathbf{P_0}$ and $\mathbf{P_1}$ that comprise the endpoints of a line segment, and we have a point $\mathbf{Q}$. We want to find the unique $t$ that minimizes the distance between $\mathbf{P_0} + \mathbf{M}t$ and $\mathbf{Q}$, with the restriction that $0 \leq t \leq 1$. Let's also assume that $\mathbf{Q}$ is not on the line segment (this will be important later).

First, let's make this simpler by assuming that $\mathbf{P_0}$ is at the origin. So We simply want to minimize the distance between $\mathbf{Q}$ and $\mathbf{M}t$. Note that this distance is

$$D(t) = \sqrt{(\mathbf{Q} - \mathbf{M}t) \cdot (\mathbf{Q} - \mathbf{M}t)}$$

Because dot products are both distributive and commutative, we can expand this out to

$$D(t) = \sqrt{\mathbf{Q} \cdot \mathbf{Q} - 2\mathbf{Q} \cdot \mathbf{M}t + \mathbf{M} \cdot \mathbf{M}t^2}$$

In order to find the value of $t$ that minimizes this equation, let's take the derivative with respect to $t$:

$$D'(t) = \dfrac{1}{2} \times \dfrac{1}{\sqrt{\mathbf{Q} \cdot \mathbf{Q} - 2\mathbf{Q} \cdot \mathbf{M}t + \mathbf{M} \cdot \mathbf{M}t^2}} \times (-2\mathbf{Q} \cdot \mathbf{M} + 2 \mathbf{M} \cdot \mathbf{M}t) = 0$$

First, let's note that because we assumed that $\mathbf{Q}$ is not colinear with $\mathbf{P_0}$ and $\mathbf{P_1}$, the distance between $\mathbf{Q}$ and $\mathbf{M}t$ is positive for all $t$, so the denominator in this equation is always a positive.

Let's simplify the equation to $$\dfrac{-\mathbf{Q} \cdot \mathbf{M} + \mathbf{M} \cdot \mathbf{M}t}{\sqrt{\mathbf{Q} \cdot \mathbf{M}t - 2\mathbf{Q} \cdot \mathbf{Q} + \mathbf{M} \cdot \mathbf{M}t^2}} = 0$$

We can multiply both sides by that ugly denominator, and the 0 makes it disappear! This leaves us with $$-\mathbf{Q} \cdot \mathbf{M} + \mathbf{M} \cdot \mathbf{M}t = 0$$ $$t = \dfrac{\mathbf{Q} \cdot \mathbf{M}}{\mathbf{M} \cdot \mathbf{M}}$$

Note that technically we would want to take the second derivative to confirm that this is a minimum and not a maximum. But right now I am feeling lazy, and also intuitively I don't see how this function could be anything other than concave up.

If $t < 0$, then this tells us that to find the closest point we would have to extend the line segment past $\mathbf{P_0}$. So truncate $t \leftarrow 0$ and output $\mathbf{M} \times 0 = \mathbf{P_0}$ (i.e., the origin) as the closest point.

If $t > 1$, then this tells us that to find the closest point we would have to extend the line segment past $\mathbf{P_1}$. So we truncate $t \leftarrow 1$ and output $\mathbf{M} \times 1 = \mathbf{P_1}$ as the closest point.

Otherwise, we output $\mathbf{M}t$ as the closest point.

Ok, so what happens if $\mathbf{P_0}$ is not at the origin? Easy! We simply translate all three points until $\mathbf{P_0}$ is at the origin. We compute $\mathbf{P_0'}, \mathbf{P_1'}, \mathbf{Q'}$ such that $\mathbf{P_0'}$ is at the origin, and the other two points have been translated by the same amount in each dimension. We compute $\mathbf{M} = \mathbf{P_1} - \mathbf{P_0}$ the optimal value of $t = \dfrac{\mathbf{Q'} \cdot \mathbf{M}}{\mathbf{M} \cdot \mathbf{M}}$ Then, we just plug in this value of $t$ with our original points, and output $\mathbf{P_0} + \mathbf{M}t$

If this is incorrect, someone please let me know and I will gladly take this down ASAP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.