在《集体智慧编程》的随机优化章节，有提到判断两条线段是否相交的算法，我觉得非常神奇，研究了好久，终于搞明白了。

如何判断两条线段相交

两点连成一条线段，我们先在二维平面上研究一下。 假设有2个点a = (1, 1), b = (3, 3), 组成一条线段ab, 有另外2个点c = (1, 2), d = (2, 1)，组成另外一条线段cd，如下图:

%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>

怎么样才算两条线段相交呢？首先，对于线段ab来说，如果c和d两个点在线段ab的两侧，那么线段ab和线段cd就有一半的可能是相交的。因为还有可能出现下面这种情况:

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>

这种情况下，对于线段ab来说，c和d两个点也在线段ab的两侧，但是两条线段并不相交。如果把这个条件反过来，对于线段cd来说，a和b点要求必须在线段cd的两侧，两个条件同时满足，就能保证两条线段相交了!

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

好，现在的问题变成，如果判断两个点是否在一条线段两侧了，实际上转化成判断2个点是否在一条直线两侧。

需要用到向量的叉积！

  • 叉积

两个向量A和B的叉积又叫外积或者向量积，结果是另外一个向量C，C的方向垂直于两个向量A和B所形成的平面, C的方向由右手定则决定。

  • 右手定则

伸出右手，四指指向向量A的方向，然后往里摆向向量B，摆的角度不能超过180度 , 这个时候大拇指指向的方向就是叉积C的方向。如果发现摆的角度大于180度，一般把大拇指的方向倒过来就对了。

用图来看可以更直观:

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.arrow(1, 1, 0, 1, head_width=0.02, length_includes_head=True, color='r')
plt.arrow(1, 1, 1, 0, head_width=0.02, length_includes_head=True, color='r')
plt.arrow(1, 1, 1, 1, head_width=0.02, length_includes_head=True, color='r')
plt.show()

<IPython.core.display.Javascript object>

以线段ab为例，要证明c和d点在线段ab的两侧，上图画了3个向量，分别为AC, AB, AD, 现在只需要计算出来两个叉积就可以: $$ P1 = AC \times AB $$ $$ P2 = AD \times AB $$

运用右手定则，可以发现P1的方向是向屏幕里面的，而P2的方向是向着屏幕外面的，方向不同，则c和d点在线段ab的两侧。

代码实现

现在写个函数来判断两条线段是否相交。

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

分别用了两条相交的线段和两条不相交的线段来测试，结果跟预期的一致！

参考资料