[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Find the shortest distance between a point and a line segment in C#

distance between a point and a line segment

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 T2 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*(dx2 + dy2) + 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*(dx2 + dy2)

Now you can divide both sides by (dx2 + dy2) to get:

t = [dx*(Pt.X - Pt1.X) + dy*(Pt.Y - Pt1.Y)] / (dx2 + dy2)

That's the equation used in the code.

Download the example to experiment with it and to see additional details.

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.