Kiểm tra xem hai đoạn thẳng có giao nhau không

Cho hai đoạn thẳng. Các điểm p1, p2 cách đoạn thẳng thứ nhất và q1, q2 cách đoạn thẳng thứ hai. Chúng tôi phải kiểm tra xem cả hai đoạn thẳng có giao nhau hay không.

Chúng ta có thể nói rằng cả hai đoạn thẳng đều giao nhau khi thỏa mãn các trường hợp sau:

Khi (p1, p2, q1) và (p1, p2, q2) có hướng khác và
(q1, q2, p1) và (q1, q2, p2) có hướng khác.

Có một điều kiện khác là khi (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) thẳng hàng.

Đầu vào và Đầu ra

 Đầu vào:Các điểm của hai đoạn thẳng Đoạn thẳng 1:(0, 0) đến (5, 5) Đoạn thẳng 2:(2, -10) đến (3, 10) Đầu ra:Các đường giao nhau   Thuật toán 
 
  hướng (a, b, c)  
 
  Đầu vào: Ba điểm. 
 
  Đầu ra: Kiểm tra xem chúng có thẳng hàng hay ngược chiều kim đồng hồ hay chiều kim đồng hồ hay không. 
  Begin val:=(b.y-a.y) * (c.x-b.x) - (b.x-a.x) * (c.y-b.y) if val =0, then return collinear else if val <0, then return back Ngược chiều kim đồng hồ theo chiều kim đồng hồEnd 
 
  isIntersect (l1, l2)  
 
  Đầu vào: Hai đoạn thẳng, mỗi đoạn thẳng có hai điểm p1 và p2. 
 
  Đầu ra: Đúng, khi chúng giao nhau. 
  Begin dir1 =direction (l1.p1, l1.p2, l2.p1); dir2 =hướng (l1.p1, l1.p2, l2.p2); dir3 =hướng (l2.p1, l2.p2, l1.p1); dir4 =hướng (l2.p1, l2.p2, l1.p2); nếu dir1 ≠ dir2 và dir3 ≠ dir4 thì trả về true nếu dir1 =0 và l2.p1 trên dòng l1, sau đó trả về true nếu dir2 =0 và l2.p2 trên dòng l1, sau đó trả về true nếu dir3 =0 và l1 .p1 trên dòng l2, sau đó trả về true nếu dir4 =0 và l1.p2 trên dòng l2, sau đó trả về true trả về falseEnd 
  Ví dụ 
  #include  using namespace std; struct Point {int x, y;}; struct line {Point p1, p2;}; bool onLine (line l1, Point p) {// kiểm tra xem p có nằm trên dòng hoặc không nếu (p.x <=max (l1.p1.x, l1.p2.x) &&p.x <=min (l1.p1.x, l1.p2.x) &&(p.y <=max (l1.p1 .y, l1.p2.y) &&p.y <=min (l1.p1.y, l1.p2.y))) trả về true; return false;} int direction (Point a, Point b, Point c) {int val =(b.y-a.y) * (c.x-b.x) - (b.x-a.x) * (c.y-b.y); if (val ==0) return 0; // cột khác if (val <0) return 2; // ngược chiều kim đồng hồ return 1; // hướng theo chiều kim đồng hồ} bool isIntersect (line l1, line l2) {// bốn hướng cho hai dòng và điểm của dòng khác int dir1 =direction (l1.p1, l1.p2, l2.p1); int dir2 =direction (l1.p1, l1.p2, l2.p2); int dir3 =direction (l2.p1, l2.p2, l1.p1); int dir4 =direction (l2.p1, l2.p2, l1.p2); if (dir1! =dir2 &&dir3! =dir4) trả về true; // chúng giao nhau if (dir1 ==0 &&onLine (l1, l2.p1)) // khi p2 của line2 nằm trên line1 return true; if (dir2 ==0 &&onLine (l1, l2.p2)) // khi p1 của line2 nằm trên line1 trả về true; if (dir3 ==0 &&onLine (l2, l1.p1)) // khi p2 của line1 nằm trên line2 trả về true; if (dir4 ==0 &&onLine (l2, l1.p2)) // khi p1 của line1 nằm trên line2 trả về true; return false;} int main () {dòng l1 ={{0,0}, {5, 5}}; dòng l2 ={{2, -10}, {3, 10}}; if (isIntersect (l1, l2)) cout <<"Các đường thẳng cắt nhau"; else cout <<"Các đường không giao nhau";} 
  Đầu ra 
  Các đường giao nhau