Crthuky

I'm implementing this in code, but I'll rewrite it so that it is easier understood (like pseudocode):

# a = pt 1 on line 1
# b = pt 2 on line 1
# c = pt 1 on line 2
# d = pt 2 on line 2
def intersect(a,b,c,d):

 # stuff for line 1
 a1 = b.y-a.y
 b1 = a.x-b.x
 c1 = a1*a.x + b1*a.y

 # stuff for line 2
 a2 = d.y-c.y
 b2 = c.x-d.x
 c2 = a2*c.x + b2*c.y

 determinant = a1*b2 - a2*b1

 if (determinant == 0):
 # Return (infinity, infinity) if they never intersect
 # By "never intersect", I mean that the lines are parallel to each other
 return math.inf, math,inf
 else:
 x = (b2*c1 - b1*c2)/determinant
 y = (a1*c2 - a2*c1)/determinant
 return x,y

All the above works, ... but only does by assuming that the lines extend infinitely in each direction, like a linear equation. I'll show what I mean here.

There are the 2 lines, red and green, and the gold dot is what is returned when I test this code ... but the lines don't actually intersect. What can be used to test whether the lines truly intersect?

Heres the actual Python code if needed.

I think you are asking for the intersection point (if any) of two line segments, not two lines.

Once you find the intersection point $P$ as you have, you can check that it is between the endpoints $A$ and $B$ of a segment by solving the equation
$$
tA + (1-t)B = P
$$
for $t$ and checking that $t$ is between $0$ and $1$. That equation will have a solution because you know $P$ is on the line. Do that for each of the two segments.

Warning: you may have numerical instability if the determinant is close to $0$. That will happen when the lines are nearly parallel.

(There may be a shorter way to do this from scratch, but this will work.)

You have the point $x$ where the infinite lines intersect. You need to check whether that point is on both finite line segments.

Line segment 1 has endpoints $a$ and $b$. Use these to make a vector $vecab=b-a$. If the dot product $vecabcdotvecax$ is positive, then $x$ is forward of $a$; if it's negative, then $x$ is behind $a$. Likewise, if $vecabcdotvecbx$ is positive, then $x$ is forward of $b$. The point $x$ is on the segment if it's between $a$ and $b$.

Do the same test for the other line segment.