检查两个线段是否相交
给出两个线段。来自第一线段的点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
EndisIntersect(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