-
// optimized line to line intersection test:
-
// from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
-
// and http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
-
var ip:Point = new Point();
-
-
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
-
var nx:Number, ny:Number, dn:Number;
-
var x4_x3:Number = p4.x - p3.x;
-
var y4_y3:Number = p4.y - p3.y;
-
var x2_x1:Number = p2.x - p1.x;
-
var y2_y1:Number = p2.y - p1.y;
-
var x1_x3:Number = p1.x - p3.x;
-
var y1_y3:Number = p1.y - p3.y;
-
-
nx = x4_x3 * y1_y3 - y4_y3 * x1_x3;
-
ny = x2_x1 * y1_y3 - y2_y1 * x1_x3;
-
dn = y4_y3 * x2_x1 - x4_x3 * y2_y1;
-
-
nx /= dn;
-
ny /= dn;
-
-
// has intersection
-
if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
-
ny = p1.y + nx * y2_y1;
-
nx = p1.x + nx * x2_x1;
-
ip.x = nx;
-
ip.y = ny;
-
}else{
-
// no intersection
-
ip.x = ip.y = -1000;
-
}
-
return ip
-
}
-
-
-
//
-
// test out the function:
-
//
-
-
stage.frameRate = 30;
-
var a:Sprite = dot();
-
a.x = a.y = 100;
-
-
var b:Sprite = dot();
-
b.x = b.y = 200;
-
-
var c:Sprite = dot();
-
c.x = 200
-
c.y = 100;
-
-
var d:Sprite = dot();
-
d.x = 100
-
d.y = 200;
-
-
var inter:Sprite = dot(0xFF0000,true);
-
-
addEventListener(Event.ENTER_FRAME, onLoop);
-
function onLoop(evt:Event):void {
-
var p:Point = intersection(a, b, c, d);
-
inter.x = p.x;
-
inter.y = p.y
-
-
with(graphics){
-
clear();
-
lineStyle(0,0x000000);
-
moveTo(a.x, a.y);
-
lineTo(b.x, b.y);
-
moveTo(c.x, c.y);
-
lineTo(d.x,d.y);
-
}
-
}
-
-
// draggable dot
-
function dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {
-
var s:Sprite = Sprite(addChild(new Sprite));
-
with(s.graphics) beginFill(col), drawCircle(0,0,5);
-
if (!noDrag){
-
s.buttonMode = true;
-
s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
-
}
-
return s;
-
}
-
function onDrag(evt:MouseEvent):void {
-
evt.currentTarget.startDrag()
-
}
-
-
stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
-
function onUp(evt:MouseEvent):void{
-
stopDrag();
-
}
This is a significantly optimized version of yesterdays post. The function intersection() takes four sprites as its arguments. The four arguments could be considered starting points and ending points for two line segments.
The bottleneck in yesterdays post looked something like this;
nx = (p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x);
dn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
ny = (p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x);
return new Point(nx /dn, ny / dn);
nx and ny are the numerators for two fractions both with dn as their denominator.... after taking a look at this page:
http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
We can simplify things a bit before we start wrapping repetitive math operations up in variables:
-
nx = (p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x);
-
// ny = (p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x);
-
dn = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y);
-
nx /= dn;
-
// ny /= dn
-
ny = p1.y + nx * (p2.y - p1.y);
-
nx = p1.x + nx * (p2.x - p1.x);
-
return new Point(nx, ny);
It's important to note here that if we didn't intend to calculate line segments we could exclude the initial calculation of ny.
At this point we're ready to get rid of duplicate math operations by wrapping them in variables. In this case this only includes subtraction:
-
var x4_x3:Number=p4.x-p3.x;
-
var y4_y3:Number=p4.y-p3.y;
-
var x2_x1:Number=p2.x-p1.x;
-
var y2_y1:Number=p2.y-p1.y;
-
var x1_x3:Number=p1.x-p3.x;
-
var y1_y3:Number=p1.y-p3.y;
-
-
nx=x4_x3*y1_y3-y4_y3*x1_x3;
-
ny=x2_x1*y1_y3-y2_y1*x1_x3;
-
dn=y4_y3*x2_x1-x4_x3*y2_y1;
-
-
nx/=dn;
-
ny/=dn;
-
-
ny=p1.y+nx*y2_y1;
-
nx=p1.x+nx*x2_x1;
-
-
return new Point(nx, ny);
After wrapping repetitive math into variables the only optimization left to be made is related to the instantiation of a new Point(). Instantiation of objects is an expensive process, so it's better to define the point once outside of the intersection() function definition.
In the end our function looks like this:
-
var ip:Point = new Point();
-
-
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
-
var nx:Number, ny:Number, dn:Number;
-
var x4_x3:Number = p4.x - p3.x;
-
var pre2:Number = p4.y - p3.y;
-
var pre3:Number = p2.x - p1.x;
-
var pre4:Number = p2.y - p1.y;
-
var pre5:Number = p1.y - p3.y;
-
var pre6:Number = p1.x - p3.x;
-
nx = x4_x3 * pre5 - pre2 * pre6;
-
ny = pre3 * pre5 - pre4 * pre6;
-
dn = pre2 * pre3 - x4_x3 * pre4;
-
nx /= dn;
-
ny /= dn;
-
// has intersection
-
if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
-
ny = p1.y + nx * pre4;
-
nx = p1.x + nx * pre3;
-
ip.x = nx;
-
ip.y = ny;
-
}else{
-
// no intersection
-
ip.x = ip.y = -1000;
-
}
-
return ip
-
}
The final version contains a conditional that checks the end values of nx and ny, if they are between 0 and 1 then we know that there is an intersection between the segments.
Note: Optimized code usually breaks some best practices... as best practices are usually geared toward code flexibility and readability... and not speed.
