# Line Segment Intersection

Given : 2 line segments. Segment 1 ( p1, q1 ) and Segment 2 ( p2, q2 ).
( p1 and q1 ) are the end points of Segment 1, ( p2 and q2 ) are the end points of Segment 2.

Objective : To find if Segment 1 intersets with Segment 2.

Concept of orientation of ordered triplets ( points )
Consider 3 points a, b and c. These points could have the possible 3 orientations in a plane. The points could be collinear, clockwise or anticlockwise as shown below. The orientation of these ordered triplets give us the clue to deduce if 2 line segments intersect with each other or not. Condition for intersection of 2 line segments.

• General case
• Segment 1 ( p1, q1 ) and Segment 2 ( p2, q2 ) intersect
If points ( p1, q1, p2 ) and points ( p1, q1, q2 ) have different orientations.
and
If points ( p2, q2, p1 ) and points ( p2, q2, q1 ) have different orientations. • Special case ( points collinear )
• Segment 1 ( p1, q1 ) and Segment 2 ( p2, q2 ) intersect when
Points ( p1, q1, p2 ), ( p1, q1, q2 ), ( p2, q2, p1 ) and ( p2, q2, q1 ) are collinear and
- X - projections of ( p1, q1 ) intersect with segment ( p2, q2 )
and
- Y - projections of ( p1, q1 ) intersect with segment ( p2, q2 ) Computing the orientation
To find the orientation of triplet, we find the slope of two segments that are formed by the triplet.
If the line segement begins at P1 ( x1, y1 ) and ends at P2 ( x2, y2 ), then the slope of line is ( y2 - y1 ) / ( x2 - x1 ).
Similary, the slope of line segment beginning at P2 ( x2, y2 ) and ending at P3 ( x3, y3 ) the slope is ( y3 - y2 ) / ( x3 - x2 ). Example Program for checking if two line segments intersect.

``````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()
``````

Output

``````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;
}
``````

Output

``````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");
}
}
}
}
``````

Output

``````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
``````