Explanation of line segment intersection for two points

line_segment_intersction.md

The answer to the question here https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect by Gareth Rees is the best explanation.

We need to expand this to fit the co-ordinates

From https://stackoverflow.com/a/565282/429476

$$ \begin{align} t= (q-p) \times \vec s / \vec r \times \vec s\\ u= (q-p) \times \vec r / \vec r \times \vec s \end{align} $$

Given that the line segment p runs from $(x1, y1)$ to $(x2, y2)$, we can express the direction vector r as:

$$ r = (x2 - x1, y2 - y1) $$

Similarly, the line segment q runs from $(lx1, ly1)$ to $(lx2, ly2)$, and its direction vector s is:

$$ s = (lx2 - lx1, ly2 - ly1) $$

Note

$$ \begin{align} r \times s = determenent\ of\ matrix (r,s) = det|r,s| \end{align} $$

Let's substitute these values in the given equation:

Substitute the value of $(q - p)$ as $(lx1 - x1, ly1 - y1)$, then the equation becomes:

$$ t = ((lx1 - x1, ly1 - y1) \times (lx2 - lx1, ly2 - ly1)) / det|r,s| $$

Note $\times$ is the Vector Cross product

Expanding

$$ t = ((lx1 - x1) * (ly2 - ly1) - (ly1 - y1) * (lx2 - lx1)) /det|r,s| \longrightarrow {1} $$

Similarly

$$ \begin{align} u= (q-p) \times \vec r / \vec r \times \vec s\ \\ u = ((lx1 - x1, ly1 - y1) \times (x2 - x1, y2 - y1) / det|r,s| \ \\ \end{align} $$

Expanding

$$ u = ((lx1-x1) * (y2-y1) - (x2-x1) * (ly1-y1) / det|r,s| \longrightarrow {2} $$

Using the above two; code in Python

def intersect(line1, line2):
    """
        Checks if two line segments intersect 
        Note - line segments not lines
    """
    x1, y1 = line1[0]
    x2, y2 = line1[1]
    lx1, ly1 = line2[0]
    lx2, ly2 = line2[1]
    
    # Calculate direction vectors for both lines
    d1 = [x2 - x1, y2 - y1]
    d2 = [lx2 - lx1, ly2 - ly1]
    
    # Calculate determinant of the matrix formed by direction vectors
    det = (d1[0] * d2[1]) - (d1[1] * d2[0])
    
    # Check if the lines are parallel
    # https://math.stackexchange.com/a/424737/284422
    if det == 0:
        return False,-1
    
    # Calculate parameters of intersection point for both lines
    # Explanation https://stackoverflow.com/a/565282/429476

    # Implementation https://stackoverflow.com/a/1968345/429476
    t1 = ((d2[1] * (lx1 - x1)) - (d2[0] * (ly1 - y1))) / det
    #t2 = (d1[0] * (ly1 - y1) - d1[1] * (lx1 - x1)) / det
    t2 = ((d1[1] * (lx1 - x1)) - (d1[0] * (ly1 - y1))) / det
    
    # Check if the intersection point is within the range of both lines
    if 0 <= t1 <= 1 and 0 <= t2 <= 1:
        return True,[x1 + t1 * d1[0], y1 + t1 * d1[1]]
    
    return False,-1

To test

out = intersect(((0,1),(1,2)),((.5, .5),(1.75,1.25)))
print(out) # false correct

out = intersect(((0,2),(2,2)),((0, 1),(1,1))) # parallel
print(out) # false correct, determenent =0

out = intersect(((1,1),(2,0)),((1, 0),(2,1)))
print(out) # True - Correct [1.5, 0.5] 

out = intersect(((.7,0),(1,1)),((1, 0),(2,1))) 
print(out) # false - intersects at (0.571, -.429) but outside 

out = intersect(((0.7,1.6),(1,1)),((1, 0),(2,1)))
print(out) # false - intersects but outside 

out = intersect(((1.32,-.8),(1,1)),((1, 0),(2,1)))
print(out) #[1.150943396226415, 0.15094339622641506]