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

[The shortest distance between a point and a line segment]

This example finds the shortest distance from a point to a line segment. Click and drag the left mouse button to define the line segment. Then click the right mouse button to select the point.

Parameterizing Segments

One way to represent a line segment is as a parameterized vector where the parameter t varies from 0.0 to 1.0. If the segment's end points are p1 and p2, then the following equation gives the location of a point on the segment as t varies from 0.0 to 1.0.

p = p1 * (1 - t) + p2 * t

When t is 0.0, the result is the segment's first end point. When t is 1.0, the equation gives the second end point.

Another way to write this is:

p[0] = p1[0] + t * dx p[1] = p1[1] + t * dy

Where:

dx = p2[0] - p1[0] dy = p2[1] - p1[1]

Minimizing Distance

To find the distance between a point p and the line segment, you can plug the equation into the distance formula. Then use a clever fact and a little calculus to minimize the distance. Here's the clever fact:

If t² minimizes the distance squared, then t minimizes the distance.

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 = p1[0] + t * dx, y = p1[1] + t * dy.

The distance squared between a point given by this equation and the target point p is:

[p[0] - (p1[0] + t * dx)]² + [p[1] - (p1[1] + t * dy)]²

This is just the X difference squared plus the Y difference squared.

Taking the derivative of that with respect to t gives:

2 * [p[0] - (p1[0] + t * dx)] * dx + 2 * [p[1] - (p1[1] + t * dy)] * dy

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

2 * [p[0] - (p1[0] + t * dx)] * dx + 2 * [p[1] - (p1[1] + t * dy)] * dy = 0

If you divide both sides by 2, multiply it out, and combine the t terms, you get:

-t * (dx² + dy²) + dx * (p[0]- p1[0]) + dy * (p[1] - p1[1]) = 0

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

dx * (p[0] - p1[0]) + dy * (p[1] - p1[1]) = t * (dx² + dy²)

Now you can divide both sides by (dx² + dy²) to get:

t = [dx * (p[0] - p1[0]) + dy * (p[1] - p1[1])] / (dx² + dy²)

Now let's take a look at the example program's Python code and see how it uses this equation.

Calculating Distance in Python

The following find_distance_to_segment function calculates the distance from the point pt to the line segment p1⟶p2.

def find_distance_to_segment(pt, p1, p2): '''Find the distance between point pt and the segment p1 --> p2.''' # Return the closest point on the segment and the distance. dx = p2[0] - p1[0] dy = p2[1] - p1[1] if dx == 0 and dy == 0: # It's a point not a line segment. closest = tuple(p1) dx = pt[0] - p1[0] dy = pt[1] - p1[1] return closest, math.sqrt(dx * dx + dy * dy) # Calculate the t that minimizes the distance. t = ((pt[0] - p1[0]) * dx + (pt[1] - p1[1]) * dy) / (dx * dx + dy * dy) # See if this represents a segment end point or a point in the middle. if t < 0: closest = (p1[0], p1[1]) dx = pt[0] - p1[0] dy = pt[1] - p1[1] elif t > 1: closest = (p2[0], p2[1]) dx = pt[0] - p2[0] dy = pt[1] - p2[1] else: closest = (p1[0] + t * dx, p1[1] + t * dy) dx = pt[0] - closest[0] dy = pt[1] - closest[1] return closest, math.sqrt(dx * dx + dy * dy)

The code first calculates the X and Y distances dx and dy from p1 to p2.

If dx and dy are both zero, then the line segment is just a point so the function returns that point and the distance between it and point pt.

If the segment isn't just a point, the code uses the earlier equation to calculate the t value that minimizes the distance.

[Sometimes the closest shortest distance between a point and a line segment occurs at a segment end point]

If t is less than zero, the point on the line that minimizes the distance is not on the segment, it is on the side of the line closer to point p1 than p2, as shown in the picture on the right. In that case, the code saves p1 as the closest point and finds the X and Y distances from that point to point pt.

Similarly, if t is greater than zero, the point on the line that minimizes the distance is not on the segment, it is on the side of the line closer to point p2 than p1. In that case, the code saves p2 as the closest point and finds the X and Y distances from that point to point pt.

Finally, if 0 ≤ t ≤ 1, the code uses t and the parameterized equation for the segment to find the closest point. It then calculates the X and Y distances from that point to pt.

The function finishes by returning the closest point and the distance between that point and pt.

Conclusion

The find_distance_to_segment is fast and easy to use. If you like, you can modify it to return the closest point on the line in the event that t is less than zero or greater than one.

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