Intersection point of 2 lines defined by 2 points each

Question

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.

Answer 1

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.)

Answer 2

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 $\vec{ab}=b-a$. If the dot product $\vec{ab}\cdot\vec{ax}$ is positive, then $x$ is forward of $a$; if it's negative, then $x$ is behind $a$. Likewise, if $\vec{ab}\cdot\vec{bx}$ 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.

Answer 3

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_x}D, \quad s = \frac {Q_y}D$$

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 smaller than $|Q_x|$ or smaller than $|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.