Trying to find if a line intersects with another, but it is failing even when the lines do intersect

Question

At the start of my program I draw six straight vertical line segments, and then after I randomly draw as many line segments as the user wants. Every time it is drawn, I check if it does intersect one of those six segments. The problem is, even if they intersect, it never returns True.

I am using Python, and used y = mx + b for both lines to find a common point where they do intersect, and check if it lies on both of the line segments. Here is the code:

import random
import turtle


wn = turtle.Screen()
wn.setworldcoordinates(-50, -50, 50.5, 50)

intersectCount = 0
stickCount = 0


def drawLines():
    draw = turtle.Turtle()
    for x in range(-5, 6):
        if x % 2 != 0:
            draw.penup()
            draw.goto(x * 10, 50)
            draw.pendown()
            draw.goto(x * 10, -50)


def drawStick():
    draw = turtle.Turtle()
    draw.color("Brown")
    rand = random.Random()

    stickLength = 10  # sticks are 10 units long
    x1 = rand.randint(-50, 50)
    y1 = rand.randint(-50, 50)
    x2 = 0
    y2 = 0

    direction = rand.randint(1, 4)

    if(direction == 1):
        x2 = x1 + stickLength
        y2 = y1 - stickLength
    elif(direction == 2):
        x2 = x1 - stickLength
        y2 = y1 + stickLength
    elif(direction == 3):
        x2 = x1 + stickLength
        y2 = y1 + stickLength
    else:
        x2 = x1 - stickLength
        y2 = y1 - stickLength

    draw.penup()
    draw.goto(x1, y1)
    draw.pendown()
    draw.goto(x2, y2)

    global stickCount
    stickCount += 1
    for x in range(-5, 6):
        if x % 2 != 0:
            if (checkStick(x * 10, 50, x * 10, -50, x1, y1, x2, y2)):
                global intersectCount
                intersectCount += 1
                break


def drop():
    sticks = input("Enter how many sticks you would like to drop: ")
    sticks = int(sticks)
    for x in range(0, sticks):
            drawStick()

    print(str(stickCount) + " sticks were dropped")
    print("There were " + str(intersectCount) + " sticks that intersected")


def checkStick(x1, y1, x2, y2, sX1, sY1, sX2, sY2):
    #greatest and least x coordinates from the line
    greatestX = 0
    leastX = 0
    if(x1 == x2 or x1 > x2):
        greatestX = x1
        leastX = x2
    else:
        greatestX = x2
        leastX = x1
    #same thing but with y's
    greatestY = 0
    leastY = 0
    if(y1 == y2 or y1 > y2):
        greatestY = y1
        leastY = y2
    else:
        greatestY = y2
        leastY = y1
    #same thing but with stick x's
    gStickX = 0
    lStickX = 0
    if(sX1 == sX2 or sX1 > sX2):
        greatestX = sX1
        leastX = sX2
    else:
        greatestX = sX2
        leastX = sX1
    #same thing but with stick x's
    gStickY = 0
    lStickY = 0
    if(sY1 == sY2 or sY1 > sY2):
        greatestY = sY1
        leastY = sY2
    else:
        greatestY = sY2
        leastY = sY1

    #y = mx + b
    #the stick
    stickSlope = ((sY2 - sY1) / (sX2 - sX1))  # m, or the slope
    stickIntercept = sY1 - (stickSlope * sX1)  # b = y - (mx)
    #the line
    lineSlope = 0
    if(x2 - x1 != 0):  # m, or the slope
        lineSlope = (y2 - y1) / (x2 - x1)

    lineIntercept = y1 - (lineSlope * x1)  # b = y - (mx)
    #set the two formulas equal to each other, find x and then y, that is where they intersect#this will be reset as the x of intersection
    x = (lineIntercept - stickIntercept) / (stickSlope - lineSlope)  # solving for x by getting the x's on one side, and other numbers on one side, then dividing out whatever number x is being multiplied by to get what x is
    y = ((stickSlope * x) + stickIntercept)  # back to y = mx + b now that we have all the variable to find y
#points intersect at x, y

    if(stickSlope == lineSlope):
        return False  # parallel
    else:
        #checking if it is within the line segment
        if(x <= greatestX and x >= leastX):
            if(y <= greatestY and y >= leastY):
                #checking if it is within the stick segment
                if(x <= gStickX and x >= lStickX):
                    if(y <= gStickY and x >= lStickY):
                        return True
                    else:
                        return False
                else:
                    return False
            else:
                return False
        else:
            return False


drawLines()
drop()

raw_input()  # waits for the user to click a key to exit

Please give an example where it doesn't do what you expect. Make it as small as you can. — saulspatz, Nov 04 '15 at 03:02
@saulspatz it is not working where I am checking the intersection checkStick(). I included all the code because it is necessary to understand. It is not correctly detecting when line cross another line (never returns True). — FyreeW, Nov 04 '15 at 03:06
The code has syntax errors in it. You can't be running this under python 3.5. — saulspatz, Nov 04 '15 at 03:10

score 0 · Answer 1 · edited May 23 '17 at 11:46

Replace your function which checks for segments collision (checkStick) with

def checkStick(x1, y1, x2, y2, x3, y3, x4, y4):
    dx1 = x2 - x1
    dy1 = y2 - y1
    dx2 = x4 - x3
    dy2 = y4 - y3

    if dx1 * dy2 - dx2 * dy1 == 0:
        # Segments are on parallel lines. There will be intersection if segments
        # are collinear and they give intersecting projection to both axis
        segments_collinear = (y3 - y1) * dx1 == dy1 * (x3 - x1)
        collision_ox = max(x1, x2) >= min(x3, x4) and min(x1, x2) <= max(x3, x4)
        collision_oy = max(y1, y2) >= min(y3, y4) and min(y1, y2) <= max(y3, y4)
        return segments_collinear and collision_ox and collision_oy

    s = (dx1 * (y1 - y3) - dy1 * (x1 - x3)) / (dx1 * dy2 - dx2 * dy1)
    t = (dx2 * (y1 - y3) - dy2 * (x1 - x3)) / (dx1 * dy2 - dx2 * dy1)

    return 0 <= s <= 1 and 0 <= t <= 1

If you want to understand the idea behind formula for parameters s and t, look at this answer (parameters u ant t there)

Basically, if 0 <= s <= 1 and 0 <= t <= 1, then intersection of two lines (which are extensions of our segments) is at both of our segments. Otherwise it is outside.

Special case. If dx1 * dy2 - dx2 * dy1 == 0 then our lines are parallel. We will have intersection only if both segments are on the same line (3rd point is collinear with first two) and they actually intersect on this line (sements projections to both axis intersect).

Ah I get it now, thank you for the help. It works great now! I will continue to read that post more so I can better understand what is going on. — FyreeW, Nov 04 '15 at 03:33

score 0 · Answer 2 · answered Nov 04 '15 at 03:12

If you are just trying to find intersection points it is rather easy:

def intersects(m1, b1, m2, b2, xlims=[0, 1], ylims=[0, 1]):
    if m1 == m2 and b1 != b2:
        return None, None

    intersect_x = (b2 - b1) / (m1 - m2)
    if intersect_x < xlims[0] or intersect_x > xlims[1]:
        return None, None

    intersect_y = m1 * intersect_x + b1
    if intersect_y < ylims[0] or intersect_y > ylims[1]:
        return None, None

    return intersect_x, intersect_y


if __name__ == '__main__':
    a, b = intersects(1, 0, -1, 1)
    print(a, b)
    a, b = intersects(1, 0, 1, 0.5)
    print(a, b)

Trying to find if a line intersects with another, but it is failing even when the lines do intersect

2 Answers2