Line segment intersection

Hello, I was hoping someone can help me build upon this great line intersect function.


function intersection(p1:Point, p2:Point, p3:Point, p4:Point):Point
    var x1:Number = p1.x,x2:Number = p2.x,x3:Number = p3.x,x4:Number = p4.x;
    var y1:Number = p1.y,y2:Number = p2.y,y3:Number = p3.y,y4:Number = p4.y;
    var z1:Number= (x1 -x2), z2:Number = (x3 - x4), z3:Number = (y1 - y2), z4:Number = (y3 - y4);
    var d:Number = z1 * z4 - z3 * z2;

    // If d is zero, there is no intersection
    if (d == 0)
        return null;

    // Get the x and y
    var pre:Number = (x1*y2 - y1*x2), post:Number = (x3*y4 - y3*x4);
    var x:Number = ( pre * z2 - z1 * post ) / d;
    var y:Number = ( pre * z4 - z3 * post ) / d;

    // Check if the x and y coordinates are within both lines
    if ( x < Math.min(x1, x2) || x > Math.max(x1, x2) ||
            x < Math.min(x3, x4) || x > Math.max(x3, x4) )
        return null;
    if ( y < Math.min(y1, y2) || y > Math.max(y1, y2) ||
            y < Math.min(y3, y4) || y > Math.max(y3, y4) )
        return null;

    // Return the point of intersection
    return new Point(x, y);

If a segment is exactly 90 degrees it will not find the intersection, but return null (as if there were no intersection).

I’m glad to see you’ve found the answer here:

But I think your code does not work with negative coordinates:

var testInters:Point = linesIntersection(new Point(-50, 100), new Point(111, 100), new Point(0, 0), new Point(0, 999));
[trace] (x=-7.105427357601002e-15, y=100)

ps. can someone tell my how to format text in reply to make it look like code? Cant see any tag or button on replay panel!

You can highlight the code and click the </> button in the editing toolbar :slight_smile:

1 Like

Ah yes i remember that day fondly. thecanadian blew my mind with math i still use to this day, and it was the one time i recall rumblesushi complementing thecanadian without attacking him due to some unknown one sided rivalry i may or may not have imagined.

The function does work in all scenerios
Edit: actually i would have to check, i think i have always used that function with a positive x, as my games scroll right

1 Like

Haha! I don’t remember that thread or function or what the math does or what {tE[0,1]}∩{sE(-∞,0)∪(1,∞)} means (if anything) or why I used the dastardly Point class or any rivalry with rumblesushi (whoever that is).

This thread reminded of another post:

I seem to recall I really enjoyed finding the shortest distance between a line and ellipse, though, in retrospect, I’m certain I didn’t help the OP at all :run_in_fear:

1 Like

The function does seem to work. -7.105427357601002e-15 is the result of floating point arithmetic and essentially equals 0.

ok, maybe I do something wrong…

[trace] Segments intersection test
[trace] (x=465.16666666666663, y=222)
[trace] (x=611, y=66.6)
[trace] (x=250, y=222)
[trace] (x=472, y=222)
[trace] result = null
[trace] vs
[trace] result = (x=465.16666666666663, y=222)
[trace] test end
[trace] Segments intersection test
[trace] (x=222, y=481.81570788839144)
[trace] (x=361, y=333)
[trace] (x=222, y=444)
[trace] (x=222, y=666)
[trace] result = null
[trace] vs
[trace] result = (x=222, y=481.81570788839144)
[trace] test end

here is the full test case:

[details=Summary] public static function startTest():void
segmentsIntersectionTest(new Point(465.16666666666663, 222), new Point(611, 66.6), new Point(250, 222), new Point(472, 222));
segmentsIntersectionTest(new Point(222, 481.81570788839144), new Point(361, 333), new Point(222, 444), new Point(222, 666));

		public static function segmentsIntersectionTest(p1:Point, p2:Point, p3:Point, p4:Point):void
			trace("Segments intersection test");
			trace("result = " + segmentsIntersectionKeith(p1, p2, p3, p4));
			trace("result = " + segmentsIntersectionNew(p1, p2, p3, p4));
			trace("test end");
		public static function segmentsIntersectionKeith(p1:Point, p2:Point, p3:Point, p4:Point):Point
			var result:Point;
			var a1:Number;
			var a2:Number;
			var b1:Number;
			var b2:Number;
			var c1:Number;
			var c2:Number;
			a1 = p2.y-p1.y;
			b1 = p1.x-p2.x;
			c1 = p2.x*p1.y - p1.x*p2.y;
			a2 = p4.y-p3.y;
			b2 = p3.x-p4.x;
			c2 = p4.x*p3.y - p3.x*p4.y;
			var denom:Number = a1*b2 - a2*b1;
			if(denom == 0)
				return null;
			result = new Point();
			result.x = (b1*c2 - b2*c1) / denom;
			result.y = (a2*c1 - a1*c2) / denom;
			//Do checks to see if intersection to endpoints
			//distance is longer than actual Segments.
			//Return null if it is with any.
				if(Point.distance(result, p2) > Point.distance(p1, p2))
					return null;
				if(Point.distance(result, p1) > Point.distance(p1, p2))
					return null;
				if(Point.distance(result, p4) > Point.distance(p3, p4))
					return null;
				if(Point.distance(result, p3) > Point.distance(p3, p4))
					return null;
			return result;
		public static function segmentsIntersectionNew(p1:Point, p2:Point, p3:Point, p4:Point):Point
			var v1:Point=new Point();
			var v2:Point=new Point();
			var intersectPoint:Point= new Point();
			var d:Number;
			v1.x = p2.x - p1.x;
			v1.y = p2.y - p1.y;
			v2.x = p4.x - p3.x;
			v2.y = p4.y - p3.y;
			d = v1.x * v2.y - v1.y * v2.x;
			if (! d)
				//points are collinear
				return null;
			var a:Number = p3.x - p1.x;
			var b:Number = p3.y - p1.y;
			var t:Number = (a * v2.y - b * v2.x) / d;
			var s:Number = (b * v1.x - a * v1.y) / -d;
			if (t < 0 || t > 1 || s < 0 || s > 1)
				//line segments don't intersect
				return null;
			intersectPoint.x = p1.x + v1.x * t;
			intersectPoint.y = p1.y + v1.y * t;
			return intersectPoint;