Ttykuu

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.

This is an elaboration on Ethan Bolker's post.

Every point on the line segment from $a$ to $b$ can be expressed as $$a + t(b-a)$$ for some $t$ between $0$ and $1$. Likewise, every point on the line segment from $c$ to $d$ can be expressed as $$c + s(d-c)$$ for some $s$ between $0$ and $1$. Any intersection point can be expressed in both forms, so we will have

$$a + t(b-a) = c + s(d - c)$$
re-arranging,
$$t(b - a) + s(c - d) = c - a$$

Letting $n = b - a, m = c-d$, and $p = c - a$, and switching to coordinates, we have
$$n_xt + m_xs = p_x\n_yt + m_ys = p_y$$

Instead of solving directly for the coordinates of the point of intersection, you should solve for $t$ and $s$. Letting
$$D = n_xm_y - n_ym_x\Q_x = m_yp_x - m_xp_y\Q_y =n_xp_y - n_yp_x$$

We have $$t=frac Q_xD, quad s = frac Q_yD$$

In particular, we can figure out the following before doing the divisions:

• If $D$ is $0$, then the segments are parallel - the only way they can intersect in a unique point is if the two segments are adjacent and have a common endpoint (for instance $b = c$, and $a$ and $d$ are on opposite sides of the common point).


• If $D$ is the opposite sign of either $Q_x$ or $Q_y$, then one of $t$ or $s < 0$, so the line segments do not intersect.


• If $|D|$ is larger than either $|Q_x|$ or $|Q_y|$, then one of $t$ or $s > 1$, and again the line segments do not intersect.


• Otherwise, the segments do intersect, and you either calculate $t$ and $a + t(b -a)$ or calculate $s$ and $c + s(d - c)$ to get the point of intersection.

This is a more numerically stable approach to the problem.