0

在我的程序开始时，我绘制了六个垂直的直线段，然后我随机绘制了用户想要的任意多的线段。每次绘制它时，我都会检查它是否与这六个段之一相交。问题是，即使它们相交，它也永远不会返回 True。

我正在使用 Python，并对两条线使用 y = mx + b 来找到它们相交的公共点，并检查它是否位于两条线段上。这是代码：

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
4

2 回答 2

0

如果您只是想找到交点，这很容易：

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)
于 2015-11-04T03:12:54.370 回答
0

将检查段碰撞 ( checkStick)的函数替换为

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

如果您想了解参数和公式背后的想法，请查看此答案（那里的参数）stut

基本上，如果0 <= s <= 1 and 0 <= t <= 1，则两条线的交点（它们是我们的线段的延伸）在我们的两个线段上。否则它在外面。

特例。如果dx1 * dy2 - dx2 * dy1 == 0那么我们的线是平行的。只有当两个线段都在同一条线上（第三点与前两个点共线）并且它们实际上在这条线上相交（线段投影到两个轴相交）时，我们才会有相交。

于 2015-11-04T02:32:56.197 回答