Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Please help. 3D Intersection

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    10

    Please help. 3D Intersection

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Last edited by CaptainBlack; January 19th 2008 at 07:18 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Note correction to my earlier post

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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)?
    Last edited by jacksoncapper; January 21st 2008 at 04:04 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by jacksoncapper View Post
    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
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Dec 2007
    Posts
    10
    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Self intersection
    Posted in the Geometry Forum
    Replies: 3
    Last Post: August 1st 2010, 05:15 AM
  2. The intersection of x and ln(x)^p, where p>1
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 24th 2009, 09:06 AM
  3. Replies: 2
    Last Post: October 19th 2009, 03:47 AM
  4. Another intersection:
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 6th 2008, 11:26 PM
  5. intersection
    Posted in the Calculus Forum
    Replies: 4
    Last Post: February 11th 2008, 09:20 AM

Search Tags


/mathhelpforum @mathhelpforum