In school I learned one thing – that I’m bad at math. I got poor grades and felt confused during lessons. That’s why I never thought I’d become a computer engineer. But look where I’m now, I code for a living.

I’ve come to the conclusion that I’m a visual person. I always felt like geometry and trigonometry were the easier fields of mathematics for me, rather than abstract algebra. I’ve recently started to learn math by coding. I still have my old high school math books, and right now I’m learning analytic geometry, that is, geometry in a coordinate system.

I once borrowed a book on game programming from my school library, but I was hopelessly lost when reading the sections about math, like collision detection. However, with hard work, I’ve started to feel a bit more enlightened about the subject. That’s why I’m here writing this blog post – I want to share what I’ve learned with others.

This post will be about intersection detection between line segments.

In my experience, with just that knowledge you’ll get pretty far when developing small games et cetera. Of course, Unity and other game engines have made collision detection very easy with colliders, but that’s another story.

Here’s the code that I’ll go through in the form of a runnable fiddle.

### Linear Equations

For first we’ll need a programmatical representation of a linear equation. A linear equation is an equation that represents a line. You can input the equation in e.g. a graphing calculator, and a line gets plotted out. Linear equations are in the following form:

*y = ax + b*

The variables *y* and *x* represent the coordinates of a single point on the line. The variable *a* is the slope of the line, i.e. how steep the line is and whether it’s ascending or descending. When *a* is positive, the line is ascending, and when negative, it’s descending. The variable *b* is called the y-intercept, and it describes where the line crosses the *y* axis. Here’s an article on linear equations.

Here’s how I decided to represent linear equations:

```
class LinearEquation {
constructor(args = {}) {
const { slope, yIntercept } = args;
this.slope = slope;
this.yIntercept = yIntercept;
}
}
```

We get the common points of lines by creating a system of equations from their equations and solving that. If we have, for example, the following two equations:

*A) y = 3x – 4*

*B) y = 2x + 3*

we can attempt to find their common points.

Two lines have either 1) zero, 2) one, or 3) infinitely many points in common. In case 1 the lines are parallel but not coincident. In case 2 the lines cross each other, and in case 3 the lines are coincident (they are “on top of one another”). We are most likely dealing with case 2.

### Systems of Equations

We can solve for x by taking the rightmost part of equation A and putting it in place of the y in equation B. We get:

*3x – 4 = 2x + 3*

Now we can solve the equation in the traditional way…

*3x – 2x = 3 + 4*

*x = 7*

Then we can solve for y by replacing the *x* in the first equation with the value we got:

*y = 3 * 7 – 4 *

y = 21 – 4

*y = 1*

Here’s an article about systems of linear equations.

But how to do this in code? Here’s my take on the problem:

```
class LinearEquation {
...
static solveSystem(equation1, equation2) {
const slopes = equation1.slope - equation2.slope;
const yIntercepts = equation2.yIntercept - equation1.yIntercept;
const x = yIntercepts / slopes;
const y = equation1.slope * x + equation1.yIntercept;
return { x, y };
}
}
```

For first, the multiplier of x on the left side of the equation is calculated (line 11). Next, the constant part is calculated (line 12). X is solved by dividing the constant with the multiplier of x (line 13). Finally, y is calculated by replacing x in one of the equations with the previous result (line 14). An object containing the coordinates of the intersection point is returned (line 15).

### Intersection Testing

Now we have the tool for finding out where two lines intersect. However, the previous function deals with lines with infinite length, not line segments. Also, we must deal with the special cases of line intersection. These problems are handled with the following method:

```
intersects(otherLineSegment) {
const equation1 = this.linearEquation;
const equation2 = otherLineSegment.linearEquation;
// slopes are identical but the y intercepts are different - lines are parallel and
// there are no common points
if (equation1.slope === equation2.slope && equation1.yIntercept !== equation2.yIntercept) {
return false;
}
// lines are identical
else if (equation1.slope === equation2.slope && equation1.yIntercept === equation2.yIntercept) {
return true;
}
const intersectionPoint = LinearEquation.solveSystem(equation1, equation2);
if (this.isOnLineSegment(intersectionPoint) && otherLineSegment.isOnLineSegment(intersectionPoint)) {
return true;
}
return false;
}
```

The two special cases are handled first. If the lines are coincident, the method returns true (line 41). If they are parallel but not coincident, the method returns false, as the lines do not intersect (line 45). Only if the lines are neither coincident or parallel, the intersection is calculated (line 48). Last, it is checked if the intersection point lies on both of the line segments (line 49) – it might be the case that the infinitely long lines intersect, but the segments do not.

The `slope`

is a simple getter function. It calculates the slope with a mathematical formula:

```
get slope() {
return ((this.endPoint.y - this.startPoint.y) / (this.endPoint.x - this.startPoint.x));
}
```

Now we can draw a pair of lines, check if they intersect, and render the result (lines 76-135). I used the HTML5 canvas element to do that. I have also added unit tests using Mocha and Chai to the end of the code in order to verify it is working correctly.

Happy hacking!