Find the shortest distance between two line segments in C#

closest points between two line segments

Click four points to pick the end points for the two line segments. The program finds the points on the two segments that are closest and connects them.

The closest distance between two segments is either 0 if they intersect, or the distance from one of the segments’ end points to the other segment. The FindDistanceBetweenSegments method shown in the following code handles those cases.

// Return the shortest distance between the two segments
// p1 --> p2 and p3 --> p4.
private double FindDistanceBetweenSegments(
    PointF p1, PointF p2, PointF p3, PointF p4,
    out PointF close1, out PointF close2)
{
    // See if the segments intersect.
    bool lines_intersect, segments_intersect;
    PointF intersection;
    FindIntersection(p1, p2, p3, p4,
        out lines_intersect, out segments_intersect,
        out intersection, out close1, out close2);
    if (segments_intersect)
    {
        // They intersect.
        close1 = intersection;
        close2 = intersection;
        return 0;
    }

    // Find the other possible distances.
    PointF closest;
    double best_dist = double.MaxValue, test_dist;

    // Try p1.
    test_dist = FindDistanceToSegment(p1, p3, p4, out closest);
    if (test_dist < best_dist)
    {
        best_dist = test_dist;
        close1 = p1;
        close2 = closest;
    }

    // Try p2.
    test_dist = FindDistanceToSegment(p2, p3, p4, out closest);
    if (test_dist < best_dist)
    {
        best_dist = test_dist;
        close1 = p2;
        close2 = closest;
    }

    // Try p3.
    test_dist = FindDistanceToSegment(p3, p1, p2, out closest);
    if (test_dist < best_dist)
    {
        best_dist = test_dist;
        close1 = closest;
        close2 = p3;
    }

    // Try p4.
    test_dist = FindDistanceToSegment(p4, p1, p2, out closest);
    if (test_dist < best_dist)
    {
        best_dist = test_dist;
        close1 = closest;
        close2 = p4;
    }

    return best_dist;
}

The method first calls the FindIntersection method to see if the segments intersect. If they do, FindDistanceBetweenSegments returns 0 and returns the point of intersection for both of the closest points.

If the segments do not intersect, the method calculates the shortest distance from the first segment’s end points to the second segment and vice versa. It then returns the shortest distance.

For information on the FindIntersection and FindDistanceToSegment methods, see:


Download Example   Follow me on Twitter   RSS feed




This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

One Response to Find the shortest distance between two line segments in C#

  1. Rodrigo says:

    Very nice, job well done! And thanks for sharing 😉

Leave a Reply

Your email address will not be published. Required fields are marked *