This example treats the segment as parameterized vector where the parameter `t` varies from `0` to `1`. It finds the value of `t` that minimizes the distance from the point to the line.

If `t` is between `0.0` and `1.0`, then the point on the segment that is closest to the other point lies on the segment. Otherwise the closest point is one of the segment’s end points. The program finds this closest point and calculates the distance between it and the target point.

The following code shows how the program finds the distance between the point `pt` and the segment `p1 --> p2`.

// Calculate the distance between // point pt and the segment p1 --> p2. private double FindDistanceToSegment( PointF pt, PointF p1, PointF p2, out PointF closest) { float dx = p2.X - p1.X; float dy = p2.Y - p1.Y; if ((dx == 0) && (dy == 0)) { // It's a point not a line segment. closest = p1; dx = pt.X - p1.X; dy = pt.Y - p1.Y; return Math.Sqrt(dx * dx + dy * dy); } // Calculate the t that minimizes the distance. float t = ((pt.X - p1.X) * dx + (pt.Y - p1.Y) * dy) / (dx * dx + dy * dy); // See if this represents one of the segment's // end points or a point in the middle. if (t < 0) { closest = new PointF(p1.X, p1.Y); dx = pt.X - p1.X; dy = pt.Y - p1.Y; } else if (t > 1) { closest = new PointF(p2.X, p2.Y); dx = pt.X - p2.X; dy = pt.Y - p2.Y; } else { closest = new PointF(p1.X + t * dx, p1.Y + t * dy); dx = pt.X - closest.X; dy = pt.Y - closest.Y; } return Math.Sqrt(dx * dx + dy * dy); }

The least obvious part of this code is the following statement.

// Calculate the t that minimizes the distance. float t = ((pt.X - p1.X) * dx + (pt.Y - p1.Y) * dy) / (dx * dx + dy * dy);

So where does this formula come from?

To find the shortest distance between that point and the line segment, you need to know some relatively easy calculus and one clever fact. The clever fact is that if T minimizes an equation, then T^{2} minimizes the equation squared. In this example that means we can minimize the distance squared between the point and the line segment, and then the value `t` that we find will also minimize the non-squared distance.

A point on the line segment has coordinates X = Pt1.X + t*dx, Y = Pt1.Y + t*dy.

The distance squared between that point and the point P is:

[Pt.X - (Pt1.X + t*dx)]^{2}+ [Pt.Y - (Pt1.Y + t*dy)]^{2}

Taking the derivative with respect to t gives:

2*[Pt.X - (Pt1.X + t*dx)]*dx + 2*[Pt.Y - (Pt1.Y + t*dy)]*dy

To find the minimum, we set this equal to 0 and solve for t.

2*[Pt.X - (Pt1.X + t*dx)]*dx + 2*[Pt.Y - (Pt1.Y + t*dy)]*dy = 0

Now if you divide both sides by 2 and then combine the t terms you get:

-t*(dx^{2}+ dy^{2}) + dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y) = 0

Subtracting the t term from both sides of the equation gives:

dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y) = t*(dx^{2}+ dy^{2})

Now you can divide both sides by (dx^{2} + dy^{2}) to get:

t = [dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y)] / (dx^{2}+ dy^{2})

That’s the equation used in the code.

Thank you! This worked great for me. ðŸ™‚

Thank you!

Finally a function that works for line segments and not just for infinite lines.

Pingback: Find the shortest distance between two line segments in C# -

Pingback: Draw and move line segments in C# -

THX BRO!!!

Pingback: Make a WPF line editor C# - C# HelperC# Helper

I have been getting some strange results when using this method is minus numbers typically less and 1. Does any one know if this method should also work correctly for

a)Negative numbers x / y input

b) when x / y could be less than 1.

Also is there a name for the theory / method this code is derived from. I really want to use this method as its alot faster than the alternatives!

It seems to work for me. Can you give me some example coordinates where it doesn’t seem to work?

I don’t know if this method has a name. I derived it a long time ago. If you use it in your code, you might include a link to the page so you can find it later if you need to.

Thank you!

can you just give the code in my sql

I don’t think MySQL (or any database tool) has any code to do this. You would need to write some code to get the segments’ end points and perform the calculation.

Been years since I’ve had to look at Algebra so probably a silly question, P1 and P2 does it matter which point on the line segment is which (i.e. most left needs to be P1) or does it make no difference?

Thx

This isn’t a silly question at all. The short answer is, no it doesn’t matter.

The value t tells you how far you go from point A to point B. If you switch them around, then t tells you how far you go from B to A, but you get the same point either way.

The reason why this isn’t a silly question is that this method uses vector arithmetic and the parameter t to make sure it doesn’t matter which order you use. If you try to solve equations like y = mx + b, you run into special cases for things like a vertical line (where the slope m is infinite). This technique lets you handle all cases the same way whether the line is vertical, horizontal, or you swap the order of the points.

How can i call this function?

If you download the example, you should be able to see how the code does it.

Thank you!

Good day sir!

I’m a student studying C# for my programming subject. I tried replicating this program to function on a Picturebox object in VS2013 but it doesn’t work. I’m currently comparing the code of the two programs, your original version and my modified version and to my rookie eyes, I couldn’t find a difference. I think I’m missing something to allow this program to work inside the Picturebox.

Did you download the example? Or just copy and paste the code into your program? The example has more code that’s not shown here to hook up the PictureBox to event handlers that let you pick the segment and point.

“float t = ((pt.X – p1.X) * dx + (pt.Y – p1.Y) * dy) /

(dx * dx + dy * dy);”

Can you explain where this formula comes from? I’ve been racking my brain this morning but it’s been too long since I took Linear Algebra or Calc 3. I understand the concept of a parametric equation, just not why the above formula produces the t that minimizes distance. Thanks!

I’ve added an explanation to the bottom of the post above.

Thank you! Very clear explanation. I had missed the fact that you could minimize the square of the function, so I was left with a really ugly equation.

Hey.. you again !!! Thanks so much. You helped me so many times! ðŸ™‚

Wrong results sometime for me with your function. I use these functions

What are some values that give the wrong answer?

Also there’s an

ifstatement where the test was removed, probably because WordPress got confused by a < or >. Should it beif (dp < sn2)?“if T minimizes an equation, then T^2 minimizes the equation squared”

You wish.

First of all, you can’t minimize “equations”. You can only minimize functions.

Second, consider this function f(x) = x^2 – 1, which is minimized by x = 0. Its square, f^2(x) = x^4 – 2x^2 + 1, is minimized by x = -1 and x = 1, and not by x = 0^2 = 0.

What you MEANT to say is this:

If T minimizes a NON-NEGATIVE real function, then T (not T squared!) minimizes the function squared. Simply because f(x) = x^2 is increasing for x >= 0.

Good catch, Giovanni, and thanks for walking through an example.

Your post was very helpful, Rod. Thanks! ðŸ™‚

Hi, does it work with Coordinate in map as in Latitude & Longitude? If it does, what is the unit of the distance? Is it in kilometers, meters or etc?

Not really. If the point and line are reasonably close together, then it would work. You would need to scale the distances to account for the distance between longitude and latitude in your part of the world. The longitudinal distances change slightly due to the Earth not being completely round. The latitudinal distances change greatly because they meet at the poles.

If the point and line are very far apart, then the shortest distance between them is a great circle and not a line, so even those calculations won’t be correct. I’ll post an example shortly that calculates the distance between two points on the globe. I’m not sure how you would calculate the closest distance between a point and a line on the globe.

I see. My application needs to determine if a vessel (the single point) stays on its route (the line) or not. The vessel needs to be within 10 nautical miles from the line. Is it too far apart?

An interesting problem!

There would be some small error, but I suspect it wouldn’t be very large when you’re only dealing with a maximum distance of 10 miles. The error might be larger between the vessel’s position and the far endpoints of the line segment, but that won’t be the shortest distance to the line so it won’t matter.

So for this problem, I think you should be fairly safe using the simpler flat geometry calculation. However, you will need to figure out how to convert the local longitude and latitude into miles because it varies at different points on the globe.

It may be easier to loop through points along the line and calculate the distance to the vessel for each. Not very elegant, but simple. And if you calculate a point every mile or so, you should get a pretty close result. (You could even calculate 100 points per mile–it shouldn’t take long.)

Cool. Thanks! I’ll try that out.

Hi,

I really want to learn your codes, but i only know just Pascal. Is there any way could you make it in pascal code?

Thank you for a post and explanation.

Tbk

Sorry but I really don’t have time to rewrite it in Pascal. You may be able to piece together how the equations work.

Pingback: Download and graph COVID-19 case data in C# - C# HelperC# Helper

Pingback: Let the user edit polygons in WPF and C# - C# HelperC# Helper

Not working for me with these points:

Pt: (93, 10592.1)

X1_lineSeg: (92, 9826.1)

X2_lineSeg: (94, 11208.3)

It’s producing the output closeset pt: (93.108, 10592.1), which is incorrect. In fact, this happens to have the same y-value as the point itself even though the line segment defined by X1 and X2 clearly have a slope; but this “closest point” does lie on the line, it is just not the closest point but rather the closest X-distance to the line.

I think this is due to rounding errors. That line is quite steep, with a slope of around 691, so the result is very close to the line. If you perform the calculations using doubles instead of floats, the Y coordinate is 10592.099452556089. If you subtract that from the given point’s Y coordinate, the difference is -0.00015681891090935096. When you convert the result into a float to make the PointF result, it rounds to the value that you’re seeing.

I don’t think this example can do much better for those points because of the limitations of the PointF type. You can do slightly better if you build your own Point class that uses doubles.