Sign in to follow this  

Ray, Line Segment Intersection Test

This topic is 4481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

EDIT: Changed focus, looking for ray, line segment intersection test. I'm trying to implement a quick way to tell whether two 2d line segments are intersecting each other. I found an old thread and lifted iMalc's code as follows:
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;
}


I converted it to be a non-member function and use D3DXVECTOR2:
typedef D3DXVECTOR2 Vector;
bool LineIntersect(const Vector& start1, const Vector& end1, const Vector& start2, const Vector& end2)
{
	Vector u = end1 - start1;
	Vector v = end2 - start2;
	float D = u.x * v.y - u.y * v.x;

	if (fabs(D) < 0.000000000f) return false; //parallel test

	Vector w = start1 - start2;

	float s = v.x * w.y - v.y * w.x;
	if (s < 0.0f || s > D) return false;

	float t = u.x * w.y - u.y * w.x;
	if (t < 0.0f || t > D) return false;
	
	//cVector2 intersectPt = a + u * (s/d); //or b + v * (t/d);
	return true;
}


But this problem occurs: That is, if endpoints A and B are swapped for some reason the code thinks they're not intersecting. It only works "one way". Does anyone see anything wrong the converted code? [Edited by - load_bitmap_file on September 6, 2005 8:56:27 PM]

Share this post


Link to post
Share on other sites
For 2D line intersection, I would calculate the slope of the lines (m in the equation y = mx + b). If the slopes are the same and the y-intersept is different, they don't intersect. In all other cases, they intersect.

To calculate the slope, you calculate the change in Y divided by the change in X. (Delta Y / Delta X OR Rise / Run)

EDIT: Oh! You mean line segment intersection. Sorry about that. [smile]

Share this post


Link to post
Share on other sites
I'm not sure if this is the fastest solution, but it should work:

I solved the two equations:
y=m0x+b0
y=m1x+b1

for x and y, resulting in the x and y coords where the lines intersect:

x = -(b0 - b1)/(m0 - m1)
y = -(b0*m1 - b1*m0)/(m0 - m2)

once you find where they meet assuming they extend to infinity and are not parallel, check to see if the intersection is within the bounds of one of the segments.

There might be a faster way, but that one was easy to derive with a TI-89

Share this post


Link to post
Share on other sites
Solving a slope-intercept equation was the first thing to come to mind but I googled for other possible solutions. The fellows in the thread that I linked (and got the code from) suggested not using slope-intercept form. The line intersection code seems like something iMalc pasted out of an already written library or something, but I can't see how anything changed converting the code to use D3DXVECTOR2 instead. Maybe I should PM him.

Share this post


Link to post
Share on other sites
Can't you just use the first line to calculate a 2D ray, use the other to calculate a 2D plane, then intersect?

This also works with 3D lines.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It looks like the original code is incorrect. It is an attempt to optimize some standard line segment intersection code (the algorithm is described in a computer graphics algorithms faq at http://www.faqs.org/faqs/graphics/algorithms-faq/ in section 1.03)

The problem is that the algorithm is to test that 0 <

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Grah stupid html messed up my post.

The problem is that the algorithm is to test that 0 < s/D < 1 and 0 < t/D < 1. The code posted attempts to eliminate the need to perform the division, but it loses the sign information. If D is negative the code doesn't work properly. To fix it, either perform the divisions or test if D is negative, and if so modify the tests accordingly.

This algorithm is easily modified to handle a ray by eliminating one of the comparisons. The comparisons test that the intersections occur between the end points of the segments. Eliminating one of the comparisons will effectively remove one of the end points from consideration.

Share this post


Link to post
Share on other sites
I can't really put much information into the 2D routine. I'm not very good with 2D vector math at all. I can explain how to do it in 3D though. Which is basically the same, except your line directions have z==0. I've just been working in 3D for so long, 2D gives me troubles.

You need to find the direction of each line (subtract one end from the other or such). Let's say line_a_dir, and line_b_dir. You also need to have a starting point for both lines. Call em line_a_start and line_b_start. Make sure the directions are pointing away from the starting locations. For example, calculate line_a_dir by subtracting line_a_start from line_a_end and normalizing. Keep in mind that it doesn't matter which end of the line is the start or end, just make sure you stick with the same one.

If you cross both directions (line_a_dir and line_b_dir), you get the shared plane that both lines rest on. Sort of looking in 3D space so that both lines are laying flat. Not only does this give you the plane, it also gives you a common orientation to look at the lines - which is what your current problem is. In other words, it won't matter which end is which.

Now calculate another normal for line a. I guess you could call this line_a_normal. Simply cross line_a_dir with the shared plane to get this. Might need to normalize the result. line_a_normal now represents the side of line a that faces line b.

From here you can do the parallel test. Just dot line_a_normal with line_b_dir. If the result is zero, no intersect. Keep this dot value for below.

Now, line b is your ray. Line a is the plane. line_a_normal is the plane normal. But since line b is a ray, we need to know it's length to test the final result (to optimize, grab the length when you normalize line_b_dir - the result of the square root ).

Anyway, this is the distance from line b's start to the plane of line a. Remember that 'dot' comes from above; the parallel test.
distance = line_a_normal.Dot( line_a_start - line_b_start ) / dot;

If distance is less than zero, no intersect. If distance is greater than line b's length, no intersect. Otherwise you made contact.

Share this post


Link to post
Share on other sites

This topic is 4481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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