Sign in to follow this  
Toji

Line Segment Intersection

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this