Why does my function claim these lines intersect?

Question

I have a python function that takes four points and checks if two lines made of those points intersect, if they do it will return the point where they intersect. The function works for the most part, except it seemingly treats all lines as infinite, even though they aren't.

class Vector:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y

def intersect(a, b, c, d):
    den = ((b.x - a.x) * (d.y - c.y)) - ((b.y - a.y) * (d.x - c.x))

    num1 = ((a.y - c.y) * (d.x - c.x)) - ((a.x - c.x) * (d.y - c.y))
    num2 = ((a.y - c.y) * (b.x - a.x)) - ((a.x - c.x) * (b.y - a.y))
    if not den:
        return

    r = num1 / den
    s = num2 / den

    if 0 < r < 1 and s > 0:
        pt = [0, 0]
        pt[0] = a.x + r * (b.x - a.x)
        pt[1] = a.y + r * (b.y - a.y)
        return pt
    else:
        return

The inputs I'm giving it are:

intersect(
    Vector(302,252),
    Vector(306,252),
    Vector(305,455),
    Vector(305,400)
)

Which gives the intersecting point of 305, 252. If these lines were infinite they would intersect here, but they aren't.

Please include an example of a call to `intersect` when it fails. Also, it is a bad practice to return different data types from the same function. Consider returning, say, an empty list when the lines do not intersect. — DYZ, Jan 09 '20 at 07:50
@DYZ I realized I forgot an example, I added one. Also, noted on the returning an empty list. Thank you! — poccket, Jan 09 '20 at 07:51
I tried your example, the function correctly returns `None`. — DYZ, Jan 09 '20 at 07:52
@DYZ This is gonna sound remarkably stupid, but I had the final two inputs first, and that causes the problem. Still, odd, it shouldn't do that right? — poccket, Jan 09 '20 at 07:57
@DYZ Here's an input that should return None but instead returns a point — poccket, Jan 09 '20 at 08:16
Did you check this? https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect — ChatterOne, Jan 09 '20 at 08:53
@ChatterOne Unfortunately, I need the function to return the intersection, not a boolean — poccket, Jan 09 '20 at 15:35

mujjiga · Answer 1 · 2020-01-10T07:45:35.817

There is lot of math involve in finding if two line are intersecting. check the link for math behind it. The python implementation of the same is below

import numpy as np

class Point:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y

class Line:
    def __init__(self, x: Point, y: Point):
        self.p1 = x
        self.p2 = y

def find_intersection(l1, l2):
    def slope(l):
        return (l.p2.y - l.p1.y)/(l.p2.x - l.p1.x)

    def intercept(l, m):
        return l.p1.y - m*l.p1.x


    m1 = slope(l1)
    m2 = slope(l2)
    b1 = intercept(l1, m1)
    b2 = intercept(l2, m2)

    A = np.array([
        [-m1, 1],
        [-m2, 1]
    ])

    b = np.array([[b1],[b2]])
    return np.dot(np.linalg.inv(A), b)        

# check whether p is on the line or not
def onLine(l1: Line, p: Point):   
    return True if p.x <= max(l1.p1.x, l1.p2.x) and p.x <= min(l1.p1.x, l1.p2.x) and p.y <= max(l1.p1.y, l1.p2.y) and p.y <= min(l1.p1.y, l1.p2.y) else False           


def direction(a, b, c):
    val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if val == 0:
        return 0     # colinear
    elif val < 0:
        return 2     # anti-clockwise direction
    return 1       # clockwise direction

def isIntersect(l1: Line, l2: Line):
    #four direction for two lines and points of other line
    dir1 = direction(l1.p1, l1.p2, l2.p1);
    dir2 = direction(l1.p1, l1.p2, l2.p2);
    dir3 = direction(l2.p1, l2.p2, l1.p1);
    dir4 = direction(l2.p1, l2.p2, l1.p2);

    if dir1 != dir2 and dir3 != dir4 :
        return True, find_intersection(l1, l2)

    if dir1==0 and onLine(l1, l2.p1): # when p2 of line2 are on the line1
        return True, l1.p1

    if dir2==0 and onLine(l1, l2.p2): # when p1 of line2 are on the line1
        return True, l2.p2

    if dir3==0 and onLine(l2, l1.p1): #when p2 of line1 are on the line2
        return True, l1.p1

    if dir4==0 and onLine(l2, l1.p2): #when p1 of line1 are on the line2
        return True, l1.p2

    return False, None

Test Cases:

isIntersect(Line(Point(15, 10), Point(49,25)),
                           Line(Point(32, 32), Point(29,5)))

isIntersect(Line(Point(0, 0), Point(5, 5)),
                           Line(Point(5, 6), Point(3, 10)))

If the points are co-linear then return one of them (infinite solutions)
If the points are not co-linear and intersect then there is one unique solution. Convert the two lines into standard line equations find the intersection by solving the equations using matrix inverse. ie. find inverse(A).b

This doesn't work for me, as it just returns a boolean, when I need the point it intersects. — poccket, Jan 09 '20 at 15:33

score 0 · Accepted Answer · answered Jan 09 '20 at 17:28

I'm still not sure why, but my function assumes lines go infinitely from a/c in the direction of b/d. Since I actually need this for a different part of my program, I made one that actually works and named it segintersect(). It uses the shapely module, so you'll have to install that, but after all the various functions I've tried, this one worked with the least headache.

from shapely.geometry import LineString, Point

class Vector:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y

def segintersect(a1, a2, b1, b2):
    line1 = LineString([(a1.x, a1.y), (a2.x, a2.y)])
    line2 = LineString([(b1.x, b1.y), (b2.x, b2.y)])

    int_pt = line1.intersection(line2)
    return [int_pt.x, int_pt.y] if (type(int_pt) == Point) else []

This function properly returns line segment intersections.

score 0 · Answer 3 · answered Jan 10 '20 at 07:51

If you're ok with using shapely, I think that your own is the best answer.

If you're curious about a way to find it without using external libraries, what you can do is find the point where the two lines intersect (note: not segments, the lines), and then check if that point lies on both segments.

To check if it lies on the segments you can check the distance from the two points defining the segment and compare that to the length of the segment. If the sum of the two distances is the same as the length of the segment, then the point lies on it.

This is some example code:

class Vector:
    def __init__(self, x: float, y: float):
        self.x = x
        self.y = y

def calc_distance(a, b):
    return math.sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y))

def intersect(a, b, c, d):
    x1diff = b.x - a.x
    x2diff = d.x - c.x

    y1diff = b.y - a.y
    y2diff = d.y - c.y

    m1 = 0
    m2 = 0
    if (x1diff != 0):
        m1 = (b.y - a.y) / (b.x - a.x)

    if (x2diff != 0):
        m2 = (d.y - c.y) / (d.x - c.x)

    # If the slope is the same, the segments are parallel
    if (m1 == m2):
        return None

    q1 = a.y - (m1 * a.x)
    q2 = c.y - (m2 * c.x)

    x = (q2 - q1) / (m1 - m2)
    y = (m1 * x) + q1

    dist_from_a = calc_distance(Vector(x, y), a)
    dist_from_b = calc_distance(Vector(x, y), b)
    segment_length = calc_distance(a, b)

    if (dist_from_a + dist_from_b) != segment_length:
        return None

    dist_from_c = calc_distance(Vector(x, y), c)
    dist_from_d = calc_distance(Vector(x, y), d)
    segment_length = calc_distance(c, d)

    if (dist_from_c + dist_from_d) == segment_length:
        return Vector(x, y)

    return None

v = intersect(
    Vector(302,252),
    Vector(306,252),
    Vector(305,455),
    Vector(305,400)
)

print(v.x, v.y) # This will print None

v = intersect(
    Vector(0, 0),
    Vector(2, 2),
    Vector(2, 0),
    Vector(0, 2),
)

print(v.x, v.y) # This will print 1.0 1.0

Why does my function claim these lines intersect?

3 Answers3