Algorithm for finding the segment overlapping two collinear segments

Question

UPDATES

• My original implementation in C#
• My final implementation in C#, based on the answers I got.

---

Given the following conditions, how can I programatically find the overlapping segment between two lines?

Also, for a different slope:

And for vertical lines:

And for horizontal lines:

Note: For all the quadrants !

I've started by coding all possible conditions but it gets ugly.

public Line GetOverlap (Line line1, Line line2)
{
    double line1X1 = line1.X1;
    double line1Y1 = line1.Y1;
    double line1X2 = line1.X2;
    double line1Y2 = line1.Y2;
    double line2X1 = line2.X1;
    double line2Y1 = line2.Y1;
    double line2X2 = line2.X2;
    double line2Y2 = line2.Y2;

    if (line1X1 > line1X2)
    {
        double swap = line1X1;
        line1X1 = line1X2;
        line1X2 = swap;

        swap = line1Y1;
        line1Y1 = line1Y2;
        line1Y2 = swap;
    }
    else if (line1X1.AlmostEqualTo (line1X2))
    {
        if (line1Y1 > line1Y2)
        {
            double swap = line1Y1;
            line1Y1 = line1Y2;
            line1Y2 = swap;

            swap = line1X1;
            line1X1 = line1X2;
            line1X2 = swap;
        }
    }

    if (line2X1 > line2X2)
    {
        double swap = line2X1;
        line2X1 = line2X2;
        line2X2 = swap;

        swap = line2Y1;
        line2Y1 = line2Y2;
        line2Y2 = swap;
    }
    else if (line2X1.AlmostEqualTo (line2X2))
    {
        if (line2Y1 > line2Y2)
        {
            double swap = line2Y1;
            line2Y1 = line2Y2;
            line2Y2 = swap;

            swap = line2X1;
            line2X1 = line2X2;
            line2X2 = swap;
        }
    }

    double line1MinX = Math.Min (line1X1, line1X2);
    double line2MinX = Math.Min (line2X1, line2X2);
    double line1MinY = Math.Min (line1Y1, line1Y2);
    double line2MinY = Math.Min (line2Y1, line2Y2);
    double line1MaxX = Math.Max (line1X1, line1X2);
    double line2MaxX = Math.Max (line2X1, line2X2);
    double line1MaxY = Math.Max (line1Y1, line1Y2);
    double line2MaxY = Math.Max (line2Y1, line2Y2);

    double overlap;
    if (line1MinX < line2MinX)
        overlap = Math.Max (line1X1, line1X2) - line2MinX;
    else
        overlap = Math.Max (line2X1, line2X2) - line1MinX;

    if (overlap <= 0)
        return null;

    double x1;
    double y1;
    double x2;
    double y2;

    if (line1MinX.AlmostEqualTo (line2MinX))
    {
        x1 = line1X1;
        x2 = x1;
        y1 = line1MinY < line2MinY
                 ? line2Y1
                 : line1Y1;
        y2 = line1MaxY < line2MaxY
                 ? line1Y2
                 : line2Y2;
    }
    else
    {
        if (line1MinX < line2MinX)
        {
            x1 = line2X1;
            y1 = line2Y1;
        }
        else
        {
            x1 = line1X1;
            y1 = line1Y1;
        }

        if (line1MaxX > line2MaxX)
        {
            x2 = line2X2;
            y2 = line2Y2;
        }
        else
        {
            x2 = line1X2;
            y2 = line1Y2;
        }
    }

    return new Line (x1, y1, x2, y2);
}

I'm sure an algorithm exists for this but I was unable to find one on the web.

---

UPDATE with solution based on answers I got:

This solution account for all the cases I could think of (verticals, horizontals, positive slope, negative slope, not intersecting)

public Line GetOverlap (Line line1, Line line2)
{
    double slope = (line1.Y2 - line1.Y1)/(line1.X2 - line1.X1);
    bool isHorizontal = AlmostZero (slope);
    bool isDescending = slope < 0 && !isHorizontal;
    double invertY = isDescending || isHorizontal ? -1 : 1;

    Point min1 = new Point (Math.Min (line1.X1, line1.X2), Math.Min (line1.Y1*invertY, line1.Y2*invertY));
    Point max1 = new Point (Math.Max (line1.X1, line1.X2), Math.Max (line1.Y1*invertY, line1.Y2*invertY));

    Point min2 = new Point (Math.Min (line2.X1, line2.X2), Math.Min (line2.Y1*invertY, line2.Y2*invertY));
    Point max2 = new Point (Math.Max (line2.X1, line2.X2), Math.Max (line2.Y1*invertY, line2.Y2*invertY));

    Point minIntersection;
    if (isDescending)
        minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Min (min1.Y*invertY, min2.Y*invertY));
    else
        minIntersection = new Point (Math.Max (min1.X, min2.X), Math.Max (min1.Y*invertY, min2.Y*invertY));

    Point maxIntersection;
    if (isDescending)
        maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Max (max1.Y*invertY, max2.Y*invertY));
    else
        maxIntersection = new Point (Math.Min (max1.X, max2.X), Math.Min (max1.Y*invertY, max2.Y*invertY));

    bool intersect = minIntersection.X <= maxIntersection.X && 
                     (!isDescending && minIntersection.Y <= maxIntersection.Y ||
                       isDescending && minIntersection.Y >= maxIntersection.Y);

    if (!intersect)
        return null;

    return new Line (minIntersection, maxIntersection);
}

public bool AlmostEqualTo (double value1, double value2)
{
    return Math.Abs (value1 - value2) <= 0.00001;
}

public bool AlmostZero (double value)
{
    return Math.Abs (value) <= 0.00001;
}

Answer 1

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)