Please help. 3D Intersection

**jacksoncapper** · January 18th 2008, 04:21 AM

I have been trying so long to do this simple thing. I have two 3D line segments, each represented by two points. I need to know if and where these two lines intersect, but I need a method that I can implement programmatically in an algorithm. Please any help would be greatly appreciated.

**CaptainBlack** · January 18th 2008, 05:56 AM

Originally Posted by jacksoncapper

I have been trying so long to do this simple thing. I have two 3D line segments, each represented by two points. I need to know if and where these two lines intersect, but I need a method that I can implement programmatically in an algorithm. Please any help would be greatly appreciated.

Let the points be $\bf{x}$ and $\bf{y}$ and $\bf{u}$ and $\bf{v}$ . Then the line segments are:

$\bold{l_1}=\bold{x}+ \lambda (\bold{y}-\bold{x}),\ \lambda \in [0,1]$
$\bold{l_2}=\bold{u}+ \mu (\bold{v}-\bold{u}),\ \mu \in [0,1]$

The lines intersect if there are $\lambda,\ \mu \in [0,1]$ such that:

$\bold{x}+ \lambda (\bold{y}-\bold{x})=\bold{u}+ \mu (\bold{v}-\bold{u})$

Now write these out in terms of the components and you have three
simultaneous linear equations for $\lambda$ and $\mu$ . If there is a solution
with $\lambda$ and $\mu \in [0,1]$ then the line segments intersect.

RonL

**jacksoncapper** · January 18th 2008, 02:58 PM

Thankyou so much for your explaination. This [0,1] part, does that mean the value has to be between 0 and 1? Can these 3 component equations be used in a gaussian matrix to work it out programatically? Thankyou again, this is great.

**CaptainBlack** · January 18th 2008, 09:38 PM

Originally Posted by jacksoncapper

Thankyou so much for your explaination. This [0,1] part, does that mean the value has to be between 0 and 1?

Yes, if they are outside this range the lines intersect but not in the segments
but outside one or both.

Can these 3 component equations be used in a gaussian matrix to work it out programatically? Thankyou again, this is great.

Yes, but some work may be needed as there are three equations and two
unknowns. Any two of them should give a solution, and this shoud be
consistent with the solution when the left out equation is substituted for
one of the equations used.

RonL

**jacksoncapper** · January 19th 2008, 01:42 AM

Thankyou again for taking your time to reply to my question.

I am having real difficulties in implementing this. Please if you could spend a moment on this simple problem and tell me where I'm going wrong? Say I have these two simple line segments:

Line segment 1 defined by points a( -6, 0, 0 ), and b( 4, 0, 0 ) and
Line segment 2 defined by points c( -1, -5, 0 ), and d( -1, 5, 0 ) with the origin o( 0, 0, 0 ).

The line segments would look something like this (slightly offset from the origin):

c
|
|
a------o---b
|
|
d

The point of intersection should be ( -1, 0, 0 ).

So from here I build an equation for each of the dimensions. What would these equations look like? I am doing something wrong.

Once I have the equations and they are re-arranged I should be able to use just two of the equations in a gaussian elimination to find the point of intersection? Or am I just finding the point along the lines where they do intersect (the number between 0 and 1) and I have to work from that (a whole other problem)? What would a gaussian elimination give me in this situation, the point or the [0,1] values?

Please if you could just explain where I am going wrong with my interpretation and what these equations might look like given the example.

Your help and time is appreciated much, thankyou so much.

**jacksoncapper** · January 19th 2008, 01:44 AM

Sorry that diagram didn't come out correctly because of the spaces I was using to align the pipe characters. Ugh, I hope you know what I meant. Thankyou again.

**CaptainBlack** · January 19th 2008, 06:19 AM

Note correction to my earlier post

RonL

**CaptainBlack** · January 19th 2008, 07:11 AM

Originally Posted by jacksoncapper

Thankyou again for taking your time to reply to my question.

I am having real difficulties in implementing this. Please if you could spend a moment on this simple problem and tell me where I'm going wrong? Say I have these two simple line segments:

Line segment 1 defined by points a( -6, 0, 0 ), and b( 4, 0, 0 ) and
Line segment 2 defined by points c( -1, -5, 0 ), and d( -1, 5, 0 ) with the origin o( 0, 0, 0 ).

Here the equations are:

$-6+\lambda(4+6)=-1+\mu(-1+1)$

$0+\lambda (0) = -5 +\mu(5+5)$

$0+\lambda (0)=0+\mu (0)$

The last of these tell us nothing, the second tells us $\mu=1/2$ , and the first tells us that $\lambda=1/2$ .

And the point of intersection is: $(-1,0,0)$

RonL

**jacksoncapper** · January 21st 2008, 02:54 AM

Ok! I have made some progress. From the above example, the gaussian matrix is returning 0.5, 0.5 meaning the two line segments intersect both at half way, which is correct as you pointed out. So now I'm not sure what to do with these two values, and how to incorporate the z axis into this whole thing... (sigh) this is so difficult... How do I convert 0.5 and 0.5 into (-1, 0, 0)?

**CaptainBlack** · January 21st 2008, 03:32 AM

Originally Posted by jacksoncapper

Ok! I have made some progress. From the above example, the gaussian matrix is returning 0.5, 0.5 meaning the two line segments intersect both at half way, which is correct as you pointed out. So now I'm not sure what to do with these two values, and how to incorporate the z axis into this whole thing... (sigh) this is so difficult... How do I convert 0.5 and 0.5 into (-1, 0, 0)?

Choose one of the lines (lets say ${\bold l_1}$ ) and plug the appropriate parameter into
it (in the case of ${\bold l_1}$ that is $\lambda$ ), and it will give you the point of intersection.

$(-6+\lambda(4+6), 0+\lambda (0), 0+\lambda (0))=(-6+0.5 \times 10, 0,0)=(-1,0,0)$

RonL

**jacksoncapper** · January 22nd 2008, 12:10 AM

Okay thanks to your advice I've worked out the x and y co-ordinates of where two 3D line segments would intersect (if they did). There only one more thing to figure out, and that is how to incorporate the z co-ordinate. Only the x and y co-ordinates could be used in the gaussian matrix (as far as I know). Please any guidance?

**CaptainBlack** · January 22nd 2008, 09:59 AM

Originally Posted by jacksoncapper

Okay thanks to your advice I've worked out the x and y co-ordinates of where two 3D line segments would intersect (if they did). There only one more thing to figure out, and that is how to incorporate the z co-ordinate. Only the x and y co-ordinates could be used in the gaussian matrix (as far as I know). Please any guidance?

There is no need the values of $\lambda$ or $\mu$ tell you all you need about the point.

RonL

**jacksoncapper** · January 22nd 2008, 02:09 PM

It's just the z co-ordinate was not in any way included in the gaussian matrix, therefore I can't see any way that the z co-ordinates played a part in determining whether the 3D lines intersect. I can extract the z value at the end just fine, but the [0,1] lambda value (and the other one) was only determined from the x and y co-ordinates. Do you know what I mean? Sorry if I am not explaining this well. I trust you know better than I do, please correct me if I'm wrong.

**CaptainBlack** · January 22nd 2008, 08:24 PM

Originally Posted by jacksoncapper

It's just the z co-ordinate was not in any way included in the gaussian matrix, therefore I can't see any way that the z co-ordinates played a part in determining whether the 3D lines intersect. I can extract the z value at the end just fine, but the [0,1] lambda value (and the other one) was only determined from the x and y co-ordinates. Do you know what I mean? Sorry if I am not explaining this well. I trust you know better than I do, please correct me if I'm wrong.

The point of intersection of two lines is a problem with two free parameters
that have to be determined. Thus we only need two equations to find these
parameters (usually). But we have three equations, and there are three
posibilities for what that third equation does for us:

1. It can be inconsitent with the first two
2. It can be consistent and give the same result when used in place of one of the other equations
3. It can add no information about the parameters at all (which is the case here)

Hence you only need two of the three equations (as long as they are independent) to find the parameters, then the third needs to check to see that it is not inconsistent with the values found.

RonL

**jacksoncapper** · January 22nd 2008, 08:50 PM

Okay I kind of understand that, however in the example I gave, z was set to 0 in both points in both line segments because I wanted to make it as simple as possible. When I implement this solution the values for the lines could be anything.

So what you are suggesting is that I perform the gaussian matrix elimination twice, once with say x and y, and the second time with say y and z.

If both turn out to be consistent with each other, the point of intersection has been found. If they turn out to be inconsistent, there is NO point of intersection.

Is this correct?

Thankyou once again for your time.

Thread: Please help. 3D Intersection

LinkBack

Thread Tools

Display

Please help. 3D Intersection

Similar Math Help Forum Discussions

Self intersection

The intersection of x and ln(x)^p, where p>1

Inverse function of intersection = intersection of inverse functions

Another intersection:

intersection

Search Tags