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;
}
Line Segment Intersection
Author
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.)
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!)
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:
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)if ((a.x - b.x) > blah * (a.y-b.y))
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.)
(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.)
Author
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)
Obviously if you need to get the actual intersection point simply return "intersect".
Hopfully that helps someone out there!
(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!
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.
Sorry, my previous post was from work. Now that I'm at home, I think this is what you're looking for:Not a divide in sight, unless you also actually want the point of intersection too (in comments for ya).
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;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
