Line segment intersection

1

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

source:
http://flassari.is/2009/04/line-line-intersection-in-as3/

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

2

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(testInters);
[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!

3

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

1 Like
4

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
5

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: https://www.kirupa.com/forum/showthread.php?372104-CDK-Collision-help&p=2638313#post2638313

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
6

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

7

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] http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
[trace] result = null
[trace] vs
[trace] https://www.kirupa.com/forum/showthread.php?361144-line-segment-intersection&p=2599918#post2599918
[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] http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
[trace] result = null
[trace] vs
[trace] https://www.kirupa.com/forum/showthread.php?361144-line-segment-intersection&p=2599918#post2599918
[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(p1);
			trace(p2);
			trace(p3);
			trace(p4);
			
			trace("http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/");
			trace("result = " + segmentsIntersectionKeith(p1, p2, p3, p4));
			trace("vs");
			
			trace("https://www.kirupa.com/forum/showthread.php?361144-line-segment-intersection&p=2599918#post2599918");
			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(as_seg){
				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;
		}[/details]