Thread: Line-Line distance

  1. #1
    Registered User
    Join Date
    Oct 2007
    Location
    Norway
    Posts
    16

    Line-Line distance

    Hi,

    I've been trying to make a function that finds the distance between two lines (stored as a start point and an end point) in a 2-dimensional space, but I can't seem to be able to find a way of doing it. I managed to figure out a method of getting the distance between a point and a line but when I turn that point into a line I just can't figure it out.

    I tried searching both on google and here but the closest thing I could find was the distance between two skew lines in 3d space.

    I'll include the code I ended up with for my point-line function (mostly to "prove" that I actually tried before running in here asking for help), it's probably not the best way of doing it but at least it works. I tried modifying this function to get it to support 2 lines instead and also tried starting over, to no avail.

    I don't necessarily need the solution, just a nudge in the right direction.

    Code:
    float linePointDistance( Vector3d l1, Vector3d l2, Vector3d p )
    {
        // Get the distances between the start and end point on the line
        float dx = l2.x - l1.x;
        float dy = l2.y - l1.y;
        // Get t, which represents how far along the line we have to move to
        // get to the closest point. l1 + t[dx,dy] = closest.
        // (found this by setting the derivative of the distance equal to 0)
        float t = -((l1.x-p.x)*dx + (l1.y-p.y)*dy)
                / (dx*dx + dy*dy);
        
        // If t isn't >= 0 and <= 1 then the closest point is outside of the
        // line, we therefore use the end or start point instead.
        Vector3d usevector;
        if( t > 1 ) usevector = l2;
        else if( t < 0 ) usevector = l1;
        else usevector = l1+((l2-l1)*t);
        
        return (usevector-p).magnitude();
    }

  2. #2
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    First, you might want to try the games forum here.

    Second, do you really mean the "shortest distance between two line segments"?

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    The distance formula is

    sqrt( (x2-x1)**2 + (y2-y1)**2 )

    Todd

    (edit - oops - you want line-line distance, not point to point distance).
    Last edited by Dino; 04-24-2008 at 12:17 PM.
    Mainframe assembler programmer by trade. C coder when I can.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Thread title says line-line distance, but the function seems to indicate point-line distance... which one is it?
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    In general, there is no such thing as line-line distance, since lines nearly always intersect. IOW, it's only meaningful for parallel lines.

    If we're talking line segments, then:
    (1) if the segments meet somewhere, then the distance is zero;
    (2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.

  6. #6
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by tabstop View Post
    In general, there is no such thing as line-line distance, since lines nearly always intersect. IOW, it's only meaningful for parallel lines.

    If we're talking line segments, then:
    (1) if the segments meet somewhere, then the distance is zero;
    (2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.
    The other case in 2D-land is where the segments form a "T" that do not touch. Then, the endpoint of the top of the vertical (for conversation purposes) to either endpoint of the horizontal is not the shortest distance between the two lines.

    In 3D-land, if they don't intersect, the shortest distance is the line that is forms a perpendicular between the two lines.
    Mainframe assembler programmer by trade. C coder when I can.

  7. #7
    Registered User
    Join Date
    Oct 2007
    Location
    Norway
    Posts
    16
    Quote Originally Posted by tabstop View Post
    If we're talking line segments, then:
    (1) if the segments meet somewhere, then the distance is zero;
    (2) if the segments don't meet, then look at the distance from endpoint of A to line B (using above) and other endpoint of A to line B. Whichever is smaller, there you go.
    That's indeed what I meant. And that's quite helpful, thanks!

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Waterbottle View Post
    That's indeed what I meant. And that's quite helpful, thanks!
    Just remember to take into account the bit that I forgot that Todd mentioned: you should check endpoints on both lines, not just one.

  9. #9
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    Quote Originally Posted by tabstop View Post
    Just remember to take into account the bit that I forgot that Todd mentioned: you should check endpoints on both lines, not just one.
    That's still not giong to find the closest points. As Todd said, what if you have this scenario:

    Code:
    ------------------------------------------------------------
                                |
                                |
                                |
                                |
                                |
                                |

  10. #10
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    the distance between two lines is not constant.

    assuming they are straight lines, the distance between them will be a linear function, so you're going to need to express the result as a slope and an intercept.
    Last edited by m37h0d; 04-24-2008 at 03:00 PM.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by medievalelks View Post
    That's still not giong to find the closest points. As Todd said, what if you have this scenario:

    Code:
    ------------------------------------------------------------
                                |
                                |
                                |
                                |
                                |
                                |
    Then the shortest distance will be found at the top endpoint of the vertical bit. There is no situation, short of intersection, where the shortest distance in 2-D is in the middle of both lines.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to do encryption in C
    By sankarv in forum C Programming
    Replies: 33
    Last Post: 12-28-2010, 11:01 AM
  2. adding line numbers and concatenating a filename
    By durrty in forum C Programming
    Replies: 25
    Last Post: 06-28-2008, 03:36 AM
  3. Finding carriage returns (\c) in a line
    By JizJizJiz in forum C++ Programming
    Replies: 37
    Last Post: 07-19-2006, 05:44 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM