import torch


def find_intersection(line_a, line_b):
    """Find the intersection point (if it exists) of two line segments, a and b.

    This uses an algorithm based upon LeMothe's "Tricks of the Windows Game Programming Gurus". We
    could have used some fancy cross product stuff here, but this is much more comprehensible.
    Each segment is parameterized by variables, s and t, such at when s=0 we are at line_a[0] and
    when s[1] we are at line_a[1] (and so on for t). We then solve for the values of s and t where
    the equations for line_a and line_b give the same result. If we cannot find values for s and t
    that satisfy this then there is no intersection.

    Arguments:
        line_a (tensor): 2x2 tensor describing line a. line_a[0] is the first point.
        line_b (tensor): The same thing is line_a.
    Returns:
        None or 2 element torch.tensor
    """
    xslope_a = line_a[1,0] - line_a[0,0]
    xslope_b = line_b[1,0] - line_b[0,0]
    yslope_a = line_a[1,1] - line_a[0,1]
    yslope_b = line_b[1,1] - line_b[0,1]
    # Find the parameters where the lines intersect
    s_numerator = -yslope_a * (line_a[0,0] - line_b[0,0]) + xslope_a * (line_a[0,1] - line_b[0, 1])
    t_numerator = -yslope_b * (line_a[0,0] - line_b[0, 0]) + xslope_b * (line_a[0,1] - line_b[0,1])
    denominator = (-xslope_b * yslope_a + xslope_a * yslope_b)
    # If the lines are parallel then the slope will cancel out and the denominator will be 0.
    # For simplicity we will just say that they do not intersect in that case.
    if 0 == denominator:
        # Early return for efficiency
        return None
    # Check one range at a time to possibly skip a second division operation
    s = s_numerator / denominator
    if 0 <= s and s <= 1:
        t = t_numerator / denominator
        if 0 <= t and t <= 1:
            intersection = [line_a[0,0] + t * xslope_a, line_a[0, 1] + t * yslope_a]
            return torch.tensor(intersection)
    # No intersection
    return None