Check if two lines intersect

Question

I have a non-linear line with these coordinates:

(1,50)(2,40)(3,45)(4,40)(5,60)(6,30)

When I draw the line passing through each of these points, noted line A, I can visually see that another straight line drawn from last to first point only - from (1,50) to (6,30) - noted line B, would intersect/cross line A.

My goal is to be able to mathematically check that line B does NOT intersects with line A, is there some equation or approach I could go with to check that?

EDIT: Sorry for the misleading "line" word I use, I should have used curve. Here is the representation of what I meant (credits to Joffan):

Answer 1

Assuming that Line A is a piecewise linear curve and your issue is illustrated by:

(line A blue, line B orange), you can essentially use the basic line intersection equations to check whether each line segment in line A intersects line B between the limits of interest or not.

In this particular case, since the points of line A are in monotonic (here, ascending) $x$ order and line A starts on one side of line B and finishes on the other, you have a shortcut; there will definitely be an intersection somewhere. Also with the same restriction on the order of points on line A, you can check dot product for each line from $a_1$ to successive points $a_i$ against line B (which is $a_1$ to $a_n$) and check if the sign changes, indicated that the point is now the other side of line B, localizing the intersection (and finding multiple intersections if occurring). If you have intermediate points that are outside the $x$-limits of the points that define line B, this may not work:

Answer 2

Got an elegant answer here, with two functions (in python, but Mathematically readable):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Joffan helped me reformulate my problem with his comment I suspect that your "line A" is a curve made of linear segments which made my research much easier with a lot more results like the mentioned solution.

Answer 3

To find out if a line segment $(x_1, y_1) - (x_2, y_2)$ intersects a line segment $(\chi_1, \gamma_1) - (\chi_2, \gamma_2)$, parametrise the two line segments using $0 \le t \le 1$ and $0 \le \tau \le 1$, $$\left\lbrace \; \begin{aligned} x(t) &= (1 - t) x_1 + t x_2 = x_1 + t (x_2 - x_1) \\ y(t) &= (1 - t) y_1 + t y_2 = y_1 + t (y_2 - y_1) \\ \end{aligned} \right.$$ $$\left\lbrace \; \begin{aligned} \chi(\tau) &= (1 - \tau) \chi_1 + \tau \chi_2 = \chi_1 + \tau (\chi_2 - \chi_1) \\ \gamma(\tau) &= (1 - \tau) \gamma_1 + \tau \gamma_2 = \gamma_1 + \tau (\gamma_2 - \gamma_1) \\ \end{aligned} \right.$$ and solving $x(t) = \chi(\tau)$ and $y(t) = \gamma(\tau)$ for $t$ and $\tau$. If $0 \le t \le 1$ and $0 \le \tau \le 1$, the line segments intersect, otherwise they do not intersect.

Note that if any of the following are true, the two line segments cannot intersect: $$\begin{aligned} \max(x_1 , x_2) &\lt \min(\chi_1 , \chi_2) \\ \min(x_1 , x_2) &\gt \max(\chi_1 , \chi_2) \\ \max(y_1 , y_2) &\lt \min(\gamma_1 , \gamma_2) \\ \min(y_1 , y_2) &\gt \max(\gamma_1 , \gamma_2) \\ \end{aligned}$$ If none of the four are true, then the axis-aligned bounding boxes for the two line segments overlap. If any of the four are true, then they do not.

Instead of calculating $t$ and $\tau$, we can avoid a division if we instead use $t^\prime = t D$ and $\tau^\prime = \tau D$, and verify $t^\prime$ and $\tau^\prime$ are between $0$ and $D$, noting that $D$ may be positive or negative: $$\begin{aligned} D &= ( x_1 - x_2 ) ( \gamma_2 - \gamma_1 ) - ( \chi_1 - \chi_2 ) ( y_2 - y_1 ) \\ t^\prime &= x_1 ( \gamma_2 - \gamma_1 ) + \chi_1 ( y_1 - \gamma_2 ) + \chi_2 ( \gamma_1 - y_1 ) \\ \tau^\prime &= x_1 ( y_2 - \gamma_1 ) + x_2 ( \gamma_1 - y_1 ) + \chi_1 ( y_1 - y_2 ) \\ \end{aligned}\tag{1}\label{G1}$$ but note that $D = 0$ if the two lines are parallel.

My preferred solution in the parallel line case is to rotate the coordinate system, bringing one of the lines horizontal. Then, it is relatively straightforward to check if they overlap.

Rotation matrix $\mathbf{R}_{12}$ that brings the line segment $(x_1, y_1) - (x_2, y_2)$ horizontal is $$\mathbf{R}_{12} = \frac{1}{\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}}\left[ \begin{matrix} x_2 - x_1 & y_2 - y_1 \\ y_2 - y_1 & x_1 - x_2 \\ \end{matrix} \right ]$$ but in this case, the scaling factor can be omitted; then, the transformed coordinates are just scaled by the length of the first line segment.

Here is an example implementation on Python:

def intersect(x1,y1,x2,y2, x3,y3,x4,y4):

    # No intersection if axis-aligned bounding boxes do not overlap.
    if (max(x1, x2) < min(x3, x4) or
        min(x1, x2) > max(x3, x4) or
        max(y1, y2) < min(y3, y4) or
        min(y1, y2) > max(y3, y4)):
        return False

    d = (x1-x2)*(y4-y3) - (x3-x4)*(y2-y1)
    if d > 0:
        t12 = x1*(y4-y3) + x3*(y1-y4) + x4*(y3-y1)
        if t12 < 0 or t12 > d:
            return False

        t34 = x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)
        if t34 < 0 or t34 > d:
            return False

        return True

    elif d < 0:
        t12 = x1*(y4-y3) + x3*(y1-y4) + x4*(y3-y1)
        if t12 > 0 or t12 < d:
            return False

        t34 = x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)
        if t34 > 0 or t34 < d:
            return False

        return True

    # d == 0, and the two line segments are parallel.

    # Transform coordinate system so that
    # (x1,y1)-(x2,y2) becomes (0,0)-(L,0), and
    # (x3,y3)-(x4,y4) becomes (xa,ya)-(xb,yb),
    # or vice versa.

    # Which of the two line segments is longer?
    x12 = x2-x1
    y12 = y2-y1
    x34 = x4-x3
    y34 = y4-y3
    L12 = x12*x12 + y12*y12
    L34 = x34*x34 + y34*y34
    if L12 > L34:
        x31 = x3 - x1
        y31 = y3 - y1
        x41 = x4 - x1
        y41 = y4 - y1
        ya = y12*x31 - x12*y31
        yb = y12*x41 - x12*y41

        # If both endpoints of the second line are on the same side,
        # we assume it is outside.  Any other case is within rounding error.
        if (ya < 0 and yb < 0) or (ya > 0 and yb > 0):
            return False

        xa = x12*x31 + y12*y31
        xb = x12*x41 + y12*y41
        return min(xa, xb) <= L12 and max(xa, xb) >= 0

    elif L34 > 0:
        x13 = x1 - x3
        y13 = y1 - y3
        x23 = x2 - x3
        y23 = y2 - y3
        ya = y34*x13 - x34*y13
        yb = y34*x23 - x34*y23

        # If both endpoints of the second line are on the same side,
        # we assume it is outside.  Any other case is within rounding error.
        if (ya < 0 and yb < 0) or (ya > 0 and yb > 0):
            return False

        xa = x34*x13 + y34*y13
        xb = x34*x23 + y34*y23
        return min(xa, xb) <= L34 and max(xa, xb) >= 0

    # Both line segments are degenerate; zero length.
    return (x1 == x3) and (y1 == y3)

if __name__ == '__main__':
    from random import Random
    prng = Random()

    rows = 40
    cols = 8
    color = { True:"#FF0000", False:"#0000FF" }

    print("""<!DOCTYPE html><head><title>Intersections</title><meta http-equiv="Content-Type" content="html;charset=UTF-8"><style type="text/css">
html, body { background: #ffffff; color: #000000; margin: 0 0 0 0; border: 0px none; padding: 0 0 0 0; }
table { margin: 0 0 0 0; border: 0px none; padding: 0 0 0 0; border-collapse: collapse; }
tbody, tr { margin: 0 0 0 0; border: 0px none; padding: 0 0 0 0; }
td { margin: 0 0 0 0; border: 0px none; padding: 0.5em 0.5em 0.5em 0.5em; }
svg { margin: 0 0 0 0; border: 1px solid #999999; padding: 0 0 0 0; }
</style><body><table>""")
    for r in range(0, rows):
        print("<tr>")
        for c in range (0,cols):
            x1 = prng.uniform(0.1, 9.9)
            y1 = prng.uniform(0.1, 9.9)
            x2 = prng.uniform(0.1, 9.9)
            y2 = prng.uniform(0.1, 9.9)
            x3 = prng.uniform(0.1, 9.9)
            y3 = prng.uniform(0.1, 9.9)
            x4 = prng.uniform(0.1, 9.9)
            y4 = prng.uniform(0.1, 9.9)
            isect = intersect(x1,y1,x2,y2,x3,y3,x4,y4)
            print("""<td><svg xmlns="http://www.w3.org/2000/svg" version="1.1" viewBox="0 0 10 10">
<rect x="0" y="0" width="10" height="10" fill="#ffffff" stroke="none"/>
<path d="M%.6f%+.6f L%.6f%+.6f M%.6f%+.6f L%.6f%+.6f" fill="none" stroke="%s" stroke-width="0.1"/>
</svg></td>""" % (x1,y1,x2,y2,x3,y3,x4,y4,color[isect]))
        print("</tr>")
    print("</table></body></html>")

When run, it emits an HTML page with 320 random tests. Non-intersecting line pairs are in blue, and intersecting line pairs in red. Redirect the output to a file, say python3 above.py > results.html, and you can open the file in your favourite browser to see the test results.

Answer 4

To find out whether two lines defined by points $(p_1, p_2)$ and $(p_3, p_4)$ intersect within the part of the line truncated by the points, first of all check whether any of the points are identical. If not, then compute $\delta=p_2-p_1$ and $\gamma=p_4-p_3$, then compute the determinant $$ d = \begin{vmatrix} \delta_x & \gamma_x \\ \delta_y & \gamma_y \\ \end{vmatrix} $$ If this is zero, the two lines are parallel, so there is no intersection. If it is not zero, let $\alpha=p_3-p_1$ and compute $$ \begin{align} s&=(\gamma_y\alpha_x - \gamma_x\alpha_y)/d\\ t&=(-\delta_y\alpha_x + \delta_x\alpha_y)/d\\ \end{align} $$ The value of $s$ is the intersection of the two lines relative to $p_1$ and $p_2$, with $s=0, 1$ representing $p_1$ and $p_2$ respectively, and the value of $t$ is similarly the offset of the intersection of the two lines relative to $p_3$ and $p_4$. For the lines to intersect within the two points, both $s$ and $t$ must be $\in[0,1]$.

These formulas originate from a Wikipedia article, but they are improved for practical computation.