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
    


Answer: 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](http://stackoverflow.com/a/565282/595870)
(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](http://math.stackexchange.com/questions/38338/methods-for-showing-three-
points-in-mathbbr2-are-colinear-or-not)) and they actually intersect on this
line (sements projections to both axis intersect).

