# Line Segment Intersection

## Recommended Posts

Toji    535
Foo. I thought I had this one figured out but I guess I was wrong. Worked in my test cases but not on "real" data. I have a member function of my "lineSegment" structure that tests it against another line segment to see if they are intersecting. (Copied straight from my code.)
int bhxSegment::Intersects( bhxSegment *seg )
{
float m1 = (b.y - a.y) / (b.x - a.x);
float m2 = (seg->b.y - seg->a.y) / (seg->b.x - seg->a.x);

float b1 = a.y - (m1 * a.x);
float b2 = seg->a.y - (m2 * seg->a.x);

float ix = (b2 - b1) / (m1 - m2);
float iy = (m1 * ix) + b1;

bhxVec2 inter = bhxVec2( ix, iy );

if( InBB( inter ) && seg->InBB( inter ) )
{
return 1;
}

return 0;
}


InBB simply checks to see if the point is within the bounding box formed by the segment itself. Now, this looks nice and all but it doesn't work! >_< It's especially prone to failure when dealing with vertical or near vertical lines. (and I can see why, now.) Does anyone have anything better? (And I remembered this being so easy in geometry!)

##### Share on other sites
iMalc    2466
Get rid of those divides. However you do it.
I can't see a really way to refactor your code to do it, but if your code looked like this:
if ((a.x - b.x)/(a.y-b.y) > blah)
then you would rearrange it to look more like this:
if ((a.x - b.x) > blah * (a.y-b.y))
There's more to it than that, but that's what you need to do to prevent problems with near vertical or horizontal lines.

##### Share on other sites
jyk    2094
iMalc is right, you don't want to use slope-intercept form to represent linear components in 2d. Use normal-distance or parametric form instead; in either case you end up with two equations in two unknowns, which has a solution if the linear components are non-degenerate and not parallel.

(There are other ways the test can be formulated as well, which can allow for earlier outs and deferring of the division until absolutely necessary.)

##### Share on other sites
Toji    535
Okay, so I eventually dug up a method that works 100% of the time, and I figured I'd post it here in case anyone cares to take a look:

(Tried to make this a little cleaner than my previous code chunk)
//A cSegment contains two cVector2 variables, a & b.//My use of the equation required "double" precision. //Could feasibly be done with floats. bool cSegment::Intersects( cSegment *seg ){	//Store our Intersection point	cVector2 intersect( 0, 0 );	        //This Line	double a1 = (b.y - a.y);	double b1 = (a.x - b.x);	double c1 = (b.x*a.y - a.x*b.y);		//Line to test against	double a2 = (seg->b.y - seg->a.y);	double b2 = (seg->a.x - seg->b.x);	double c2 = (seg->b.x*seg->a.y - seg->a.x*seg->b.y);	double denom = a1*b2 - a2*b1;		//Check for parallel lines	if(denom == 0) { return false; }		//Get the intersection point	intersect.x = (b1*c2 - b2*c1)/denom;	intersect.y = (a2*c1 - a1*c2)/denom;	//InBoundingBox tests to see if the point is in the bounding box for        //a line segment. The point must be in both lines' bounding boxes to        //register and intersection.        if( InBoundingBox( intersect ) && seg->InBoundingBox( intersect ) )	{		return true;	}		return false;}

Obviously if you need to get the actual intersection point simply return "intersect".

Hopfully that helps someone out there!

##### Share on other sites
snk_kid    1312
Quote:
 Original post by Toji(Tried to make this a little cleaner than my previous code chunk)

Let me give you a helping hand:

bool cSegment::Intersects(const cSegment& seg_ref) const { /* ... */ }

Intersection routines don't generally modify states of the objects in question, and prefer using reference types for pass-by reference.

##### Share on other sites
iMalc    2466
Sorry, my previous post was from work. Now that I'm at home, I think this is what you're looking for:
bool bhxSegment::Intersects( const cSegment &seg ) const{	cVector2 u = b - a;	cVector2 v = seg.b - seg.a;	float D = u.x * v.y - u.y * v.x;	if (fabs(D) < EPSILON) return false; //parallel test	cVector2 w = a - seg.a;	float s = v.x * w.y - v.y * w.x;	if (s < 0 || s > D) return false;	float t = u.x * w.y - u.y * w.x;	if (t < 0 || t > D) return false;		//cVector2 intersectPt = a + u * (s/d); //or b + v * (t/d);	return true;}
Not a divide in sight, unless you also actually want the point of intersection too (in comments for ya).