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

no intersection no intersection intersection no intersection

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

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

Thanks in advance.

  • 6
    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
up vote 15 down vote accepted

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:

enter image description here

  • I did not get a result from this algorithm, sorry ! – Vishnu Mar 23 '12 at 11:11
  • 4
    @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
  • 1
    I got the desired result from you algorithm , thanks @DavidGouveia. – Vishnu Mar 26 '12 at 5:31
  • 1
    Well, but now I have another problem :) ! I need to make the intersected lines with red color and green. The intersection works fine. But as I've understood now, (not mathematically though) that a simple if-else won't work as for putting red and green lines for intersected and non-intersected lines. The node i am dragging has both a left and right line . So, something's gone wrong somewhere while changing the color of non-intersected lines back to green. I guess I need another condition too. Hmmm, anyways thanks a ton, I'm marking this as the correct answer. – Vishnu Mar 26 '12 at 5:33

Without Divisions! So no problem with precision nor by division by zero.

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.

  • 1
    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
  • 1
    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
  • Nice! however the link is broken – clabe45 Aug 26 at 23:40

I just want to say, I needed it for my Gamemaker Studio game and it works well:

///scr_line_collision(x1,y1,x2,y2,x3,y3,x4,y4)

var denominator= ((argument2 - argument0) * (argument7 - argument5)) - ((argument3 - argument1) * (argument6 - argument4));
var numerator1 = ((argument1 - argument5) * (argument6 - argument4)) - ((argument0 - argument4) * (argument7 - argument5));
var numerator2 = ((argument1 - argument5) * (argument2 - argument0)) - ((argument0 - argument4) * (argument3 - argument1));

// Detect coincident lines
if (denominator == 0) {return (numerator1 == 0 && numerator2 == 0)}

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

return ((r >= 0 && r <= 1) && (s >= 0 && s <= 1));
  • I think this answer could really improve if you explained what the code does. – TomTsagk Aug 10 at 16:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.