This problem is roughly equivalent to the test whether two axis-aligned rectangles intersect: you can threat every segment as the diagonal of an axis-aligned rectangle, then you need to find the intersection of these two rectangles. The following is the approach I use for rectangle intersection.
Let's assume that the slope of the segments is ascending, vertical, or horizontal; if the segments are descending, negate every y-coordinate so that they are ascending.
Define the MinPoint and MaxPoint for each line segment:
Point min1 = new Point(Math.Min(line1.X1, line1.X2),Math.Min(line1.Y1,line1.Y2);
Point max1 = new Point(Math.Max(line1.X1, line1.X2),Math.Max(line1.Y1,line1.Y2);
Point min2 = new Point(Math.Min(line2.X1, line2.X2),Math.Min(line2.Y1,line2.Y2);
Point max2 = new Point(Math.Max(line2.X1, line2.X2),Math.Max(line2.Y1,line2.Y2);
Now the intersection is given by the following two points: the maximum of the two minimums, and the minimum of the two maximums
Point minIntersection = new Point(Math.Max(min1.X, min2.X), Math.Max(min1.Y, min2.Y));
Point maxIntersection = new Point(Math.Min(max1.X, max2.X), Math.Min(max1.Y, max2.Y));
and that's it. To test whether the two segments intersect at all, you check
bool intersect = (minIntersection.X< maxIntersection.X) && (minIntersection.Y< maxIntersection.Y);
If they do intersect, the intersection is given by the two points minIntersection
and maxIntersection
. If they do not intersect, the length of the segment (minIntersection, maxIntersection)
is the distance between the two original segments.
(If you negated every y-coordinate in the first step, negate the y-coordinate of the result now)
(You can easily extend this approach to cover colinear segments in 3 or more dimensions)