How to check if two given line segments intersect in python

In this article, we come to know how to check if two given line segments intersect in python:-

Given line segments intersect each other:

If two given line segments intersect or not: We can check two line segments in O(1) time. This approach takes O(n2).

Sweep Line Algorithm: The algorithm first sorts the end points along the x-axis from left to right, then it passes a vertical line through all  the points from left to right and checks for intersection.

They are few steps to be followed:-

1. Let there be n given lines.
2. Start from the leftmost point. (a: Insert a new line segment, b: Delete a line segment, c: Find predecessor and successor)

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 doIntersection(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