2

I want to make a function to get the closest/shortest distance between any two lines (assuming they don't intersect). I know there are several posts about the shortest distance between a point and a line, but I couldn't find any for two lines.

I have consulted several math and vector learning sites and managed to crack out the algorithm below. It gives an answer, but not the correct one. For instance, when finding the shortest distance between:

l1 = [(5,6),(5,10)]
l2 = [(0,0),(10,10)]
print _line2line(l1,l2)

...it gives the answer as...

5.75223741636

As can be seen in the graph of the two lines (it shows a 10x10 frame with ticks mark every 1 unit) and theoretically speaking, the distance should be much smaller, around 1, between the points (6,5) and (5,5).

So I'm wondering if anyone can spot what I'm doing wrong in my code? (If possible I would also like to know how to get the actual points where the two lines are closest...)

enter image description here

Notes on the code below: L1 and L2 stands for line1 and line2, and x/y1 vs x/y2 being the start and endpoints of each line, respectively. The suffixes dx and dy stands for the delta or x and y, ie the vector if its origin is at 0,0.

def _line2line(line1, line2):

    """
    - line1 is a list of two xy tuples
    - line2 is a list of two xy tuples
    References consulted:
    http://mathforum.org/library/drmath/view/51980.html
    and http://mathforum.org/library/drmath/view/51926.html
    and https://answers.yahoo.com/question/index?qid=20110507163534AAgvfQF
    """

    import math
    #step1: cross prod the two lines to find common perp vector
    (L1x1,L1y1),(L1x2,L1y2) = line1
    (L2x1,L2y1),(L2x2,L2y2) = line2
    L1dx,L1dy = L1x2-L1x1,L1y2-L1y1
    L2dx,L2dy = L2x2-L2x1,L2y2-L2y1
    commonperp_dx,commonperp_dy = (L1dy - L2dy, L2dx-L1dx)

    #step2: normalized_perp = perp vector / distance of common perp
    commonperp_length = math.hypot(commonperp_dx,commonperp_dy)
    commonperp_normalized_dx = commonperp_dx/float(commonperp_length)
    commonperp_normalized_dy = commonperp_dy/float(commonperp_length)

    #step3: length of (pointonline1-pointonline2 dotprod normalized_perp).
    # Note: According to the first link above, it's sufficient to
    #    "Take any point m on line 1 and any point n on line 2."
    #    Here I chose the startpoint of both lines
    shortestvector_dx = (L1x1-L2x1)*commonperp_normalized_dx
    shortestvector_dy = (L1y1-L2y1)*commonperp_normalized_dy
    mindist = math.hypot(shortestvector_dx,shortestvector_dy)

    #return results
    result = mindist
    return result
Karim Bahgat
  • 2,781
  • 3
  • 21
  • 27
  • 4
    possible duplicate of [Shortest distance between two line segments](http://stackoverflow.com/questions/2824478/shortest-distance-between-two-line-segments) – David Heffernan Jun 09 '14 at 14:01
  • 2
    Indeed. Explaining that a bit more: The code above is for line-line distance, and what you have is two line *segments*. (Line-line distance is silly in 2D -- any two non-parallel lines have distance zero.) – Sneftel Jun 09 '14 at 14:04
  • 2
    (As for why your current function isn't returning zero, BTW, that's because you're calculating the perpendicular incorrectly, using a 2D perpendicular formula. Two non-parallel 2D lines cannot *have* a common perpendicular, other than one which leaves Flatland.) – Sneftel Jun 09 '14 at 14:06
  • @Sneftel and David Heffernan, thanks for the link, it basically solved my problem and taught me how it works :) I tried searching prior to posting but couldn't find that particular post. As for my code, I guess must have misread the math sources, I guess the main part was I forgot to distinguish betwen line-segments and infinite lines. Given that there is a better question and answer in the link you gave, do you guys think I should remove this question, or could it be useful to help others find the link you gave? I'm ok for anything... – Karim Bahgat Jun 09 '14 at 16:16

0 Answers0