Line Segment Intersection

class Point :

    def __init__(self, arg_x, arg_y) :
        self.x = arg_x
        self.y = arg_y

# Fetch the orientation of triplet (p, q and r).
# Return 0, If the points p, q and r are collinear.
# Return 1, if the points are oriented clockwise.
# Return 2, if the points are oriented anticlockwise

def Get_Orientation (point_p, point_q, point_r) :

    delta = ( point_q.y - point_p.y ) * ( point_r.x - point_q.x ) - \
            ( point_q.x - point_p.x ) * ( point_r.y - point_q.y )

    if (delta == 0) :
        return 0
    elif (delta > 0) :
        return 1

    return 2

# Check if point_r lies on the segment p-q. 
# If point_r lies on line p-q, then the x-coordinate of point_r should be between the x-coordinates of
# point_p and point_q and the y-coordinate of point_r should be between the y-coordinates of point_p and
# point_q.

def Check_On_Segment (point_p, point_q, point_r) :

    if (point_r.x <=  max (point_p.x, point_q.x) and point_r.x >= min (point_p.x, point_q.x) and
        point_r.y <=  max (point_p.y, point_q.y) and point_r.y >= min (point_p.y, point_q.y) ) :
        return True

    return False

# Return True if line segment at point (p1, q1) intersect with line segment at point (p2, q2)
def Intersect (point_p1, point_q1, point_p2, point_q2) :

    or_1 = Get_Orientation (point_p1, point_q1, point_p2)
    or_2 = Get_Orientation (point_p1, point_q1, point_q2)
    or_3 = Get_Orientation (point_p2, point_q2, point_p1)
    or_4 = Get_Orientation (point_p2, point_q2, point_q1)

    # General case : Points are non-collinear.
    if (or_1 != or_2 and or_3 != or_4) :
        return True

    # Special case : Points are collinear.
    # If points p1, q1 and p2 are collinear, check if point p2 lies on segment p1-q1
    if (or_1 == 0 and Check_On_Segment (point_p1, point_q1, point_p2)) :
        return True

    # If points p1, q1 and q2 are collinear, check if point q2 lies on segment p1_q1
    if (or_2 == 0 and Check_On_Segment (point_p1, point_q1, point_q2)) :
        return True

    # If points p2, q2 and p1 are collinear, check if point p1 lies on segment p2_q2
    if (or_3 == 0 and Check_On_Segment (point_p2, point_q2, point_p1)) :
        return True

    # If points p2, q2 and q1 are collinear, check if point q1 lies on segment p2_q2
    if (or_4 == 0 and Check_On_Segment (point_p2, point_q2, point_q1)) :
        return True

    return False

def main() :

    # Segment 1 (p1--q1)
    list_p1 = [Point(1,1), Point(1,1), Point(1,2), Point(5,2), Point(4,1)]
    list_q1 = [Point(4,4), Point(4,4), Point(3,4), Point(7,4), Point(6,3)]

    # Segment 2(p2--q2)
    list_p2 = [Point(2,2), Point(3,1), Point(1,4), Point(6,5), Point(6,5)]
    list_q2 = [Point(5,5), Point(6,4), Point(3,1), Point(8,3), Point(8,3)]

    for i in range(len(list_p1)) :

        if (Intersect(list_p1[i], list_q1[i], list_p2[i], list_q2[i])) :
              print( "Line p1 (" + str(list_p1[i].x) + "," + str(list_p1[i].y) + ") q1 (" + str(list_q1[i].x) + "," + str(list_q1[i].y) + ") --- Line p2 (" + str(list_p2[i].x) + "," + str(list_p2[i].y) + ") q2 (" + str(list_q2[i].x) + "," + str(list_q2[i].y) + ") intersect")
        else :
              print( "Line p1 (" + str(list_p1[i].x) + "," + str(list_p1[i].y) + ") q1 (" + str(list_q1[i].x) + "," + str(list_q1[i].y) + ") --- Line p2 (" + str(list_p2[i].x) + "," + str(list_p2[i].y) + ") q2 (" + str(list_q2[i].x) + "," + str(list_q2[i].y) + ") don't intersect")

if __name__ == "__main__" :
    main()

Line p1 (1,1) q1 (4,4) --- Line p2 (2,2) q2 (5,5) intersect
Line p1 (1,1) q1 (4,4) --- Line p2 (3,1) q2 (6,4) don't intersect
Line p1 (1,2) q1 (3,4) --- Line p2 (1,4) q2 (3,1) intersect
Line p1 (5,2) q1 (7,4) --- Line p2 (6,5) q2 (8,3) intersect
Line p1 (4,1) q1 (6,3) --- Line p2 (6,5) q2 (8,3) don't intersect

#include <iostream>
#include <vector>

class Point {
    public:
    Point (int x_, int y_) : x(x_), y(y_)
    {}
    int x;
    int y;
};

// Fetch the orientation of triplet (p, q and r).
// Return 0, If the points p, q and r are collinear.
// Return 1, if the points are oriented clockwise.
// Return 2, if the points are oriented anticlockwise

int Get_Orientation (Point point_p, Point point_q, Point point_r) {

    int delta = ( point_q.y - point_p.y ) * ( point_r.x - point_q.x ) -
                ( point_q.x - point_p.x ) * ( point_r.y - point_q.y );

    if (delta == 0)
        return 0;

    return ( delta > 0 ) ? 1 : 2;
}

// Check if point_r lies on the segment p-q. 
// If point_r lies on line p-q, then the x-coordinate of point_r should be between the x-coordinates of
// point_p and point_q and the y-coordinate of point_r should be between the y-coordinates of point_p and
// point_q.

bool Check_On_Segment (Point point_p, Point point_q, Point point_r) {

    if ( point_r.x <= std :: max (point_p.x, point_q.x) && point_r.x >= std :: min (point_p.x, point_q.x) &&
         point_r.y <= std :: max (point_p.y, point_q.y) && point_r.y >= std :: min (point_p.y, point_q.y) ) {
         return true;
    }
    return false;
}

// Return true if line segment at point (p1, q1) intersect with line segment at point (p2, q2)
bool Intersect (Point point_p1, Point point_q1, Point point_p2, Point point_q2) {

    int or_1 = Get_Orientation (point_p1, point_q1, point_p2);
    int or_2 = Get_Orientation (point_p1, point_q1, point_q2);
    int or_3 = Get_Orientation (point_p2, point_q2, point_p1);
    int or_4 = Get_Orientation (point_p2, point_q2, point_q1);

    // General case : Points are non-collinear.
    if (or_1 != or_2 && or_3 != or_4)
        return true;

    // Special case : Points are collinear.

    // If points p1, q1 and p2 are collinear, check if point p2 lies on segment p1-q1
    if (or_1 == 0 && Check_On_Segment (point_p1, point_q1, point_p2))
        return true;

    // If points p1, q1 and q2 are collinear, check if point q2 lies on segment p1_q1
    if (or_2 == 0 && Check_On_Segment (point_p1, point_q1, point_q2))
        return true;

    // If points p2, q2 and p1 are collinear, check if point p1 lies on segment p2_q2
    if (or_3 == 0 && Check_On_Segment (point_p2, point_q2, point_p1))
        return true;

    // If points p2, q2 and q1 are collinear, check if point q1 lies on segment p2_q2
    if (or_4 == 0 && Check_On_Segment (point_p2, point_q2, point_q1))
        return true;

    return false;
}

int main() {

    // Segment 1 (p1--q1)
    std :: vector<Point> vec_p1 = { Point(1,1), Point(1,1), Point(1,2), Point(5,2), Point(4,1) };
    std :: vector<Point> vec_q1 = { Point(4,4), Point(4,4), Point(3,4), Point(7,4), Point(6,3) };
    
    // Segment 2 (p2--q2)
    std :: vector<Point> vec_p2 = { Point(2,2), Point(3,1), Point(1,4), Point(6,5), Point(6,5) };
    std :: vector<Point> vec_q2 = { Point(5,5), Point(6,4), Point(3,1), Point(8,3), Point(8,3) };

    for (int i=0; i<vec_p1.size(); i++) {
        if ( Intersect(vec_p1[i], vec_q1[i], vec_p2[i], vec_q2[i]) ) {
             std :: cout << "Line p1 (" << vec_p1[i].x << "," << vec_p1[i].y << ") q1 (" << vec_q1[i].x << "," << vec_q1[i].y << ")" \
             " --- Line p2 (" << vec_p2[i].x << "," << vec_p2[i].y << ") q2 (" << vec_q2[i].x << "," << vec_q2[i].y << ") intersect" << std :: endl;
        } else {
             std :: cout << "Line p1 (" << vec_p1[i].x << "," << vec_p1[i].y << ") q1 (" << vec_q1[i].x << "," << vec_q1[i].y << ")" \
             " --- Line p2 (" << vec_p2[i].x << "," << vec_p2[i].y << ") q2 (" << vec_q2[i].x << "," << vec_q2[i].y << ") don't intersect" << std :: endl;
        }
    }
    return 0;
}

Line p1 (1,1) q1 (4,4) --- Line p2 (2,2) q2 (5,5) intersect
Line p1 (1,1) q1 (4,4) --- Line p2 (3,1) q2 (6,4) don't intersect
Line p1 (1,2) q1 (3,4) --- Line p2 (1,4) q2 (3,1) intersect
Line p1 (5,2) q1 (7,4) --- Line p2 (6,5) q2 (8,3) intersect
Line p1 (4,1) q1 (6,3) --- Line p2 (6,5) q2 (8,3) don't intersect

import java.util.Arrays;
import java.util.List;

class LineSegment {

    static class Point {

        Point (int arg_x, int arg_y) {
            x = arg_x;
            y = arg_y;
        }
        int x;
        int y;
    }

    // Fetch the orientation of triplet (p, q and r).
    // Return 0, If the points p, q and r are collinear.
    // Return 1, if the points are oriented clockwise.
    // Return 2, if the points are oriented anticlockwise

    int Get_Orientation (Point point_p, Point point_q, Point point_r) {

        int delta = ( point_q.y - point_p.y ) * ( point_r.x - point_q.x ) -
                    ( point_q.x - point_p.x ) * ( point_r.y - point_q.y );

        if (delta == 0)
            return 0;

        return ( delta > 0 ) ? 1 : 2;
    }

    // Check if point_r lies on the segment p-q. 
    // If point_r lies on line p-q, then the x-coordinate of point_r should be between the x-coordinates of
    // point_p and point_q and the y-coordinate of point_r should be between the y-coordinates of point_p and
    // point_q.

    boolean Check_On_Segment (Point point_p, Point point_q, Point point_r) {

        if ( point_r.x <=  Math.max (point_p.x, point_q.x) && point_r.x >=  Math.min (point_p.x, point_q.x) &&
             point_r.y <=  Math.max (point_p.y, point_q.y) && point_r.y >=  Math.min (point_p.y, point_q.y) ) {
             return true;
        }
        return false;
    }

    // Return true if line segment at point (p1, q1) intersect with line segment at point (p2, q2)
    boolean Intersect (Point point_p1, Point point_q1, Point point_p2, Point point_q2) {

        int or_1 = Get_Orientation (point_p1, point_q1, point_p2);
        int or_2 = Get_Orientation (point_p1, point_q1, point_q2);
        int or_3 = Get_Orientation (point_p2, point_q2, point_p1);
        int or_4 = Get_Orientation (point_p2, point_q2, point_q1);

        // General case : Points are non-collinear.
        if (or_1 != or_2 && or_3 != or_4)
            return true;

        // Special case : Points are collinear.

        // If points p1, q1 and p2 are collinear, check if point p2 lies on segment p1-q1
        if (or_1 == 0 && Check_On_Segment (point_p1, point_q1, point_p2))
            return true;

        // If points p1, q1 and q2 are collinear, check if point q2 lies on segment p1_q1
        if (or_2 == 0 && Check_On_Segment (point_p1, point_q1, point_q2))
            return true;

        // If points p2, q2 and p1 are collinear, check if point p1 lies on segment p2_q2
        if (or_3 == 0 && Check_On_Segment (point_p2, point_q2, point_p1))
            return true;

        // If points p2, q2 and q1 are collinear, check if point q1 lies on segment p2_q2
        if (or_4 == 0 && Check_On_Segment (point_p2, point_q2, point_q1))
            return true;

        return false;
    }

    public static void main (String [] args) {

         // Segment 1 (p1--q1)
         List<Point> list_p1 = Arrays.asList(new Point(1,1), new Point(1,1), new Point(1,2), new Point(5,2), new Point(4,1));
         List<Point> list_q1 = Arrays.asList(new Point(4,4), new Point(4,4), new Point(3,4), new Point(7,4), new Point(6,3));

         // Segment 2 (p2--q2)
         List<Point> list_p2 = Arrays.asList(new Point(2,2), new Point(3,1), new Point(1,4), new Point(6,5), new Point(6,5));
         List<Point> list_q2 = Arrays.asList(new Point(5,5), new Point(6,4), new Point(3,1), new Point(8,3), new Point(8,3));

         LineSegment obj = new LineSegment();
         for (int i=0; i<list_p1.size(); i++) {

             if ( obj.Intersect (list_p1.get(i), list_q1.get(i), list_p2.get(i), list_q2.get(i)) ) {
                   System.out.println( "Line p1 (" + list_p1.get(i).x + "," + list_p1.get(i).y + ") q1 (" + list_q1.get(i).x + "," + list_q1.get(i).y + ") --- Line p2 (" + list_p2.get(i).x + "," + list_p2.get(i).y + ") q2 (" + list_q2.get(i).x + "," + list_q2.get(i).y + ") intersect");
             } else {
                   System.out.println( "Line p1 (" + list_p1.get(i).x + "," + list_p1.get(i).y + ") q1 (" + list_q1.get(i).x + "," + list_q1.get(i).y + ") --- Line p2 (" + list_p2.get(i).x + "," + list_p2.get(i).y + ") q2 (" + list_q2.get(i).x + "," + list_q2.get(i).y + ") don't intersect");
             }
         }
    }
}

Line p1 (1,1) q1 (4,4) --- Line p2 (2,2) q2 (5,5) intersect
Line p1 (1,1) q1 (4,4) --- Line p2 (3,1) q2 (6,4) don't intersect
Line p1 (1,2) q1 (3,4) --- Line p2 (1,4) q2 (3,1) intersect
Line p1 (5,2) q1 (7,4) --- Line p2 (6,5) q2 (8,3) intersect
Line p1 (4,1) q1 (6,3) --- Line p2 (6,5) q2 (8,3) don't intersect