Line Intersection

(Bora Kasap) #1

I should check intersection between a single line and another lines when mouse released.

So, as example i have four different line entity in the world each has variables below.

MasterLine(x1,y1,x2,y2);
Line(x1,y1,x2,y2);
Line(x1,y1,x2,y2);
Line(x1,y1,x2,y2);

When i release the mouse, i wanna check if any of them intersecting with MasterLine then remove intersecting lines.

How can i do that, i need some mathhhh… :!

NOTE: x1 and y1 variables for each “Line”(not master line) entity have same value everymoment. So, that may help to find an easier code for whole process.

(Bora Kasap) #2

I think i found an idea depending on x1 and y1 values are same.

All Lines have a central point so i can use angles to check for intersection.

var start_angle:Number = FP.angle(LinesAll.x1, LinesAll.y1, MasterLine.x1, MasterLine.y1);
var end_angle:Number = FP.angle(LinesAll.x1, LinesAll.y1, MasterLine.x2, MasterLine.y2);

for each (var line:Line in Lines)
{
   var line_angle:Number = FP.angle(line.x1, line.y1, line.x2, line.y2);
   if(line_angle > start_angle && line_angle < end_angle) {
      FP.remove(line, Lines);
      world.remove(line);
}

i think thats gonna work… let’s try…

(Bora Kasap) #3

That doesn’t work because lines have different lengths. Also, i give up using this in my game because of someother gameplay. After all, i still curious about how to do this.

(azrafe7) #4

Hey @AlobarNon, try this: http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/

(JP Mortiboys) #5

I’m sure it doesn’t really matter in this day and age, but the blatant lack of optimisation in the second part of the function just looks wrong to me. Not as in incorrect, but needlessly complicated and certainly not exposing why it works the way it does.

The best way to solve segment intersection is to express both segments as parametric equations. this shows a nice way and explanation, although it isn’t in AS3 (shouldn’t be hard to translate though).

Also note that neither of these methods handle the degenerate case of parallel segments which overlap (example: [(0,0)-(2,0)] and [(1,0)-(3,0)] - which is technically an intersection, although the result could be another segment as well as a point.

If you’re checking a small number of segments then checking them one-by-one is fine, but if you’re checking a LOT of segments - or checking lots of segments against every other one, there are ways to reduce the number of checks you need to do (because lots of checks can be slow - if you were checking all possible intersections between 1000 segments then the naive method would give you 500000 (half a million!) checks to run).

(Bora Kasap) #6

i was gonna check maximum 20 lines against 1 line. and that’s not a continuous check, it is 1 frame check. so, performance is not so important in this case. also, i don’t understand what you mean because of my lack of english. i’l take time for your reply soon. thanks you both <3

(rostok) #7 
    // check if two segments intersect
    public static function ptsits2d(p1x:Number, p1y:Number, p2x:Number, p2y:Number, p3x:Number, p3y:Number, p4x:Number, p4y:Number):Boolean
    {
        var w21x:Number = p2x - p1x;  var w21y:Number = p2y - p1y;
        var w31x:Number = p3x - p1x;  var w31y:Number = p3y - p1y;
        var w41x:Number = p4x - p1x;  var w41y:Number = p4y - p1y;
        var w43x:Number = p4x - p3x;  var w43y:Number = p4y - p3y;
        var w23x:Number = p2x - p3x;  var w23y:Number = p2y - p3y;
        if (((w21x*w31y-w21y*w31x)*(w21x*w41y-w21y*w41x)) > 0) return false;
        if (((w43x*w23y-w43y*w23x)*(w31x*w43y-w31y*w43x)) > 0) return false;
        return true;
    }

Here’s a simple function to find if two segments intersect. I would avoid code provided by Azrafe7 as it has 16 Math.pow() calls that will surely slow things down.

@AlobarNon check out my game code from this topic "Krupki" - ultra simple game.