Given two line segments (p1,q1)and (p2,q2), find if the given line segments intersect with each other.
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified.
1.General case:
-(p1,q1,p2) and (p1,q1,q2) have different orientations and
-(p2,q2,p1) and (p2,q2,,q1) have different orientations.
2.Special case:
-(p1,q1,p2) ,(p1,q1,q2),(p2,q2,p1) and (p2,q2,q1) are all collinear and
-the x-projections of(p1,q1) and (p2,q2) intersect
-the y-projections of (p1,q1) and (p2,q2) intersect.
class Point:
def _init_(self, x, y):
self.x = x
self.y = y
def onSegment(p, q, r):
if ( (q.x <= max(p.x, r.x)) and (q.x >= min(p.x, r.x)) and
(q.y <= max(p.y, r.y)) and (q.y >= min(p.y, r.y))):
return True
return False
def orientation(p, q, r):
val = (float(q.y - p.y) * (r.x - q.x)) - (float(q.x - p.x) * (r.y - q.y))
if (val > 0):
return 1
elif (val < 0):
return 2
else:
return 0
def doIntersect(p1,q1,p2,q2):
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)
if ((o1 != o2) and (o3 != o4)):
return True
if ((o1 == 0) and onSegment(p1, p2, q1)):
return True
if ((o2 == 0) and onSegment(p1, q2, q1)):
return True
if ((o3 == 0) and onSegment(p2, p1, q2)):
return True
if ((o4 == 0) and onSegment(p2, q1, q2)):
return True
return False
p1 = Point(1, 1)
q1 = Point(10, 1)
p2 = Point(1, 2)
q2 = Point(10, 2)
if doIntersect(p1, q1, p2, q2):
print("Yes")
else:
print("No")
p1 = Point(10, 0)
q1 = Point(0, 10)
p2 = Point(0, 0)
q2 = Point(10,10)
if doIntersect(p1, q1, p2, q2):
print("Yes")
else:
print("No")
p1 = Point(-5,-5)
q1 = Point(0, 0)
p2 = Point(1, 1)
q2 = Point(10, 10)
if doIntersect(p1, q1, p2, q2):
print("Yes")
else:
print("No")
Output:
No Yes No