作者：非妃是公主
专栏：《笔记》《C++》
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩
判断两条直线是否相交，通过快速排斥实验和跨立实验进行判断。
快速排斥实验，主要原理：
如果l1.x的最小值比l2.x的最大值还要大，肯定没有交点
如果l1.y的最小值比l2.y的最大值还要大，肯定没有交点
反之如下：交换l1和l2的位置
如果l2.x的最小值比l1.x的最大值还要大，肯定没有交点
如果l2.y的最小值比l1.y的最大值还要大，肯定没有交点
跨立实验原理，主要原理：
进行叉积运算，向量AC×向量AB，向量AD×向量AB，如果两个向量（AC，AD）都排在两边，那么两个结果则分别指向纸内和纸外，这样，将上面叉积的结果进行点积运算，就可以得到一个负值。
当最终点积等于0的时候，说明两条重合，这时也符合条件（由于通过了第一步的快速排斥实验）
交换两条直线，同理。
综上，最终点积大于0的情况为两条直线不相交的情况
// An highlighted block
#include<iostream>
using namespace std;
struct Line {
double x1;
double y1;
double x2;
double y2;
};
// 快速排斥实验 Rapid rejection experiments
bool RapidRejExper(Line& l1, Line& l2) {
if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) ||
(l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) ||
(l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) ||
(l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)) {
return false;
}
return true;
}
// 跨立实验
bool Cross(Line& l1, Line& l2) {
if ((((l1.x1 - l2.x1) * (l2.y2 - l2.y1) - (l1.y1 - l2.y1) * (l2.x2 - l2.x1)) *
((l1.x2 - l2.x1) * (l2.y2 - l2.y1) - (l1.y2 - l2.y1) * (l2.x2 - l2.x1))) > 0 ||
(((l2.x1 - l1.x1) * (l1.y2 - l1.y1) - (l2.y1 - l1.y1) * (l1.x2 - l1.x1)) *
((l2.x2 - l1.x1) * (l1.y2 - l1.y1) - (l2.y2 - l1.y1) * (l1.x2 - l1.x1))) > 0)
{
return false;
}
return true;
}
int main() {
Line l1, l2;
cin >> l1.x1 >> l1.y1 >> l1.x2 >> l1.y2;
cin >> l2.x1 >> l2.y1 >> l2.x2 >> l2.y2;
if (RapidRejExper(l1, l2) && Cross(l1, l2)) {
cout << "Yes";
}
else {
cout << "No";
}
}
针对评论区老哥”时光3″问题的解答
这个了解了，不过还是得到的结果和你列的不一样，能把你一步一步叉乘乘以叉乘展开得到这个结果的过程列一下吗？
另外，感觉判断两个点在一个边的两边，把四个点的坐标都用到了，算一次就可以了，再算这个边是不是在另一个边的两边是重复计算呀。
主要解答为什么要对称计算两条直线的问题。推理过程很简单，大概就是我上面列的式子的坐标形式了。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130558.html
