【面】判断两线段是否相交

更新于
快速排斥实验 + 跨立实验，判断平面上任意两条线段是否相交。

STEP1：快速排斥
设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，若R、T不相交，则两线段不可能相交。而判断两个矩形是否相交，只要任一矩形的最右端都大于另一矩形的最左端且任一矩形最高端大于另一矩形的最低端，则两矩形相交；反之，若其中任一条件不满足，两矩形不相交。

STEP2：跨立实验
如果两线段相交，则两线段必须互相跨立对方，即其中任一线段的两端一定在另一线段的两侧。这一步用叉积去做就可以了，即只要判断向量P1Q1和向量P1Q2是否在P1P2的两边相对的位置上，如果是这样，则线段P1P2跨立线段Q1Q2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Point:
    def __init__(self, x, y):
        self.x=x
        self.y=y 

class Vector:
    def __init__(self, start_point, end_point):
        self.start_point, self.end_point = start_point, end_point
        self.x = end_point.x - start_point.x
        self.y = end_point.y - start_point.y
    
def vector_negative(vector):   # 向量取反
    return Vector(vector.end_point, vector.start_point)

def vector_product(vectorA, vectorB):  # 向量积/向量的叉积
    return vectorA.x * vectorB.y - vectorB.x * vectorA.y

def isOverlap(A, B, C, D):
    P1 = Point(A[0], A[1])
    P2 = Point(B[0], B[1])
    Q1 = Point(C[0], C[1])
    Q2 = Point(D[0], D[1])

    # 快速排斥
    if (max(P1.x, P2.x) >= min(Q1.x, Q2.x)    # 矩形1最右端大于矩形2最左端
    and max(Q1.x, Q2.x) >= min(P1.x, P2.x)     # 矩形2最右端大于矩形最左端
    and max(P1.y, P2.y) >= min(Q1.y, Q2.y)     # 矩形1最高端大于矩形最低端
    and max(Q1.y, Q2.y) >= min(P1.y, P2.y)):   # 矩形2最高端大于矩形最低端

        # 跨立实验
        P1Q1 = Vector(P1, Q1)
        P1Q2 = Vector(P1, Q2)
        P2Q1 = Vector(P2, Q1)
        P2Q2 = Vector(P2, Q2)
        Q1P1 = vector_negative(P1Q1)
        Q1P2 = vector_negative(P2Q1)
        Q2P1 = vector_negative(P1Q2)
        Q2P2 = vector_negative(P2Q2)
        
        return (vector_product(P1Q1, P1Q2) * vector_product(P2Q1, P2Q2) <= 0) and (vector_product(Q1P1, Q1P2) * vector_product(Q2P1, Q2P2) <= 0)
    else:
        return False

print(isOverlap([1,1], [1,5], [0,1], [0,4]))
print(isOverlap([0,0], [0,5], [1,1], [-1,4]))
0%