All for the love of tables

Main
Links
Gallery
Projects
Mail me
Routines


	Routines

Quick index
Line collision detection Chrome mapping Screen blurring Tutorial 1 Tutorial 2 Tutorial 3

Line collision detection

Introduction
To start this new section of my web site off, I thought I'd like to share with you a routine I thought up for detecting if two lines intersect or not. This is probably not the best way of doing it, but it's my way and the only one I could think of. I don't claim to be the first person to think of this routine as it's probably been explained before, but I've not managed to find any info on this topic around, so I devised this one on a five hour trip down to Cornwall. The rest of my efforts that were thought up during the journey will be added to the page in due course. If any of the algorithm descriptions have a blue box with a small Playstation icon in them (look closely), then clicking on this will download a demo executable and its corresponding source files. Some have a small picture frame icon as well and clicking on this will download a screenshot of the executable.

Step 1

Assume you start with two pairs of end-points, forming two lines. In this explanation, the lines are defined using the points (A, B) and (C, D).

Step 2

The next thing to do, is find the two end-points that neighbour the intersect of the lines in the horizontal direction. This is the same as ordering the points according to their x values, then taking the second and third points. In the example, these points are A and D. The next thing to do is to clip the lines so that new points A', B', C' and D' are found. These are points on the original lines that also lie on vertical lines that pass through the two points neighbouring the intersect. If that sounds a bit complicated, just think of finding the four points on the lines that lie on the dotted lines in the diagram.

Step 3

Now, the points shown in diagram opposite should have been found. Checking to see if the lines cross is simply a matter of subtracting the y components of the endpoints in the order B'y-D'y and A'y-C'y and checking signs of the answers. If they are the same, the lines don't cross, but if they're different, then the lines do cross. Huzzah!

Coding the algorithm
Finding the two points closest to the the intersection is nerely a matter of a whole heap of conditionals. You could, I suppose use a proper sorting routine, but specially written if statements are much faster. Finding the new points is easy, just use y = mx + c. In case you're feeling particularly dense or lazy, here's an example:

The only bit that is left to do is to check the signs of the subtracted y components and return true or false accordingly. Sorted. Respect due. This routine will not report that lines running parallel to each other cross, even if they share the same endpoints. This doesn't matter as lines can only ever cross when once one is no longer parallel to the other.

Chrome mapping

Screen blurring

Tutorial 1

Tutorial 2

Tutorial 3