检查两个线段是否相交

给出两个线段。来自第一线段的点p1，p2和来自第二线段的点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

算法

方向(a,b,c)

输入：三点。

输出：检查它们是否共线，逆时针或顺时针方向。

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)

输入：两个线段，每条线都有两个点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) {
   //两条线的四个方向和另一条线的点
   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