2つの線分が交差しているかどうかを確認します

2つの線分を指定します。最初の線分からの点p1、p2、および2番目の線分からのq1、q2。両方の線分が交差しているかどうかを確認する必要があります。

これらのケースが満たされると、両方の線分が交差していると言えます。

• （p1、p2、q1）と（p1、p2、q2）の向きが異なる場合
• （q1、q2、p1）と（q1、q2、p2）の向きは異なります。

別の条件は、（p1、p2、q1）、（p1、p2、q2）、（q1、q2、p1）、（q1、q2、p2）が同一線上にある場合です。

入力と出力

Input:
Points of two line-segments
Line-segment 1: (0, 0) to (5, 5)
Line-segment 2: (2, -10) to (3, 10)
Output:
Lines are intersecting

アルゴリズム

direction（a、b、c）

入力： 3つのポイント。

出力： それらが同一線上にあるか、反時計回りまたは時計回りの方向であるかを確認してください。

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 anti-clockwise
   return clockwise
End

isIntersect（l1、l2）

入力： 2つの線分。各線には2つの点p1とp2があります。

出力： 確かに、それらが交差しているとき。

Begin
   dir1 = direction(l1.p1, l1.p2, l2.p1);
   dir2 = direction(l1.p1, l1.p2, l2.p2);
   dir3 = direction(l2.p1, l2.p2, l1.p1);
   dir4 = direction(l2.p1, l2.p2, l1.p2);

   if dir1 ≠ dir2 and dir3 ≠ dir4, then
      return true
   if dir1 =0 and l2.p1 on the line l1, then
      return true
   if dir2 = 0 and l2.p2 on the line l1, then
      return true
   if dir3 = 0 and l1.p1 on the line l2, then
      return true
   if dir4 = 0 and l1.p2 on the line l2, then
      return true
   return false
End

例

#include<iostream>
using namespace std;

struct Point {
   int x, y;
};

struct line {
   Point p1, p2;
};

bool onLine(line l1, Point p) {   //check whether p is on the line or not
   if(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)))
      return 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;     //colinear
   else if(val < 0)
      return 2;    //anti-clockwise direction
      return 1;    //clockwise direction
}

bool isIntersect(line l1, line l2) {
   //four direction for two lines and points of other line
   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)
      return true; //they are intersecting

   if(dir1==0 && onLine(l1, l2.p1)) //when p2 of line2 are on the line1
      return true;

   if(dir2==0 && onLine(l1, l2.p2)) //when p1 of line2 are on the line1
      return true;

   if(dir3==0 && onLine(l2, l1.p1)) //when p2 of line1 are on the line2
      return true;

   if(dir4==0 && onLine(l2, l1.p2)) //when p1 of line1 are on the line2
      return true;
         
   return false;
}

int main() {
   line l1 = {{0,0}, {5, 5}};
   line l2 = {{2,-10}, {3, 10}};
   
   if(isIntersect(l1, l2))
      cout << "Lines are intersecting";
   else
      cout << "Lines are not intersecting";
}

出力

Lines are intersecting