def intersect s1 s2 if max s1 s1 min s2 s2 or max s1 s1 min s2 s2 or m

 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
def intersect(s1, s2):
if max([s1[0][0],s1[1][0]]) < min([s2[0][0],s2[1][0]]) or \
max([s1[0][1],s1[1][1]]) < min([s2[0][1],s2[1][1]]) or \
max([s2[0][0],s2[1][0]]) < min([s1[0][0],s1[1][0]]) or \
max([s2[0][1],s2[1][1]]) < min([s1[0][1],s1[1][1]]):
return False
z = (s1[1][1]-s1[0][1])*(s2[0][0]-s2[1][0])-(s2[0][1]-s2[1][1])*(s1[1][0]-s1[0][0])
ca = (s1[1][1]-s1[0][1])*(s2[0][0]-s1[0][0])-(s2[0][1]-s1[0][1])*(s1[1][0]-s1[0][0])
cb = (s2[0][1]-s1[0][1])*(s2[0][0]-s2[1][0])-(s2[0][1]-s2[1][1])*(s2[0][0]-s1[0][0])
if sum(map(abs,[z,ca,cb]))<eps:
# on one line. compare xs
if (s1[0][0] <= s2[0][0] <= s1[1][0] or
s1[0][0] <= s2[1][0] <= s1[1][0]) and s1[0][0]!=s1[1][0]:
return True
if (s1[0][1] <= s2[0][1] <= s1[1][1] or
s1[0][1] <= s2[1][1] <= s1[1][1]) and s1[0][1]!=s1[1][1]:
return True
return False
if z == 0:
return False
ua=ca/z
ub=cb/z
if 0 <= ua <= 1 and 0 <= ub <= 1:
return True
return False