• 3D to 2D projection - like in the good old days
• Extracting text from PDF files with PHP
• GetJPGInfo - retrieving type, width and height from a JPG image with ASP/VB
• Extended ActionScript Date methods : getWeek() and getDayOfYear()
• Getting the intersection point of two straight lines with Actionscript
• pdf2jpg - Converting PDF to JPG with Photoshop Scripting
• Counting the pages of a PDF document with PHP
• Client-server communication with Flash : Common pitfalls
• Unable to Fork - Running PHP exec/system on IIS

Getting the intersection point of two straight lines with Actionscript

There are a number of situations where you might want to know where two lines cross. I bumped into the problem developing a car racing game when I wanted to check if one road crossed another and a bridge was neccessary. I found some articles on the internet about it, but wanted to see if I could solve it myself, maybe in a better way? Also it's nice to finally find a use for some of those old schoolmaths.

There is some ready-to-use code and an example at the end of the page, so if you don't care about understanding the maths, just go there directly.

The two lines are each defined by two sets of coordinates (points A and B):
Line1: x1A,y1A to x1B,y1B
Line1: x2A,y2A to x2B,y2B

The basic straight line equation

All of the maths here derive from the basic straight line equation, which is:

y = k * x + m

This equation means that the y coordinate is dependant upon the x coordinate, and two constants - k and m.

Getting K

The k constant has to do with direction and indicates how much y will change for every change in x. If k is 1, y will follow x exactly, giving a 45 degree "diagonal" line. If k is 0, y will not change at all as x does, giving a horizontal line. We can calculate k for a given line by dividing the difference between y for the two defining points, divided by the difference in x, so for line 1 it's:

k1 = (y1B-y1A) / (x1B-x1A)

Getting M

The m constant displaces the line vertically, it is the y coordinate that the line will have when x is 0. If m is 0, the line will go through origo. We can calculate m for a line using the k constant and either one of the two defining points, by swapping things around in the basic equation, like so:

y	=	k * x + m	The basic straight line equation
y - k * x	=	m	Subtracting k * x over to the left side
m	=	y - k * x	Just switching sides
m1	=	y1A - k1 * x1A	This will be for line 1

Getting X

So now that we can get k and m for the two lines, we need a way to get x and y for the intersection point, expressed through these k and m constants. We'll start with x. Since the intersection point is where x and y for the two lines are equal, we can merge the basic line equations for the two lines, like this:

y	=	k1 * x + m1	Equation for line 1
y	=	k2 * x + m2	Equation for line 2
k1 * x + m1	=	k2 * x + m2	Putting two right sides together like this gives us the case where the y of two lines are equal
k1 * x + m1 - m2	=	k2 * x	Getting m2 over to the left side
( k1 * x + m1 - m2 ) / x	=	( k2 * x ) / x	Dividing both sides by x
k1 + ( m1 - m2 ) / x	=	k2	Now we only have one x, nice!
( m1 - m2 ) / x	=	k2 - k1	Getting k1 over to the right side
( m1 - m2 ) / ( k2 - k1 )	=	x	Do a little swapping around
x	=	( m1 - m2 ) / ( k2 - k1 )	Neater this way, and done!

Getting Y

And now that we have the x coordinate of the intersection point, and the k and m constants, getting y is a piece of cake. This is just what the basic straight line equation is for! We can use the k and m from either of the lines. It will give the same y result, since it's the intersection point we're talking about. So either:

y = k1 * x + m1

...or...

y = k2 * x + m2

Parallel lines

Since parallel lines do not intersect by definition, the above will not work for such lines. Good thing parallels are easy to spot - they simply have the same k value. This will give us trouble when trying to calculate x, since (k2-k1) will be zero and as we divide by zero, x will be Infinity. In my code below I just return undefined for lines where k1 == k2.

Vertical lines

Vertical lines cannot be described by the basic straight line equation, because for them, y cannot be said to depend on x. Instead, x is constant, and y is sort of every value simultaniously. Furthermore, a vertical line has a k value of Infinity (since x1B-x1A will be zero), which is how you identify them. Anyway, this doesn't make them impossible - in fact they are easiler to deal with. Just skip calculating m, and use the x coordinate of either of the defining points. Then, calculating y, use the k and m values from the other line. So what if they're both vertical? Well then they're parallel aren't they? - see above.

Intersection is "not on the line"

This algorithm will always get you an intersection point, regardless of wether it's located between the defining points or not. So, if this is a problem for you, just check if the x coordinate of the intersection point is between the x coordinates of the definition points. There is no real need to check y as well. In the code and in the example, I've included an algorithm for this, that neatly takes care of any reversed order of starting and ending points. The definition is that the point should be on one side of the starting point, and on the other side of the ending point:

within = ( ( x < start ) != ( x < end ) )

Downloadable example

You can download an example implementing the code below with this link.

The code

function lineIntersection( x1A,y1A,x1B,y1B, x2A,y2A,x2B,y2B )
{
    // calculate directional constants
    var k1 = (y1B-y1A) / (x1B-x1A);
    var k2 = (y2B-y2A) / (x2B-x2A);
    
    // if the directional constants are equal, the lines are parallel,
    // meaning there is no intersection point.
    if( k1 == k2 ) return undefined;
    
    var x,y;
    
    // an infinite directional constant means the line is vertical
    if( !isFinite(k1) )
    {
        // so the intersection must be at the x coordinate of the line
        x = x1A;
        
        // compute y offset constants for line 2
        var m2 = y2A - k2 * x2A;
        
        // use
        // y = k * x + m
        // to get y coordinate
        y = k2 * x + m2;
    }
    // same as above for line 2
    else if( !isFinite(k2) )
    {
        var m1 = y1A - k1 * x1A;
        
        x = x2A;
        y = k1 * x + m1;
    }
    // if neither of the lines are vertical
    else
    {
        // compute y offset constants for both lines
        var m1 = y1A - k1 * x1A;
        var m2 = y2A - k2 * x2A;
        
        // compute x
        x = (m1-m2) / (k2-k1);
        
        // use
        // y = k * x + m
        // to get y coordinate
        y = k1 * x + m1;
    }
    
    return {x:x,y:y};
}

function inRange( v, vA, vB )
{
    return v <= vA != v < vB;
}