FacebookTwitterGoogle+Share

Line segment intersection

Sometimes you just need to know if two line segments intersect, right? right? right guys?

(Drag things about as you will)

I legit and fully stole this code from http://www.java-gaming.org/index.php?topic=22590.0 (comments and all), and then converted it to Haxe.


function doLinesIntersect(a1:Point, a2:Point, b1:Point, b2:Point):Bool {
	// Return false if either of the lines have zero length
	if (a1.x == a2.x && a1.y == a2.y ||
		b1.x == b2.x && b1.y == b2.y){
		return false;
	}
	// Fastest method, based on Franklin Antonio's "Faster Line Segment Intersection" topic "in Graphics Gems III" book (http://www.graphicsgems.org/)
	var ax = a2.x-a1.x;
	var ay = a2.y-a1.y;
	var bx = b1.x-b2.x;
	var by = b1.y-b2.y;
	var cx = a1.x-b1.x;
	var cy = a1.y-b1.y;

	var alphaNumerator = by*cx - bx*cy;
	var commonDenominator = ay*bx - ax*by;
	if (commonDenominator > 0){
		if (alphaNumerator < 0 || alphaNumerator > commonDenominator)
			return false;
	} else if (commonDenominator < 0){
		if (alphaNumerator > 0 || alphaNumerator < commonDenominator)
			return false;
	}
	var betaNumerator = ax*cy - ay*cx;
	if (commonDenominator > 0){
		if (betaNumerator < 0 || betaNumerator > commonDenominator)
			return false;
	}else if (commonDenominator < 0){
		if (betaNumerator > 0 || betaNumerator < commonDenominator)
			return false;
	}
	if (commonDenominator == 0){
		// This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.
		// The lines are parallel.
		// Check if they're collinear.
		var y3LessY1 = b1.y-a1.y;
		var collinearityTestForP3 = a1.x*(a2.y-b1.y) + a2.x*(y3LessY1) + b1.x*(a1.y-a2.y);   // see http://mathworld.wolfram.com/Collinear.html
		// If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4
		if (collinearityTestForP3 == 0){
			// The lines are collinear. Now check if they overlap.
			if (a1.x >= b1.x && a1.x <= b2.x || a1.x <= b1.x && a1.x >= b2.x ||
				a2.x >= b1.x && a2.x <= b2.x || a2.x <= b1.x && a2.x >= b2.x ||
				b1.x >= a1.x && b1.x <= a2.x || b1.x <= a1.x && b1.x >= a2.x){
				if (a1.y >= b1.y && a1.y <= b2.y || a1.y <= b1.y && a1.y >= b2.y ||
					a2.y >= b1.y && a2.y <= b2.y || a2.y <= b1.y && a2.y >= b2.y ||
					b1.y >= a1.y && b1.y <= a2.y || b1.y <= a1.y && b1.y >= a2.y){
					return true;
				}
			}
		}
		return false;
	}
	return true;
}

And just to reiterate, this is not my code. I didn’t write it, just altered it slightly to compile in Haxe.
 

Comments