Category: Math

// 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.

// completely unoptimized line to line intersection test:
// from wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection
function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {
	var nx:Number, ny:Number, dn:Number;
	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);
}

//
// 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 snippet shows the first step toward a usable line to line intersection test. While this demo is fully functional, there is some room for optimization within the intersection() function itself…

From Equations to Code

When I go directly from an equation to code I like to try to make the code resemble the equation… test to make sure it works and then add optimizations. I do this to keep things clear for myself and also so that I have a step by step process to show my students.

The optimizations and additional features that I’ll add to this function tomorrow will make it look very different from the original equation from wikipedia. Some things that I’ll do:

1) tweak the equation to use fewer operators (it has 12 multiplications right now)
2) wrap duplicate mathmatical operations in variables
3) add the ability to test for line segments rather than infinite lines
4) move any object instantiation outside the function
etc…