improve in coding saving how to check if two line segments are crossing in Python

Question

Consider the following example of crossing lines:

l1 = ((20,5),(40,20))
l2 = ((20,20),(40,5))
l3 = ((30,30),(30,5)) # vertical line 

I developed the following code to compute the x,y of the crossing point (see theoretical details)

def gradient(l):
    """Returns gradient 'm' of a line"""
    m = None
    # Ensure that the line is not vertical
    if l[0][0] != l[1][0]:
        m = (1./(l[0][0]-l[1][0]))*(l[0][1] - l[1][1])
        return m

def parallel(l1,l2):
    if gradient(l1) != gradient(l2):
        return False
    return True


def intersect(l):
    """Returns intersect (b) of a line using the equation of
    a line in slope and intercepet form (y = mx+b)"""
    return l[0][1] - (gradient(l)*l[0][0])


def line_intersection(l1,l2):
    """Returns the intersection point (x,y) of two line segments. Returns False
    for parallel lines"""
    # Not parallel
    if not parallel(l1,l2):
        if gradient(l1) is not None and gradient(l2) is not None:
            x = (1./(gradient(l1) - gradient(l2))) * (intersect(l2) - intersect(l1))
            y = (gradient(l1)*x) + intersect(l1)
        else:
            if gradient(l1) is None:
                x = l1[0][0]
                y = (gradient(l2)*x) + intersect(l2)
            elif gradient(l2) is None:
                x = l2[0][0]
                y = (gradient(l1)*x) + intersect(l1)
        return (x,y)
    else:
        return False

example session:

>>> line_intersection(l1,l2)
(30.0, 12.5)
>>> line_intersection(l2,l3)
(30, 12.5)

I wish to improve in an efficient style my code in the case of line segments which have a limited length, and they might not actually intersect.

l1 = ((4,4),(10,10)) 
l2 = ((11,5),(5,11))
l3 = ((11,5),(9,7))

line_intersection(l1,l2) #valid
(8.0, 8.0)
line_intersection(l1,l3) # they don't cross each other
(8.0, 8.0)
line_intersection(l2,l3) #line parallel
False

my inelegant solution is the follow.

def crosses(l1,l2):
    if not parallel(l1,l2):
        x = line_intersection(l1,l2)[0]
        xranges = [max(min(l1[0][0],l1[1][0]),min(l2[0][0],l2[1][0])),min(max(l1[0][0],l1[1][0]),max(l2[0][0],l2[1][0]))]
        if min(xranges) <= x <= max(xranges):
            return True
        else:
            return False
    else:
        return False


crosses(l1,l2)
True
crosses(l2,l3)
False

i am looking if it's possible to improve the style of my functions in python

Answer 1

Any code that returns the right answer is pretty awesome in my book. Well done.

Here are a few suggestions:

def parallel(l1,l2):
    if gradient(l1) != gradient(l2):
        return False
    return True

can be written as

def parallel(l1,l2):
    return gradient(l1) == gradient(l2)

Similarly,

if min(xranges) <= x <= max(xranges):
    return True
else:
    return False

can be written as

return min(xranges) <= x <= max(xranges)

---

Avoid integer indexing whenever possible, especially double-level integer indexing like l1[0][0].

Words or variable names are easier to read and understand than integer indices.

One way around integer indexing is to use "tuple-unpacking":

(x1, y1), (x2, y2) = l1

And then l1[0][0] becomes x1. This could improve the readability of your code in the gradient and crosses functions.

---

There are two cases when the lines are parallel. If the lines are not collinear, then they never intersect. But if the lines are collinear, they intersect everywhere.

It does not seem accurate to say

line_intersection(line, line)

is False when the lines are collinear. It seems even more wrong (if such a thing were possible :)) when the lines in question are the exact same line.

I suggest returning an arbitrary point of intersection if the lines are collinear, and None if the lines are parallel but non-collinear.

---

There is a bug that can arise when floats are compared for equality:

    In [81]: 1.2 - 1.0 == 0.2
    Out[81]: False

This is not a bug in Python, but rather it is a problem caused by the internal representation of floats which affects all floating point computation done in any language. It can introduce a bug into any code that tries to compare floats for equality -- such as here:

def parallel(l1,l2):
    if gradient(l1) == gradient(l2): ...

So instead of comparing the equality of floats, the best we can do is test if two floats are near each other within some level of tolerance. For example,

def near(a, b, rtol=1e-5, atol=1e-8):
    # Essentially borrowed from NumPy 
    return abs(a - b) < (atol + rtol * abs(b))

def parallel(l1,l2):
    if near(gradient(l1), gradient(l2)): ...

---

The PEP8 style guide says,

Never use the characters 'l' (lowercase letter el), 'O' (uppercase letter oh), or 'I' (uppercase letter eye) as single character variable names.

In some fonts, these characters are indistinguishable from the numerals one and zero.

So instead of l1 I suggest line1.

---

Now, as @george pointed out, there are a number of places where the code handles vertical lines as a special case (if gradient is None.) If we use the parametric form of the line, we can handle all lines the same way. The code will be simpler because the math will be simpler.

If you know two points on a line, (x1, y1) and (x2, y2), then the parametric form of the line is

l(t) = (x1, y1)*(1-t) + (x2, y2)*t

where t is a scalar. As t varies you get different points on the line. Notice some pertinent facts about the parametric form:

• When t = 1, the first term on the right-hand side drops out, so you are left with (x2, y2).

• When t = 0, the second term on the right-hand side drops out, so you are left with (x1, y1)*(1-0) = (x1, y1).

• The right-hand side of the equation depends linearly on t. There are no t**2 terms or any other non-linear dependence on t. So the parametric form describes a line.

---

Why is the parametric form of the line powerful?

• The points inside the line segment (x1, y1) to (x2, y2) correspond to t values between 0 and 1 (inclusive). All other values of t correspond to points outside the line segment.

• Notice also that vertical lines are nothing special as far as the parametric form is concerned. You do not have to worry about infinite slopes. Every line can be treated the same way.

---

How can we leverage this fact?

If we have two lines in parametric form:

l1(t) = (x1, y1)*(1-t) + (x2, y2)*t

l2(s) = (u1, v1)*(1-s) + (u2, v2)*s

(think of x1, y1, x2, y2, u1, v1, u2, v2 as given constants), then the lines intersect when

l1(t) = l2(s)

Now, l1(t) is a two-dimensional point. l1(t) = l2(s) is a two-dimensional equation. There is an equation for the x-coordinate and an equation for the y-coordinate built into l1(t) = l2(s). So we really have two equations, and two unknowns (t and s). We can solve these equations for t and s! (Hopefully. If the lines do not intersect, then there is no solution for t and s.

---

So let's do some math :)

l1(t) = (x1, y1) + (x2-x1, y2-y1)*t
l2(s) = (u1, v1) + (u2-u1, v2-v1)*s

l1(t) = l2(s) implies two scalar equations:

x1 + (x2-x1)*t = u1 + (u2-u1)*s
y1 + (y2-y1)*t = v1 + (v2-v1)*s

(x2-x1)*t - (u2-u1)*s = u1-x1
(y2-y1)*t - (v2-v1)*s = v1-y1

And we can rewrite that as a matrix equation:

Using Cramer's Rule we can solve for t and s: If

then

Note that Cramer's rule is valid from a mathematical point of view, (and is easy to code) but it has poor numerical properties (see also GEPP vs Cramer's Rule). For serious applications, use LU decomposition, or LAPACK (available through NumPy).

---

So we can code it up as follows:

def line_intersection(line1, line2):
    """
    Return the coordinates of a point of intersection given two lines.
    Return None if the lines are parallel, but non-collinear.
    Return an arbitrary point of intersection if the lines are collinear.

    Parameters:
    line1 and line2: lines given by 2 points (a 2-tuple of (x,y)-coords).
    """
    (x1,y1), (x2,y2) = line1
    (u1,v1), (u2,v2) = line2
    (a,b), (c,d) = (x2-x1, u1-u2), (y2-y1, v1-v2)
    e, f = u1-x1, v1-y1
    # Solve ((a,b), (c,d)) * (t,s) = (e,f)
    denom = float(a*d - b*c)
    if near(denom, 0):
        # parallel
        # If collinear, the equation is solvable with t = 0.
        # When t=0, s would have to equal e/b and f/d
        if near(float(e)/b, float(f)/d):
            # collinear
            px = x1
            py = y1
        else:
            return None
    else:
        t = (e*d - b*f)/denom
        # s = (a*f - e*c)/denom
        px = x1 + t*(x2-x1)
        py = y1 + t*(y2-y1)
    return px, py


def crosses(line1, line2):
    """
    Return True if line segment line1 intersects line segment line2 and 
    line1 and line2 are not parallel.
    """
    (x1,y1), (x2,y2) = line1
    (u1,v1), (u2,v2) = line2
    (a,b), (c,d) = (x2-x1, u1-u2), (y2-y1, v1-v2)
    e, f = u1-x1, v1-y1
    denom = float(a*d - b*c)
    if near(denom, 0):
        # parallel
        return False
    else:
        t = (e*d - b*f)/denom
        s = (a*f - e*c)/denom
        # When 0<=t<=1 and 0<=s<=1 the point of intersection occurs within the
        # line segments
        return 0<=t<=1 and 0<=s<=1

def near(a, b, rtol=1e-5, atol=1e-8):
    return abs(a - b) < (atol + rtol * abs(b))

line1 = ((4,4),(10,10)) 
line2 = ((11,5),(5,11))
line3 = ((11,5),(9,7))
line4 = ((4,0),(10,6)) 

assert all(near(a,b) for a,b in zip(line_intersection(line1,line2), (8.0, 8.0)))
assert all(near(a,b) for a,b in zip(line_intersection(line1,line3), (8.0, 8.0)))
assert all(near(a,b) for a,b in zip(line_intersection(line2,line3), (11, 5)))

assert line_intersection(line1, line4) == None # parallel, non-collinear
assert crosses(line1,line2) == True
assert crosses(line2,line3) == False