def line_segments_intersect(p1, p2, q1, q2, magn_delta_p):
# solve equation line1 = line2
# p1 + lambda * (p2-p1) = q1 + my * (q2-q1)
# lambda * (p2-p1) - my * (q2-q1) = q1 - p1
# normalize deltas to 1
# lambda * (p2-p1)/|p1-p2| - my * (q2-q1)/|q1-q2| = q1 - p1
# magn_delta_p = |p1-p2| (magnitude)
# magn_delta_q = euclidean_distance(q1[0], q1[1], q2[0], q2[1])
if max(p1[0], p2[0]) < min(q1[0], q2[0]) or max(q1[0], q2[0]) < min(p1[0], p2[0]) or \
max(p1[1], p2[1]) < min(q1[1], q2[1]) or max(q1[1], q2[1]) < min(p1[1], p2[1]):
return False
dif_p_x = p2[0] - p1[0]
dif_p_y = p2[1] - p1[1]
dif_q_x = q2[0] - q1[0]
dif_q_y = q2[1] - q1[1]
a = array([[dif_p_x, -dif_q_x], [dif_p_y, -dif_q_y]])
# [[dif_p_x / magn_delta_p, -dif_q_x / magn_delta_q], [dif_p_y / magn_delta_p, -dif_q_y / magn_delta_q]])
b = array([q1[0] - p1[0], q1[1] - p1[1]])
try:
x = linalg.solve(a, b)
except linalg.linalg.LinAlgError:
# Singular matrix (lines parallel, there is not intersection)
return False
if x[0] < 0 or x[0] > 1 or x[1] < 0 or x[1] > 1:
# intersection of the two lines appears before or after actual line segments
# in this use case it is important to include the points themselves when checking for intersections
# that way a new edge that barely touches the old polygon is also legal
return False
return True
评论列表
文章目录