13
$\begingroup$

I'm pretty sure this may be a duplicate post somewhere, but I've searched all through the internet looking for a definite formula to calculate the distance between a point and a line segment. There are so many different variations of the formula that people have posted that its hard to determine which is correct.

I actually have several points that I will be looping through to get their distances. Each point will be within the boundary of the segment(if that makes any sense) so there will be no need to perform this theoretical check of the point being 'within' the segment that I've somewhat heard about. So can anyone please post the correct formula to calculate the distance of a point C(x,y) from a line segment AB??

$\endgroup$
  • $\begingroup$ What do you mean by "within the segment" ? If C in on AB, distance is zero. If C is not, distance will be found by projection of C on AB, if this projection falls inside AB, or will be AC or BC in other cases. $\endgroup$ – Jean-Claude Arbaut Mar 14 '13 at 13:06
  • $\begingroup$ I don't think this has a general answer as it may depend, in euclidean plane or space, on the relative positions of the point and the segment. There is a general, pretty nice, formula for the distance from a point to a straight line, though... $\endgroup$ – DonAntonio Mar 14 '13 at 13:06
  • 1
    $\begingroup$ I think "within the segment" means exactly that the projection on (the line supporting) the segment falls within the segment. If you are assume this is always the case, then just use that line instead of the segment of it. And for the distance of a point to a line, see the answer by julien. $\endgroup$ – Marc van Leeuwen Mar 14 '13 at 13:34
  • $\begingroup$ I had first overlooked the "segment" thing. So I did the distance to a line. But note that the distance to a line segment is done here. And note that is valid in any Hilbert space, not only $\mathbb{R}^3$. $\endgroup$ – Julien Mar 14 '13 at 13:46
  • $\begingroup$ Aarbautjc - I had mis typed. WHen I meant C is within the segment AB, i had just meant that if A(-1,1) and B(4,4) then our point C is of course not on the segment but at the same time, Cx can only be greater than Ax and less than Bx. Make sense? Geometry lingo is a tad bit off. But I agree that the distance does need to be found by projection of C on AB so that a line from point to the segment would form a right angle, i.e. orthological I think. Some big word that starts with an O. lol $\endgroup$ – user1898629 Mar 14 '13 at 13:53
15
$\begingroup$

Let the line segment be described by two points $s_1,s_2$, and you wish to find the nearest point on the segment to the point $p$.

We find the nearest point to the line through $s_1,s_2$, then 'project' back to the segment, then compute the distance.

A point on the line can be parameterized by $s(t) = s_1+t(s_2-s_1)$, note that $s(t)$ is on the line segment iff $t \in [0,1]$. The distance from $p$ to the point $s(t)$ given by the function $\phi(t)= \|s(t)-p\|$. It is easier to deal with $\phi^2$, which is a convex quadratic in $t$.

To find the minimizing '$t$', we set the derivative of $\phi^2$ to zero giving $\hat{t} = \frac{\langle p-s_1, s_2-s_1\rangle}{\|s_2-s_1\|^2}$. To find the $t$ that minimizes the distance on the segment, we 'project' back to $[0,1]$ using $t^* = \min(\max(\hat{t},0),1)$. Then the minimum distance is given by $\|s(t^*)-p\|$.

$\endgroup$
3
$\begingroup$

Edit: this is indeed a duplicate, I had not read the question carefully enough. Below is how you compute the distance from a point to a line, which is the major bulk when computing the distance from a point to a line segment.

Let us assume we are in $\mathbb{R}^n$ ($n\geq 2$) equipped with its usual Euclidean inner product $(x,y)=\sum_{k=1}^nx_ky_k$.

Let $L$ be a line parameterized by $$ t\longmapsto P+t\vec{u} $$ where $P$ is a point belonging to this line and $\vec{u}$ is a vector giving the direction of $L$. If you know two points $P,P'$ on the line, it suffices to take $P$ and $\vec{u}=\vec{PP'}$.

Now let $Q$ be any point. The distance $Q$ to $L$ is the distance between $Q$ and $Q_L$ its orthogonal projection on $L$. Now $Q_L$ is characterized by the vector projection formula: $$ \vec{PQ_L}=\frac{(\vec{PQ_L},\vec{u})}{\|\vec{u}\|^2}\vec{u}. $$ So $$ \vec{QQ_L}=\vec{QP}+\vec{PQ_L}=\vec{QP}+\frac{(\vec{PQ_L},\vec{u})}{\|\vec{u}\|^2}\vec{u}. $$ It only remains to compute the norm of the latter to get the distance from $Q$ to $L$.

Note: when $n=2$ and $L$ is given by a cartesian equation $ax+by+c=0$, this yields the formula $$ d(P,L)=\frac{|ax+by+c|}{\sqrt{a^2+b^2}} $$ for every $P=(x,y)$.

Algorithm to compute the distance from $Q$ to the line segment $[P,P']$: Take an arbitrary point $Q$. Compute the coordinates of the projection $Q_L$ on the line (which does not necessarily belong to the segment). Compute $d(Q,Q_L)=\|\vec{QQ_L}\|$ the distance between $Q$ and $Q_L$. Also compute the distances $d(Q,P)$ and $d(Q,P')$ to the endpoints. Then the number you are looking for (the distance from $Q$ to $[P,P']$) is the minimum of these three numbers: $d(Q,Q_L)$, $d(Q,P)$ and $d(Q,P')$.

$\endgroup$
  • $\begingroup$ Julien -- I appreciate the mathematical breakdown. I will attempt to decipher all this so it fits into a python script. W/out full understanding, I have no script. My math/geometry skill is shamefully rusty. At this point, I'd need step by step instructions. Lol. Thanks for your feedback though. $\endgroup$ – user1898629 Mar 14 '13 at 13:57
  • $\begingroup$ @Gis_Guy Note that my answer in the link I provided above explains the three steps of a possible algorithm. I think it is not to hard to program it then, in any language. Good luck! $\endgroup$ – Julien Mar 14 '13 at 14:01
  • $\begingroup$ Julien -- Just so I can better my understanding, because I am dealing with strictly a segment, my projection Q would belong to [p1, p2] in terms of calculating the distance, correct? Also, in the link explaining the algorithm, I am having trouble understanding "3.2". Again, my math is lacking, and all the symbols and arrows aren't making things to clear. Thanks for your patience/understanding. $\endgroup$ – user1898629 Mar 14 '13 at 14:54
  • 3
    $\begingroup$ Your algorithm is wrong: If the projection is outside the segment it should be ignored. The projection could be outside the segment and still be closer than the distance to the endpoints. e.g. the line between (0,0) and (1,1) for the point (3,2). $\endgroup$ – keyser May 1 '14 at 17:20
  • 1
    $\begingroup$ As keyser said, the algorithm is wrong. When the projection is outside of the segment, its length will be always shorter than the distance to any of the endpoints. $\endgroup$ – Saul Berardo Jul 6 '15 at 16:54

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.