How to check if two given line segments intersect ? | A Python3 program to find if 2 given line segments intersect or not ; Given three colinear points p , q , r , the function checks if point q lies on line segment ' pr ' ; to find the orientation of an ordered triplet ( p , q , r ) function returns the following values : 0 : Colinear points 1 : Clockwise points 2 : Counterclockwise See https : www . geeksforgeeks . org / orientation - 3 - ordered - points / amp / for details of below formula . ; Counterclockwise orientation ; The main function that returns true if the line segment ' p1q1' and ' p2q2' intersect . ; Find the 4 orientations required for the general and special cases ; General case ; Special Cases p1 , q1 and p2 are colinear and p2 lies on segment p1q1 ; p1 , q1 and q2 are colinear and q2 lies on segment p1q1 ; p2 , q2 and p1 are colinear and p1 lies on segment p2q2 ; p2 , q2 and q1 are colinear and q1 lies on segment p2q2 ; If none of the cases ; Driver program to test above functions :
class Point : NEW_LINE INDENT def __init__ ( self , x , y ) : NEW_LINE INDENT self . x = x NEW_LINE self . y = y NEW_LINE DEDENT DEDENT def onSegment ( p , q , r ) : NEW_LINE INDENT 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 ) ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def orientation ( p , q , r ) : NEW_LINE INDENT val = ( float ( q . y - p . y ) * ( r . x - q . x ) ) - ( float ( q . x - p . x ) * ( r . y - q . y ) ) NEW_LINE if ( val > 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT elif ( val < 0 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT def doIntersect ( p1 , q1 , p2 , q2 ) : NEW_LINE INDENT o1 = orientation ( p1 , q1 , p2 ) NEW_LINE o2 = orientation ( p1 , q1 , q2 ) NEW_LINE o3 = orientation ( p2 , q2 , p1 ) NEW_LINE o4 = orientation ( p2 , q2 , q1 ) NEW_LINE if ( ( o1 != o2 ) and ( o3 != o4 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( ( o1 == 0 ) and onSegment ( p1 , p2 , q1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( ( o2 == 0 ) and onSegment ( p1 , q2 , q1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( ( o3 == 0 ) and onSegment ( p2 , p1 , q2 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( ( o4 == 0 ) and onSegment ( p2 , q1 , q2 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT p1 = Point ( 1 , 1 ) NEW_LINE q1 = Point ( 10 , 1 ) NEW_LINE p2 = Point ( 1 , 2 ) NEW_LINE q2 = Point ( 10 , 2 ) NEW_LINE if doIntersect ( p1 , q1 , p2 , q2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT p1 = Point ( 10 , 0 ) NEW_LINE q1 = Point ( 0 , 10 ) NEW_LINE p2 = Point ( 0 , 0 ) NEW_LINE q2 = Point ( 10 , 10 ) NEW_LINE if doIntersect ( p1 , q1 , p2 , q2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT p1 = Point ( - 5 , - 5 ) NEW_LINE q1 = Point ( 0 , 0 ) NEW_LINE p2 = Point ( 1 , 1 ) NEW_LINE q2 = Point ( 10 , 10 ) NEW_LINE if doIntersect ( p1 , q1 , p2 , q2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT