计算几何之判断两线段是否相交代码模板与证明

素颜马尾好姑娘i 2022-11-06 00:50 207阅读 0赞

### 判断两线段是否相交 ###

已知两线段 a 1 a 2 a\_1a\_2 a1a2和 b 1 b 2 b\_1b\_2 b1b2，判断是否相交

#### 代码模板 ####

bool segment_intersection(Point a1,Point a2,Point b1,Point b2)
    { 
    	double c1 = cross(a2 - a1,b1 - a1), c2 = cross(a2 - a1,b2 - a1);
    	double c3 = cross(b2 - b1,a2 - b1), c4 = cross(b2 - b1,a1 - b1);
    	return (c1 * c2 <= 0 && c3 * c4 <= 0);
    }

#### 证明 ####

有两条线段 a 1 a 2 a\_1a\_2 a1a2和 b 1 b 2 b\_1b\_2 b1b2，我们只需先证明 a 1 a\_1 a1和 a 2 a\_2 a2分别在 b 1 b 2 b\_1b\_2 b1b2的两侧，然后证明 b 1 b\_1 b1和 b 2 b\_2 b2分别在 a 1 a 2 a\_1a\_2 a1a2，当两个**同时满足时**，两线段一定相交。

然后关键就是如何判断两点在线段两侧，如下图：

![eg][]  
如图有 v ⃗ 1 、 v ⃗ 2 、 v ⃗ 3 \\vec v\_1、 \\vec v\_2 、\\vec v\_3 v1、v2、v3三个向量， v ⃗ 1 \\vec v\_1 v1与 v ⃗ 2 \\vec v\_2 v2的叉积对应的角度是 θ 1 \\theta\_1 θ1，同理， v ⃗ 1 \\vec v\_1 v1与 v ⃗ 3 \\vec v\_3 v3的叉积对应的角度是 θ 2 \\theta\_2 θ2，这两个角度的sin值符号一定是相反的，因此如果 v ⃗ 1 \\vec v\_1 v1与 v ⃗ 2 \\vec v\_2 v2的叉积和 v ⃗ 1 \\vec v\_1 v1与 v ⃗ 3 \\vec v\_3 v3的叉积相乘，得到的答案小于等于零就说明位于两侧，否则就是同侧。注意这里的等于0说明有一个端点在另一条直线上，这个也算相交，所以说小于等于零。

[eg]: /images/20221023/49d1ae70bfd44417a94acd43e5755a77.png

发表评论取消回复

表情：

评论列表（有 0 条评论，207人围观）

还没有评论，来说两句吧...

相关阅读

相关 nod1264 线段相交（计算几何）

1264 线段相交基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注给出平面上两条线段的两个端点，判断这两条线段是否相交（有一

迈不过友情╰/ 2024年02月17日 23:17/ 0 赞/ 69 阅读

相关计算几何之旋转卡壳代码模板与证明

旋转卡壳旋转卡壳这个算法很形象，一般用来在 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度下求最远点对问题，就是求平面中任意两点的最远距

以你之姓@/ 2022年11月10日 14:19/ 0 赞/ 225 阅读

相关计算几何之判断两线段是否相交代码模板与证明

判断两线段是否相交已知两线段 a 1 a 2 a\_1a\_2 a1a2和 b 1 b 2 b\_1b\_2 b1b2，判断是否相交代码模板

素颜马尾好姑娘i/ 2022年11月06日 00:50/ 0 赞/ 208 阅读

相关计算几何之点到直线的距离&点到线段的距离代码模板与证明

点到直线的距离已知直线上两点a、b，和直线外一点p，求p到直线ab的距离。代码模板 double distance_line(Point p,Poin

深碍√TFBOYSˉ_/ 2022年11月05日 12:55/ 0 赞/ 351 阅读

相关计算几何之判断两直线是否相交并求两直线交点代码模板与证明

判断两直线是否相交并求两直线交点首先判断两直线的向量 v ⃗ \\vec v v与 w ⃗ \\vec w w的叉积是否为0，若为0说明两向量作为邻边构成的平行四边

港控/mmm°/ 2022年11月05日 10:59/ 0 赞/ 217 阅读

相关判断两个线段相交

http://www.cnblogs.com/zhangchaoyang/articles/2668562.html

╰+哭是因爲堅強的太久メ/ 2022年08月14日 03:46/ 0 赞/ 319 阅读

相关判断两个线段是否相交

已知线段AB，线段CD. 先来判断直线AB与线段CD是否相交，如果不相交，那么线段AB和线段CD肯定不相交。如果直线AB和线段CD已经相交，那么继续判断直线CD与线

末蓝、/ 2022年08月02日 06:04/ 0 赞/ 209 阅读

相关 pku 1556 The Doors 计算几何之叉积判断线段是否相交

这是黑书上的一道题目, 以前很少刷计算几何的题, 算是一个开端吧. \include <iostream> \include <cmath> using namespace

浅浅的花香味﹌/ 2022年07月12日 10:14/ 0 赞/ 423 阅读

相关计算几何-判断两条线段是否相交模板

给定两个点: typedef struct \{ double x, y; \} Point; Point A1,A2,B1,B2; 首先引入两个实验： a

我不是女神ヾ/ 2022年05月15日 08:37/ 0 赞/ 324 阅读

相关 51Nod 1264：线段相交（计算几何）

51Nod 1264：线段相交 Decision 给出平面上两条线段的两个端点，判断这两条线段是否相交（有一个公共点或有部分重合认为相交）。如果相交，输出"Yes

痛定思痛。/ 2021年12月21日 03:35/ 0 赞/ 261 阅读