如何判断两条线段相交

%matplotlib notebook
import matplotlib.pyplot as plt

plt.text(1, 0.96, 'a')
plt.text(2, 1.96, 'b')
plt.text(1, 1.96, 'c')
plt.text(2, 0.96, 'd')
# [x1, x2], [y1, y2]
plt.plot([1, 2], [1, 2])
plt.plot([1, 2], [2, 1])
plt.show()

<IPython.core.display.Javascript object>


plt.text(1, 0.96, 'a')
plt.text(1.39, 1.36, 'b')
plt.text(1, 1.96, 'c')
plt.text(2, 0.96, 'd')
# [x1, x2], [y1, y2]
plt.plot([1, 1.4], [1, 1.4
plt.plot([1, 2], [2, 1])
plt.show()

<IPython.core.display.Javascript object>


如何判断两个点是否在一条线段两侧

• 叉积

• 右手定则

import numpy as np

# 画文字
plt.text(1, 0.96, 'a')
plt.text(2, 1.96, 'b')
plt.text(1, 1.96, 'c')
plt.text(2, 0.96, 'd')

# 画线段
# [x1, x2], [y1, y2]
plt.plot([1, 2], [1, 2])
plt.plot([1, 2], [2, 1])

# 画向量
plt.show()

<IPython.core.display.Javascript object>


代码实现

def outer_product(vec1, vec2):
"""
计算两个向量的外积
"""
return vec2[0] * vec1[1] - vec1[0] * vec2[1]

def isBeside(segment, point1, point2):
"""
判断两个点是否在一条线段的两侧
"""
start, end = segment[0], segment[1]
center_vector = [end[0] - start[0], end[1] - start[1]]
left_vector = [point1[0] - start[0], point1[1] - start[1]]
right_vector = [point2[0] - start[0], point2[1] - start[1]]

return outer_product(left_vector, center_vector) * outer_product(right_vector, center_vector) <= 0

# segment格式[[1, 1], [2, 2]], 为点[1, 1]和点[2, 2]连成的线段
def isCross(segment1, segment2):
"""
判断两条线段是否相交
"""
return isBeside(segment1, segment2[0], segment2[1]) and isBeside(segment2, segment1[0], segment1[1])

result1 = isCross([[1, 1], [2, 2]], [[1, 2], [2, 1]])
print(result1)

result2 = isCross([[1, 1], [1.4, 1.4]], [[1, 2], [2, 1]])
print(result2)

True
False