# 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?

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

• sorry for lately asking this question. Can you please explain why you need to test only X coordinate to know the lines segment intersect not both X and Y coordinate. Thanks in advance. – Trying Aug 28 '13 at 10:16
• @Trying: Two lines can only intersect in one point. If the $x$-coordinate to that point is outside the given interval, then the two line segments will not intersect. – Thomas Aug 28 '13 at 15:11
• Depending on how ones calculates the intersection, this algorithm may not work for vertical line segments, since the slope is undefined. – Ceasar Bautista Apr 23 '18 at 20:54

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.

• I think this is essentially what Thomas described at the end of his answer. – daveMac May 25 '12 at 16:24
• I was mainly trying to clarify that concept, and point out that it could be within the right x values but not count as an intersection point because it's still outside of the right y values, which his answer didn't mention. – Robert Mastragostino May 25 '12 at 17:02
• That is very true about the need to check the y as well. (I think I just took that for granted.) – daveMac May 25 '12 at 17:34

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.

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.

• As it seems the OP is using "line" to mean "line segment", in the case that the slopes are different, it is also necessary to check whether the intersection occurs in the necessary segments, which is easy enough to do from the coordinates of the intersection point. – mdp May 25 '12 at 12:39
• I updated my question to clarify that I am trying to figure out if the line "segments" intersect. – daveMac May 25 '12 at 14:55

A necessary condition to check the turn it makes. Assume $U$ and $V$ to be the vectors of the segments where $U=(u_{x_2} - u_{x_1}, u_{y_2}-u_{y_1})$, likewise for $V$.

If $((u_{x_1}, u_{y_2}) - (v_{x_1},v_{y_1}) ) * V < 0$, they will intersect. If the scalar product is positive does not intersect. Otherwise, this fast test doesn't apply.