How to detect 2D line on line collision?

Question

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

Thanks in advance.

Answer 1

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:

Answer 2

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.

Answer 3

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));

Answer 4

The accepted answer gave a wrong answer in this case:

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 10;

x3 = 10.1;
y3 = 10.1;
x4 = 15;
y4 = 15;

These lines obviously don't intersect, but according to the function in the "correct answer" the lines do intersect.

This is what I use:

function do_lines_intersect(px1,py1,px2,py2,px3,py3,px4,py4) {
  var ua = 0.0;
  var ub = 0.0;
  var ud = (py4 - py3) * (px2 - px1) - (px4 - px3) * (py2 - py1);


  if (ud != 0) {
    ua = ((px4 - px3) * (py1 - py3) - (py4 - py3) * (px1 - px3)) / ud;
    ub = ((px2 - px1) * (py1 - py3) - (py2 - py1) * (px1 - px3)) / ud;
        if (ua < 0.0 || ua > 1.0 || ub < 0.0 || ub > 1.0) ua = 0.0;
  }

  return ua;
}

returns 0 = the lines do not intersect

returns > 0 = the lines intersect

Update to answer the question:

I did not create this code myself. It is over 5 years old and I don't know what the original source is. But..

I think the return value is the relative position of the first line where they cross (to explain it badly). To calculate the point of intersection you could probably use lerp like this:

l = do_lines_intersect(...)
if (l > 0) {
    intersect_pos_x = l * (px2-px1);
    intersect_pos_y = l * (py2-py1);
} else {
    // lines do not cross
}

(I DID NOT TEST THIS)