線分交差判定

線分が交差しているかを判定するアルゴリズム

import numpy as np
a1 = np.array([1,1])
a2 = np.array([5,5])
# crossing
b1 = np.array([3,1])
b2 = np.array([1,3])
# non-crossing
c1 = np.array([3,1])
c2 = np.array([5,3])

def judge(p1,p2,p3,p4):
    t1 = (p1[0] - p2[0]) * (p3[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p3[0])
    t2 = (p1[0] - p2[0]) * (p4[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p4[0])
    t3 = (p3[0] - p4[0]) * (p1[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p1[0])
    t4 = (p3[0] - p4[0]) * (p2[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p2[0])
    return t1*t2<0 and t3*t4<0

print judge(a1,a2,b1,b2)
print judge(a1,a2,c1,c2)
print judge(b1,b2,c1,c2)

True
False
True

returnの行の不等号(<)を等号つき(<=)にすると、クロスじゃなくてぎりぎり重なっているのもOKになる