Wait, is that a blog of some sort?

• Leftward or rightward?
• One Last Corner Case
• The Code
• And the Demo

---

Geometric things have always been really tricky to program for me, and quite a lot of other people as well. I think I need more practice coding geometric stuff and explaining them in a post would help me remember them well. So I decided this would be the first step since finding whether two line segments on a cartesian plane intersect or not is pretty much the simplest problem to be faced in computational geometry. And hopefully, this will be the first in a series of blog posts.

So, how do we find whether two lines are intersecting? In the first example; consider the red line segment, and the line segment from top of red segment to both ends of the green segment.Call them $\bf{a}$, $\bf{b_1}$ and $\bf{b_2}$ respectively.

So, just check whether the opposite ends of the second segment are on the opposite sides of the first segment, right? Well, there is an (pretty obvious) exception to that:

In this case; one end of the green line segment is to the left of the red one and the other one is to the right, but they don’t intersect. To solve this, just check for both line segments.

---

Leftward or rightward?

That leaves us with one more question, how do we find out if a vector is to the left or to the right of another one. And the answer for that, is the Cross Product. The cross product $\bf{a}\times\bf{b}$ results in a vector perpendicular to the plane the vectors $\bf{a}$ and $\bf{b}$ are in, so in case of 2-dimensional vectors, the resultant vector only has the z component. For 2-Dimensional vectors; the cross product is calculated as

$$\|\bf{a}\times\bf{b}\|=(\bf{a}\times\bf{b})_z = \bf{a}_x \bf{b}_y - \bf{b}_x \bf{a}_y$$

Due to the anticommutativity¹ of the cross product, we can find the order vectors are oriented, i.e. whether a vector is to the left or right of the other one². In 2-dimensions; If $\|\bf{a}\times\bf{b}\|>0$; $\bf{a}$ is to the right of $\bf{b}$, and vice versa if the product is negative. The vectors are collinear if the cross product is equal to zero. There is a right-hand rule for that, but most of the times, I can’t remember the rule, the easy way to come up with is just check the cross product of two vectors, say $\begin{bmatrix}1 & 1\end{bmatrix} \times \begin{bmatrix}1 & 2\end{bmatrix}$ and see if it is positive or negative.

---

One Last Corner Case

If two line segments lie on the same line, this method will always return false, whether there is overlap between line segments or not. To cover this case, we can check for both ends of the second line if they are within the first line or not. To do that; we can find the corresponding line to the line segment ($a_x$, $a_y$) – ($b_x$, $b_y$), which is

$$y - a_y = \frac{b_y-a_y}{b_x-a_x}x-a_x$$

and test if the point tested satisfies the equation and check if its x coordinate lies between $a_x$ and $b_x$. If one of the endpoints of the second line segment is contained within the first one, then those line segments intersect.

---

The Code

The intersection checking code is pretty short, about 35 lines long in my javascript implementation. In terms of time and memory, it obviosly has $O(1)$ complexity, since what we’re doing is just a few mathematical operations regardless of the size, shape etc. of the line segments.

The code(for line segment intersection, the demo and drawing line segments on canvas) can be found here: https://github.com/kuzux/kuzux.github.com/blob/master/line-segment-intersection.js

---

And the Demo

Usage: Just click around in the area below :)