Попытка определить, пересекается ли одна линия с другой, но она терпит неудачу, даже если линии пересекаются
В начале моей программы я рисую шесть отрезков прямой вертикальной линии, а затем случайным образом рисую столько отрезков, сколько хочет пользователь. Каждый раз, когда он рисуется, я проверяю, пересекает ли он один из этих шести сегментов. Проблема в том, что, даже если они пересекаются, он никогда не возвращает 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
2 ответа
Если вы просто пытаетесь найти точки пересечения, это довольно просто:
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)
Замените вашу функцию, которая проверяет наличие сегментов (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
Если вы хотите понять идею, лежащую в основе формулы для параметров s а также tпосмотри на этот ответ (параметры u муравей t там)
В основном, если 0 <= s <= 1 and 0 <= t <= 1, то пересечение двух линий (которые являются продолжением наших сегментов) находится на обоих наших сегментах. В противном случае это снаружи.
Особый случай. Если dx1 * dy2 - dx2 * dy1 == 0 тогда наши линии параллельны. У нас будет пересечение только в том случае, если оба отрезка находятся на одной линии ( третья точка коллинеарна первым двум), и они фактически пересекаются на этой линии (проекции сегментов на обе оси пересекаются).