Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
5  
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
1  
So much math in physics... –  Byte56 Mar 22 '12 at 15:03
    
So much math in math... :P –  kaoD Mar 23 '12 at 16:56
    
:) @Byte56 but when you love something well, you forget the technicalities, don't you ! –  Vishnu Mar 26 '12 at 5:35
    
@Byte56 but when you love something well, you forget the technicalities, don't you ! –  Vishnu Mar 26 '12 at 5:35

2 Answers 2

up vote 9 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

share|improve this answer
    
I did not get a result from this algorithm, sorry ! –  Vishnu Mar 23 '12 at 11:11
1  
@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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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