数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查两条线段是否相交
假设有两条线段。第一条线段上的点为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
算法
direction(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) {
//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
更新于： 2020年6月17日
5K+ 次浏览
广告