Finding out whether two line segments intersect each other

I need to know whether or not two line segments intersect. I thought the formula for that is $y = mx + b$, but I don't think that will work for what I need; at least, I think I need to first know whether the line segments intersect, because that formula just gives the point where the two lines will eventually intersect.

For example, say I have two line segments. Line $1$ has a starting point of $(15, 10)$ and its ending point is $(30, 17)$. Line $2$ has a starting point of $(29,5)$ and an ending point of $(33, 14)$. These shouldn't intersect within those coordinates, but, by using $y = mx + b$, I find that they approximately intersect at $(35, 19.5)$.

How can I find out whether these line segments happen to intersect each other?

Solution 1:

The only reason that two lines will not intersect is if they are parallel. Being parallel is the same as having the same slope. So, in your example, line $1$ has slope

$$\frac{17 - 10}{30 - 15} = \frac{7}{15}.$$

Line $2$ has slope

$$\frac{14 - 5}{33 - 29} = \frac{9}{4}.$$

Since these two numbers are not the same, the lines are not parallel, and they intersect somewhere.

Now, if what you are considering is only the line segment between the two points, I would first consider the slopes as we just did. If they are parallel, then for sure you know that they do not intersect. If, however, the slopes are different, then they will intersect in one point. You then need to find this point, and see if it happens in bounds given on the $x$-values.

So, when you find that the lines intersect at the point $(35, 19.5)$, then this intersection is outside the bounds given, since, e.g., your first line only goes from $x = 15$ to $x = 30$. It never reaches $x = 35$.

Solution 2:

I'm assuming you can already check intersection of lines, as that's already been answered and you seem to understand it fine.

The segments are $AB$ and $CD$. They intersect if their intersection point lies within the darker middle rectangle (i.e. the area in space that they both occupy). In other words, if the intersection point is $(x,y)$, then $x$ must be less than the smallest right-side value (the $x$-coordinate of $AH$ here), and larger than the smallest left-side value ($GB$). Here the check $x>GB_x$ fails, so they don't intersect. The idea is similar for $y$ values, and it has to pass all 4 tests (two for $x$ and two for $y$) before you can conclude that they intersect.

Solution 3:

There are two cases to consider when determining if two line segments $AB$ and $CD$ intersect: (1) The line segments are not co-linear (top three images in the following figure); (2) the line segments are co-linear (bottom two images).

The standard $y = mx + b$ is not generally useful as it omits vertical lines. Here it is best to consider the following implicit function $h(P)$ for a line passing through $A$ and $B:$ $$ h(P) = (B - A) \times (P - A)= 0 $$ where $U \times V = U_x \cdot V_y - U_y \cdot V_x.$ Note that $h(P)$ defines a half space by determining where the point $P$ lies relative to the boundary line through $AB:$ $$ \begin{array}{ll} h(P) > 0 & \mbox{$P$ in positive half-space} \\ h(P) = 0 & \mbox{$P$ on the line} \\ h(P) < 0 & \mbox{$P$ in negative half-space} \end{array} $$ Thus we know if the points $C$ and $D$ straddle the (infinite) line through $AB$ if both $h(C)$ and $h(D)$ are non-zero and have opposite signs. In the general case, we know the line segments $AB$ and $CD$ intersect if the points $C$ and $D$ straddle the line through $AB$ and the points $A$ and $B$ straddle the line through $CD.$

First we must handle the co-linear case where $h(C) = 0$ and $h(D) = 0.$ Here we have an intersection iff $$ \min(C_x,D_x) \leq max(A_x,B_x) \wedge \max(C_x,D_x) \geq \min(A_x,B_x) $$ and $$ \min(C_y,D_y) \leq max(A_y,B_y) \wedge \max(C_y,D_y) \geq \min(A_y,B_y) $$

Otherwise, in the general case we use our half space equations. The half space $g(x)$ defined by $CD$ is $$ g(P) = (D - C) \times (P - C) = 0. $$ We have an intersection where $$ (h(C) \cdot h(D) \leq 0) \wedge (g(A) \cdot g(B) \leq 0). $$

If you wish to know the actual intersection point you plug the parametric equation $L(t)$ for a line through $AB$ $$ L(t) = (B - A)\cdot t + A, \ \ \ -\infty < t < \infty $$ into $g$ and solve for $t:$ $$ g(L(t)) = (D - C) \times (L(t) - C) = 0 \\ (D - C) \times ((B - A)\cdot t + A - C) = 0 \\ t = \frac{(C - A) \times (D - C)}{(D - C) \times (B - A)} $$ Plug this value for $t$ back into $L(t)$ and you have your intersection point. Of course the assumes the caveat that $(D - C) \times (B - A) \neq 0$ where the lines are not parallel.

Another great explanation for this can be found here.

Solution 4:

If two lines have unequal slope they will intersect in a a point. If two lines have equal slope, they are either disjointly parallel and never intersect, or they are the same line.