# How to detect 2D line on line collision?

I'm a flash actionscript game developer who is a bit backward with mathematics, though I find physics both interesting and cool.

For reference this is a similar game to the one I'm making: Untangled flash game

I have made this untangled game almost to full completion of logic. But, when two lines intersect, I need those intersected or 'tangled' lines to show a different color; red.

It would be really kind of you people if you could suggest an algorithm for detecting line segment collisions. I'm basically a person who likes to think 'visually' than 'arithmetically' :)

Edit: I'd like to add a few diagrams to make convey the idea more clearly

P.S I'm trying to make a function as

``````private function isIntersecting(A:Point, B:Point, C:Point, D:Point):Boolean
``````

-
This is a disappointingly non-visual explanation of the problem, but it is an algorithm and it does make sense if you can bring yourself to read their maths: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d It may be heavy if your vector maths is weak. I understand -- I also prefer visual explanations. I'll try to find time later to doodle this, but if someone at all artistically inclined sees this link and has time before I do, get to it! – Anko Mar 22 '12 at 10:32

I use the following method which is pretty much just an implementation of this algorithm. It's in C# but translating it to ActionScript should be trivial.

``````bool IsIntersecting(Point a, Point b, Point c, Point d)
{
float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));
float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));
float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

// Detect coincident lines (has a problem, read below)
if (denominator == 0) return numerator1 == 0 && numerator2 == 0;

float r = numerator1 / denominator;
float s = numerator2 / denominator;

return (r >= 0 && r <= 1) && (s >= 0 && s <= 1);
}
``````

There's a subtle problem with the algorithm though, which is the case in which two lines are coincident but don't overlap. The algorithm still returns an intersectioin in that case. If you care about that case, I believe this answer on stackoverflow has a more complex version that addresses it.

Edit

I did not get a result from this algorithm, sorry !

That's strange, I've tested it and it's working for me except for that single case I described above. Using the exact same version I posted above I got these results when I took it for a test drive:

-
I did not get a result from this algorithm, sorry ! – Vishnu Mar 23 '12 at 11:11
@Vish What problem did you have? I tested this exact copy of the algorithm before posting and it worked flawlessly except for the single case described. – David Gouveia Mar 23 '12 at 11:12
Then , let me try again, I might have mixed up some math in it. I'll let you know soon. Thanks a ton ,nyways :) – Vishnu Mar 23 '12 at 12:25
@DavidGouveia I think you could check if lines are coincident/parallel with something like: `ab.Y / ab.X == cd.Y / cd.X`, where `ab` is the delta between `a` and `b` and `cd` the delta between `c` and `d`. If that condition is met, simply return false. – bummzack Mar 23 '12 at 18:00
@bummzack That's not really the problem, because checking for parallelism and coincidence is already handled by the algorithm, i.e. when the denominator is 0 both lines are parallel, and when both numerators are also 0 then the lines are coincident. The problem is determining whether two coincident lines segments are intersecting or not, at least using this algorithm which relies on checking if the results of the division falls within the [0-1] range, but 0/0 is indeterminate. The solution I linked is more complex, and handles that particular case separately with another algorithm. – David Gouveia Mar 23 '12 at 18:28

IIRC: (might have mixed up left & right but that shouldn't matter)

Line segment 1 is A to B Line segment 2 is C to D

A line is a never ending line, the line segment is a defined part of that line.

Check if the two bounding boxes intersect : if no intersection -> No Cross! (calculation done, return false)

Check if line seg 1 straddles line seg 2 and if line seg 2 straddles line seg 1 (ie. line Segment 1 is on both sides of Line defined by the line Segment 2).

This can be made by translating all points by -A (ie. you move the 2 lines so A is in origo (0,0))

Then you check if point C and D is on different sides of the line defined by 0,0 to B

``````//Cross Product (hope I got it right here)
float fC= (B.x*C.y) - (B.y*C.x); //<0 == to the left, >0 == to the right
float fD= (B.x*D.y) - (B.y*D.x);

if( (fc<0) && (fd<0)) //both to the left  -> No Cross!
if( (fc>0) && (fd>0)) //both to the right -> No Cross!
``````

If you haven't already got a "No Cross" then continue using not A,B versus C,D but C,D versus A,B (same calcs, just swap A and C, B and D), if there are no "No Cross!" then you have an intersection!

I searched for the exact calculations for the cross product and found This blog post that explains the method too.

-
I'm sorry but I'm not quite good with vector maths, I implemented this algorithm as such, but got no result, sorry ! – Vishnu Mar 23 '12 at 11:11
It should work so maybe if you can show us your code we can help you out there? – Valmond Mar 23 '12 at 12:29