给定两条线段 （p1，q1） 和 （p2，q2）， 找出给定的线段是否相互相交。 在讨论解决方案之前，让我们先定义 方向 .平面中有序三元组点的方向可以是 –逆时针 -顺时针 –共线
null
下图显示了不同的可能方向( A. , B , C )
![图片[1]-如何检查两条给定线段是否相交？-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_linesegments.png)
定位在这里有什么用处？ 两部分 （p1，q1） 和 （p2，q2） 当且仅当下列两个条件之一得到验证时相交
1. 一般情况： – ( p1 , q1 , p2 )及( p1 , q1 , 问题2 )有不同的方向和 – ( p2 , 问题2 , p1 )及( p2 , 问题2 , q1 )有不同的方向。
例如：
![图片[2]-如何检查两条给定线段是否相交？-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_linesegments1.png)
2. 特例 – ( p1 , q1 , p2 ), ( p1 , q1 , 问题2 ), ( p2 , 问题2 , p1 )，及( p2 , 问题2 , q1 )都是共线的 ——x射线投影( p1 , q1 )及( p2 , 问题2 )相交 –的y-投影( p1 , q1 )及( p2 , 问题2 )相交
例如：
![图片[3]-如何检查两条给定线段是否相交？-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_linesegments2.png)
以下是基于上述思想的实现。
C++
// A C++ program to check if two given line segments intersect #include <iostream> using namespace std; struct Point { int x; int y; }; // Given three collinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise int orientation(Point p, Point q, Point r) { // for details of below formula. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // collinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Driver program to test above functions int main() { struct Point p1 = {1, 1}, q1 = {10, 1}; struct Point p2 = {1, 2}, q2 = {10, 2}; doIntersect(p1, q1, p2, q2)? cout << "Yes" : cout << "No" ; p1 = {10, 0}, q1 = {0, 10}; p2 = {0, 0}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes" : cout << "No" ; p1 = {-5, -5}, q1 = {0, 0}; p2 = {1, 1}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes" : cout << "No" ; return 0; } |
JAVA
// Java program to check if two given line segments intersect class GFG { static class Point { int x; int y; public Point( int x, int y) { this .x = x; this .y = y; } }; // Given three collinear points p, q, r, the function checks if // point q lies on line segment 'pr' static boolean onSegment(Point p, Point q, Point r) { if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise static int orientation(Point p, Point q, Point r) { // for details of below formula. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0 ) return 0 ; // collinear return (val > 0 )? 1 : 2 ; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. static boolean doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Driver code public static void main(String[] args) { Point p1 = new Point( 1 , 1 ); Point q1 = new Point( 10 , 1 ); Point p2 = new Point( 1 , 2 ); Point q2 = new Point( 10 , 2 ); if (doIntersect(p1, q1, p2, q2)) System.out.println( "Yes" ); else System.out.println( "No" ); p1 = new Point( 10 , 1 ); q1 = new Point( 0 , 10 ); p2 = new Point( 0 , 0 ); q2 = new Point( 10 , 10 ); if (doIntersect(p1, q1, p2, q2)) System.out.println( "Yes" ); else System.out.println( "No" ); p1 = new Point(- 5 , - 5 ); q1 = new Point( 0 , 0 ); p2 = new Point( 1 , 1 ); q2 = new Point( 10 , 10 );; if (doIntersect(p1, q1, p2, q2)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Princi Singh |
Python3
# A Python3 program to find if 2 given line segments intersect or not class Point: def __init__( self , x, y): self .x = x self .y = y # Given three collinear points p, q, r, the function checks if # point q lies on line segment 'pr' 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): # to find the orientation of an ordered triplet (p,q,r) # function returns the following values: # 0 : Collinear points # 1 : Clockwise points # 2 : Counterclockwise # for details of below formula. val = ( float (q.y - p.y) * (r.x - q.x)) - ( float (q.x - p.x) * (r.y - q.y)) if (val > 0 ): # Clockwise orientation return 1 elif (val < 0 ): # Counterclockwise orientation return 2 else : # Collinear orientation return 0 # The main function that returns true if # the line segment 'p1q1' and 'p2q2' intersect. def doIntersect(p1,q1,p2,q2): # Find the 4 orientations required for # the general and special cases o1 = orientation(p1, q1, p2) o2 = orientation(p1, q1, q2) o3 = orientation(p2, q2, p1) o4 = orientation(p2, q2, q1) # General case if ((o1 ! = o2) and (o3 ! = o4)): return True # Special Cases # p1 , q1 and p2 are collinear and p2 lies on segment p1q1 if ((o1 = = 0 ) and onSegment(p1, p2, q1)): return True # p1 , q1 and q2 are collinear and q2 lies on segment p1q1 if ((o2 = = 0 ) and onSegment(p1, q2, q1)): return True # p2 , q2 and p1 are collinear and p1 lies on segment p2q2 if ((o3 = = 0 ) and onSegment(p2, p1, q2)): return True # p2 , q2 and q1 are collinear and q1 lies on segment p2q2 if ((o4 = = 0 ) and onSegment(p2, q1, q2)): return True # If none of the cases return False # Driver program to test above functions: 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" ) # This code is contributed by Ansh Riyal |
C#
// C# program to check if two given line segments intersect using System; using System.Collections.Generic; class GFG { public class Point { public int x; public int y; public Point( int x, int y) { this .x = x; this .y = y; } }; // Given three collinear points p, q, r, the function checks if // point q lies on line segment 'pr' static Boolean onSegment(Point p, Point q, Point r) { if (q.x <= Math.Max(p.x, r.x) && q.x >= Math.Min(p.x, r.x) && q.y <= Math.Max(p.y, r.y) && q.y >= Math.Min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise static int orientation(Point p, Point q, Point r) { // for details of below formula. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // collinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. static Boolean doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Driver code public static void Main(String[] args) { Point p1 = new Point(1, 1); Point q1 = new Point(10, 1); Point p2 = new Point(1, 2); Point q2 = new Point(10, 2); if (doIntersect(p1, q1, p2, q2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); p1 = new Point(10, 1); q1 = new Point(0, 10); p2 = new Point(0, 0); q2 = new Point(10, 10); if (doIntersect(p1, q1, p2, q2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); p1 = new Point(-5, -5); q1 = new Point(0, 0); p2 = new Point(1, 1); q2 = new Point(10, 10);; if (doIntersect(p1, q1, p2, q2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to check if two given line segments intersect class Point { constructor(x, y) { this .x = x; this .y = y; } } // Given three collinear points p, q, r, the function checks if // point q lies on line segment 'pr' function onSegment(p, q, r) { if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) return true ; return false ; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are collinear // 1 --> Clockwise // 2 --> Counterclockwise function orientation(p, q, r) { // for details of below formula. let val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // collinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. function doIntersect(p1, q1, p2, q2) { // Find the four orientations needed for general and // special cases let o1 = orientation(p1, q1, p2); let o2 = orientation(p1, q1, q2); let o3 = orientation(p2, q2, p1); let o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true ; // Special Cases // p1, q1 and p2 are collinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true ; // p1, q1 and q2 are collinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true ; // p2, q2 and p1 are collinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true ; // p2, q2 and q1 are collinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true ; return false ; // Doesn't fall in any of the above cases } // Driver code let p1 = new Point(1, 1); let q1 = new Point(10, 1); let p2 = new Point(1, 2); let q2 = new Point(10, 2); if (doIntersect(p1, q1, p2, q2)) document.write( "Yes<br>" ); else document.write( "No<br>" ); p1 = new Point(10, 1); q1 = new Point(0, 10); p2 = new Point(0, 0); q2 = new Point(10, 10); if (doIntersect(p1, q1, p2, q2)) document.write( "Yes<br>" ); else document.write( "No<br>" ); p1 = new Point(-5, -5); q1 = new Point(0, 0); p2 = new Point(1, 1); q2 = new Point(10, 10);; if (doIntersect(p1, q1, p2, q2)) document.write( "Yes<br>" ); else document.write( "No<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
NoYesNo
时间复杂性： O（1）
资料来源： http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1。pdf 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
