Line-Line Intersection Detection Explained in Plain English

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!

Advertisements

I Got A New Toy – a Netbook

I got myself a used Samsung N210 netbook a few days ago. It had a 250 GB HDD and a whopping 1 GB of memory installed. (Here are the specs.) So, I had to tune the machine up a little. I replaced the HDD with a 240 GB SSD, and Kubuntu instantly started to perform in a much more acceptable speed. I’m still waiting for the 2 GB DDR2 memory module to arrive, as I’m intending to upgrade memory too. Too bad the machine cannot utilize more memory than that.

Here’s a picture:

Samsun N210

I’m intending to use the machine while on the go, so it doesn’t have to be as powerful as the computer I primarily use. The netbook is small, something like 10.5”, and weighs just over a kilogram, so it’s very portable. Ubuntu with LXDE runs satisfactorily fast.

Streamlined My JavaScript Build Configuration

I’m developing this web app on the visualization of mathematics, and I had set up a build configuration with two phases. I wrote the graph drawing code in ES6 JavaScript, then transpiled to ES5 JS (that browsers understand) with Babel and then ran that that through Browserify with the help of Gulp.

I, however, had a nagging doubt that this could be done more efficiently, avoiding the duplication of the code (or actually triplication due to Browserify). I found out how this could be done with a relatively quick search around the Interwebs.

I then decided to run Browserify directly in the ES6 folder, adding a Babelify transform to the process.

Here’s a snippet of my gulpfile.js:

gulp.task('bonsai', function() { // create a new Gulp task
    var bundleFiles = function(filenames) {
        filenames.forEach(function(filename) {
            var filenameWithoutExtension = filename.split('.')[0]; // split the filename at the dot and use the preceding element
            // this should probably be generated with the help of the Node 'path' module
            var sourceFilePath = './src/bonsai_movies/' + filenameWithoutExtension + '.js'; 
            var bundle = browserify([sourceFilePath]) // call Browserify
                .transform("babelify", {presets: ["@babel/preset-env"]}) // here we're changing the ES6 to ES5
                .bundle();
            bundle.pipe(source(filenameWithoutExtension + '.js')) // from...
                .pipe(gulp.dest('../js/bonsai_movie_bundles/')); // ... to
        });
    }

    // actually call the function, give the filenames under 'bonsai_movies' as parameters to it
    bundleFiles(fs.readdirSync('src/bonsai_movies'));
});

So now my codebase is simpler, cleaner and smaller. 🙂

Django Database Routing Was Broken But I Fixed It

I noticed today that the Django routing system was broken when using the manage.py administration script file, specifically when migrating new changes. After a little over an hour of debugging, I found a solution – I had to specify the database in the migrate command.

Like this:

python3 manage.py migrate myapp --database=mydatabase

Problem solved and everything works again!

Creating MySQL Users on the Command Line After Fresh Install

I’ve installed MySQL and PHPMyAdmin on my laptop, but I encountered an issue when logging in to the latter. I, however, was able to login to MySQL via command line as root. So I ran

sudo mysql

and wondered what to do next. The MySQL documentation was helpful after a little browsing. So, for first I created a user:

CREATE USER 'maija'@'localhost' IDENTIFIED BY 'P4ssw0rd';

Then I granted all privileges to myself:

GRANT ALL on *.* TO 'maija'@'localhost' WITH GRANT OPTION;

And I was able to log into PHPMyAdmin and actually do stuff there.

How to Configure PHPMyAdmin on a Local Apache Server

I installed PHPMyAdmin on my Linux laptop via apt-get, but when I tried to navigate to the address localhost/phpmyadmin, there was a 404 Not Found error. I’ve been dealing with this issue before, so I kind of knew what to do.

What I had to do was to add the following entry to the Apache configuration file (residing in /etc/apache2/apache2.conf):

Include /etc/phpmyadmin/apache.conf

Then I had to run the following command to restart Apache:

sudo systemctl restart apache2

and I was able to navigate to PHPMyAdmin.

Now all that’s left is the user setup (I won’t be root all the time).

Source – Stack Overflow

Fixed a Unity Problem with Editor Scripts

I was coding a little game in Unity, and briefly moved all of my scripts to the Assets/Scripts/Editorfolder for unit testing. This, however, caused problems later on when I moved them back to the Scripts folder, as Unity still thought they were Editor scripts. The error was

Can't add script behaviour NewBehaviourScript because 
it is an editor script. To attach a script it needs to be 
outside the 'Editor' folder.

I tried various things as I attempted to solve the problem. I finally found the solution – the files were told to reside in the Editor folder in the MyProjectAssemblyDefinition.csproj file. There was a block like this…

  <ItemGroup>
    <Compile Include="Assets\Scripts\Editor\GameMasterScript.cs" />
    ...
  </ItemGroup>

So I removed the “Editor” from each <Compile /> entry like this:

<Compile Include="Assets\Scripts\GameMasterScript.cs" />

…and everything worked again.