Wikipedia:Reference desk/Archives/Mathematics/2024 September 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 6

Distance to a line segment

I am unsure if this is better in Maths or in Computing, but I've chosen Maths.

In a standard planar (x,y) world, a line segment is defined by two endpoints P1=(x1,y1) and P2=(x2,y2).

A third point (anywhere, not necessarily off the line segment extension) is A=(xa,ya).

It is easy to calculate the distance from A to P1 and from A to P2. Sometimes one will be the answer for which part of the line segment is closest to A.

But if A is "perpendicularly within P1~P2", then the closest part of P1~P2 will be somewhere on that line segment.

Is there a standard algorithm for determining the coordinates of the closest part of the line segment to A?

--SGBailey (talk) 22:59, 6 September 2024 (UTC)

I don't know if it's "standard", but it's not too hard to work out. Let D be the square distance between P₁ and P₂, so D = (x₂-x₁)² + (y₂-y₁)². Let E be twice the (signed) area of the triangle P₁P₂A, so E = x₁y₂ - x₁y_a - x₂y₁ + x₂y_a + x_ay₁ - x_ay₂. Note that if D=0 then the result is undefined, if E=0 then the result is just A, if x₁=x₂ then y=y_a, and if y₁=y₂ then x=x_a; these facts can be used as checks. Then, using Cramer's rule and a few tricks I'm pretty sure I wouldn't be able to fully explain, I get x = x_a + (y₂-y₁)E/D, y = y_a - (x₂-x₁)E/D. Geometrically, you know that the vector PA is perpendicular to P₁P₂, which means P can be written A + mP₁P₂^⊥, where P₁P₂^⊥ is normal to P₁P₂; we can take this as (-(y₂-y₁), x₂-x₁). You can then solve for m by finding the area of the triangle P₁P₂A in two ways. Note that if you just want the distance to the line it's a lot easier, just divide twice the area of the triangle, |E|, by the length of the segment P₁P₂. I'm assuming here that you want the closest point to the line P₁P₂, since there's no guarantee that the result P will be between P₁ and P₂, and if not it technically won't be on the segment P₁P₂. --RDBury (talk) 05:51, 7 September 2024 (UTC)

Here is an analytic approach. The line through the distinct points ${\text{P}}_{1}$ and ${\text{P}}_{2}$ can be parametrically represented by

$(x,y)=(\lambda x_{1}+(1-\lambda )x_{2},\lambda y_{1}+(1-\lambda )y_{2}).$

(The usual equation for the line can be obtained by eliminating $\lambda$ from this equation.)

The vector connecting a generic point $(x,y)$ on the line to a point $(x_{\text{A}},y_{\text{A}})$ not on the line is then given by

$(\lambda x_{1}+(1-\lambda )x_{2}-x_{\text{A}},\lambda y_{1}+(1-\lambda )y_{2}-y_{\text{A}}).$

The length of this vector is minimized when its square is, which is given by the quantity

$f(\lambda )=(\lambda x_{1}+(1-\lambda )x_{2}-x_{\text{A}})^{2}+(\lambda y_{1}+(1-\lambda )y_{2}-y_{\text{A}})^{2}.$

Now solve ${\frac {d}{d\lambda }}f(\lambda )=0$ for $\lambda$ and substitute the result in the parametric equation and you have the coordinates of the nearest point. Note: if ${\text{A}}$ is on the line, this procedure may lead to division by zero.

(If done by hand, it helps to first rewrite the parametric equation as

$(x,y)=(\lambda (x_{1}-x_{2})+x_{2},\lambda (y_{1}-y_{2})+y_{2}).$

Also, alternatively, to avoid differentiation, rewrite the equation for $f(\lambda )$ in the form $f(\lambda )=a\lambda ^{2}+b\lambda +c.$ The value of $\lambda$ minimizing $f(\lambda )$ is then given by $\lambda =-{\frac {b}{2a}}.$)
 --Lambiam 06:47, 7 September 2024 (UTC)

One advantage to this method is that it works just as well in multiple dimensions. A more general version is: Given k points P₁, ... P_k, and l points Q₁, ... Q_l in Rⁿ, with k+l≤n-1, find a formula for the points P and Q where P is on the affine space determined by the P_i's, Q is on the affine space determined by the Q_i's, and P and Q are a close as possible to each other. It might be easier if the affine planes were given by systems of equations instead of as affine hulls. --RDBury (talk) 07:31, 7 September 2024 (UTC)

PS. It might be worth mentioning that when you solve for lambda, the resulting point P will be the one where AP⊥P₁P₂, so you're basically just proving what was assumed in the original question. This holds for any smooth curve and even smooth surfaces; if P is the closest point to A on a smooth curve/surface, then PA is perpendicular to the tangent line/plane at P. --RDBury (talk) 01:53, 9 September 2024 (UTC)

Thanks. That is probably resolved, but I need to study the replies. -- SGBailey (talk) 18:02, 8 September 2024 (UTC)