16
\$\begingroup\$

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.

\$\endgroup\$
1
  • 6
    \$\begingroup\$ 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! \$\endgroup\$
    – Anko
    Mar 22, 2012 at 10:32

4 Answers 4

21
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ I did not get a result from this algorithm, sorry ! \$\endgroup\$
    – Vishnu
    Mar 23, 2012 at 11:11
  • 4
    \$\begingroup\$ @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. \$\endgroup\$ Mar 23, 2012 at 11:12
  • \$\begingroup\$ Then , let me try again, I might have mixed up some math in it. I'll let you know soon. Thanks a ton ,nyways :) \$\endgroup\$
    – Vishnu
    Mar 23, 2012 at 12:25
  • 1
    \$\begingroup\$ I got the desired result from you algorithm , thanks @DavidGouveia. \$\endgroup\$
    – Vishnu
    Mar 26, 2012 at 5:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Vishnu
    Mar 26, 2012 at 5:33
5
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm sorry but I'm not quite good with vector maths, I implemented this algorithm as such, but got no result, sorry ! \$\endgroup\$
    – Vishnu
    Mar 23, 2012 at 11:11
  • 1
    \$\begingroup\$ It should work so maybe if you can show us your code we can help you out there? \$\endgroup\$
    – Valmond
    Mar 23, 2012 at 12:29
  • 1
    \$\begingroup\$ Nice! however the link is broken \$\endgroup\$
    – clabe45
    Aug 26, 2018 at 23:40
  • \$\begingroup\$ Is there something you can add to this to get the point of intersection? \$\endgroup\$
    – SeanRamey
    Jun 19, 2019 at 0:09
1
\$\begingroup\$

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));
\$\endgroup\$
1
  • \$\begingroup\$ I think this answer could really improve if you explained what the code does. \$\endgroup\$
    – TomTsagk
    Aug 10, 2018 at 16:08
1
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ Is there a version of this that returns the point of intersection? \$\endgroup\$
    – SeanRamey
    Jun 19, 2019 at 0:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .