line_segment_intersect.py

def line_segment_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
    """
    Compute line segment intersection.

    Line 1: (x1, y1) to (x2, y2)
    Line 2: (x3, y3) to (x4, y4)

    returns intersection (px, py)

    returns None with no intersection.

    https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
    """

    # Common divisor
    d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    
    # Check for parallel lines
    if d == 0:
        return None

    # Make sure we're not off the end of segment 1
    t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / d

    if t < 0 or t > 1:
        return None

    # Make sure we're not off the end of segment 2
    u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / d

    if u < 0 or u > 1:
        return None

    # Common other factors
    f1 = x1*y2 - y1*x2
    f2 = x3*y4 - y3*x4

    # Intersection
    px = (f1 * (x3 - x4) - (x1 - x2) * f2) / d
    py = (f1 * (y3 - y4) - (y1 - y2) * f2) / d

    return px, py


if __name__ == "__main__":
    assert(line_segment_intersect(0,0, 5,0, 0,10, 5,10) is None)
    assert(line_segment_intersect(0,0, 10,10, 0,10, 10,0) == (5,5))
    assert(line_segment_intersect(0,0, 10,10, 0,6, 10,6) == (6,6))
    assert(line_segment_intersect(0,0, 10,10, 0,4, 10,4) == (4,4))
    assert(line_segment_intersect(0,0, 5,0, 6,10, 6,-10) is None)