Python intersection of two line segments not working

Question

I created this code to find the intersection point between 2 line segments in python, but it doesn't seem to produce correct results for all lines:

Note: I am using this in a game, where y values increase as you go down. So top left is (0,0), bottom left is say (0,300). Not sure if that makes a difference.

def getIntersectPoint(p1, p2, p3, p4):
    e = sys.float_info.epsilon * 1000

    # reorganize points from smaller to bigger in x-axis
    if p2[0]<p1[0]:
        p1,p2=p2,p1
    if p4[0]<p3[0]:
        p3,p4=p4,p3

    rise1 = float(p2[1]-p1[1])
    run1 = float(p2[0]-p1[0])
    if abs(run1) <= e:
        m1 = None
        b1 = float(p1[0])
    else:
        m1 = rise1/run1
        b1 = float(p1[1]-m1*p1[0])

    rise2 = float(p4[1]-p3[1])
    run2 = float(p4[0]-p3[0])
    if abs(run2) <= e:
        m2 = None
        b2 = float(p3[0])
    else:
        m2 = rise2/run2
        b2 = float(p3[1]-m2*p3[0])

    # check if lines are parallel
    if (m1==None and m2==None) or (m1!=None and m2!=None and abs(m1-m2)<=e):
        #check if they are right on top of each other
        if abs(b1-b2)<=e:
            return () # infinite points
        return None
    elif m1==None:
        iy2 = m2*b1 + b2
        ix, iy = b1, iy2
    elif m2==None:
        iy1 = m1*b2 + b1
        ix, iy = b2, iy1
    else:
        ix = (b1-b2)/(m2-m1)
        iy = m1*ix + b1

    # check if the intersection is in the bounding box
    if ix>=p1[0]-e and ix<=p2[0]+e and ix>=p3[0]-e and ix<=p4[0]+e:
        if iy>=p1[1]-e and iy<=p2[1]+e and iy>=p3[1]-e and iy<=p4[1]+e:
            return [ix, iy]

    return None

Some test cases generated when it found no intersection in p1,p2,p3,p4 format:

[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [440, 0]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 0] [0, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [0, 280] [440, 280]
[-545.901858671, 443.161842698] [198.177615767, 149.315393477] [440, 0] [440, 280]

Does anyone know what's wrong?

Thanks

This is surely a creative way to test for line intersection; I would recommend googling a more standard approach to line intersection, and building your solution from that. — Eelco Hoogendoorn, Jan 10 '16 at 19:13
Some code comments, test cases, and expected/failing outputs would be useful — Spacedman, Jan 10 '16 at 19:14
A good method to do this is given in the answer to [this question](http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect). — xnx, Jan 10 '16 at 19:32

score 0 · Answer 1 · answered Jan 10 '16 at 20:23

The problem you have is that you are sometimes swapping the order of the line segment endpoints based on their x-values. But this also changes the order of the y-values and so your test for the intersection point being within the "bounding box" fails. You could try the following for that check:

# check if the intersection is in the bounding box
    if ix>=p1[0]-e and ix<=p2[0]+e and ix>=p3[0]-e and ix<=p4[0]+e:
        y1, y2, y3, y4 = p1[1], p2[1], p3[1], p4[1]
        if y2 < y1:
            y2, y1 = y1, y2
        if y4 < y3:
            y4, y3 = y3, y4
        if iy>=y1-e and iy<=y2+e and iy>=y3-e and iy<=y4+e:
                return [ix, iy]

Python intersection of two line segments not working

1 Answers1