Just a quick note: Keith Hair has a very sweet and useful series of posts about line intersections that have saved me more than a few hours of headbanging. In particular, his line intersection function is a marvelous paste-and-go solution, and I really feel like posting a small optimisation that accelerates the constraint checks at the end, which, as Nicolas Barradeau points out, do need some attention.

Instead of posting the whole function body here, here’s a recipe. First, get the original code from Keith’s post. Then, replace the function declaration with the following:

function lineIntersectLine ( A : Point, B : Point, E : Point, F : Point, ABasSeg : Boolean = true, EFasSeg : Boolean = true ) : Point

Finally, instead of the *if (as_seg)* block, paste this:

// Deal with rounding errors. if ( A.x == B.x ) ip.x = A.x; else if ( E.x == F.x ) ip.x = E.x; if ( A.y == B.y ) ip.y = A.y; else if ( E.y == F.y ) ip.y = E.y; // Constrain to segment. if ( ABasSeg ) { if ( ( A.x < B.x ) ? ip.x < A.x || ip.x > B.x : ip.x > A.x || ip.x < B.x ) return null; if ( ( A.y < B.y ) ? ip.y < A.y || ip.y > B.y : ip.y > A.y || ip.y < B.y ) return null; } if ( EFasSeg ) { if ( ( E.x < F.x ) ? ip.x < E.x || ip.x > F.x : ip.x > E.x || ip.x < F.x ) return null; if ( ( E.y < F.y ) ? ip.y < E.y || ip.y > F.y : ip.y > E.y || ip.y < F.y ) return null; }

By having both an ABasSeg and EFasSeg parameters, you’ll be also able to easily intersect segments with lines:

Great!

You can’t know how useful it is to me! ;-)

nice function! I’ve used it in my application, and found a small bug with (almost) horizontal and vertical line segments:

where

A = (3.0999999999999996, 3.1499999999999995)

B = (5, 3.15)

E = (3.1499999999999995, 5.8500000000000005)

F = (3.1499999999999995, 3.0999999999999996)

and

ip = (3.1499999999999995, 3.149999999999999)

this line executes and returns null:

if ( ( A.y < B.y ) ? ip.y B.y : ip.y > A.y || ip.y

A.yHey Jack,

I see your point – I’ll look into it when I have some time, but sounds like bigtime rounding errors.

What sort of app runs into this kind of trouble ???? :)

Thanks for the comment

I have done some performance tests on the original, this version, and the version below. I can’t remember where I found this code, but it seems to be slightly more efficient than Keith’s one when an intersection is found. If no intersection is found, it’s more than twice as fast.

public function intersectsLine(A:Point, B:Point, E:Point, F:Point):Point

{

var bx:int = B.x – A.x;

var by:int = B.y – A.y;

var dx:int = F.x – E.x;

var dy:int = F.y – E.y;

var b_dot_d_perp:Number = bx * dy – by * dx;

if(b_dot_d_perp == 0) {

return null;

}

var cx:int = E.x – A.x;

var cy:int = E.y – A.y;

var t:Number = (cx * dy – cy * dx) / b_dot_d_perp;

if(t 1) {

return null;

}

var u:Number = (cx * by – cy * bx) / b_dot_d_perp;

if(u 1) {

return null;

}

return new Point(A.x+t*bx, A.y+t*by);

}