计算几何--线段求交

线段求交

问题描述：已知两条线段$P_1P_2$P1​P2​和$Q_1Q_2$Q1​Q2​，判断$P_1P_2$P1​P2​和$Q_1Q_2$Q1​Q2​是否相交，若相交，求出交点。

两条线段的位置关系可以分为三类：有重合部分、无重合部分但有交点、无交点。

方法一

step1：快速排斥实验

设以线段$P_1P_2$P1​P2​为对角线的矩形为R，设以线段$Q_1Q_2$Q1​Q2​为对角线的矩形为T，如果R和T不相交，则两线段不相交。

step2：跨立实验

如果两线段相交，则两线段必然相互跨立对方。

若P$P_1P_2$P1​P2​跨立$Q_1Q_2$Q1​Q2​，则矢量$(P_1-Q_1)$(P1​−Q1​)和$(P_2-Q_1)$(P2​−Q1​)位于矢量$(Q_2-Q_1)$(Q2​−Q1​)的两侧，即$( P_1 - Q_1 ) × ( Q_2 - Q_1 ) * ( P_2 - Q_1 ) × ( Q_2 - Q_1 ) < 0。$(P1​−Q1​)×(Q2​−Q1​)∗(P2​−Q1​)×(Q2​−Q1​)<0。

若$Q_1Q_2$Q1​Q2​跨立$P_1P_2$P1​P2​，则矢量$(Q_1-P_1)$(Q1​−P1​)和$(Q_2-P_1)$(Q2​−P1​)位于矢量$(P_2-P_1)$(P2​−P1​)的两侧，即$( Q_1 - P_1 ) × ( P_2 - P_1 ) * ( Q_2 - P_1 ) × ( P_2 - P_1 ) < 0。$(Q1​−P1​)×(P2​−P1​)∗(Q2​−P1​)×(P2​−P1​)<0。

排斥实验和跨立实验的示例如下图所示。

step3：列方程求解

当判定两条线段相交后，可以进行交点的求解，求交点可以用平面几何方法，列点斜式方程来完成。但由于点斜式方程难以处理斜率为0的特殊情况，不方便求解。因而，参用向量法求解交点。

方法二：

先求出直线交点，然后判断交点在不在两线段上

设这两个线段的端点分别为$a、b 和c、d. L_{ab}和L_{cd}$a、b和c、d.Lab​和Lcd​为两个线段所在的直线。计算交点的一种常用方法是同时求解 L_(ab)和L_(cd)$的斜截方程: 2个两个未知数(交点的x和y坐标)，两个的方程。相反，我们将使用两个线段的参数表示，因为变量的意义似乎更直观。

设$A = b - a, C = d - c;$A=b−a,C=d−c; 这些向量的方向和线段的方向一致。$L_{ab}$Lab​线上的任意一点都可以表示为向量和$p(s) = a + sA$p(s)=a+sA，它将我们带到$L_{ab}$Lab​上的$a$a点，然后通过改变$s$s使$a$a沿着直线移动一段距离，如图所示。变量$s$s称为这个方程的参数。考虑$s = 0, s = 1, s = 1/2: p(0) = a, p(1) = a + A = a + b - a = b, p(1/2) = (a + b)/2$s=0,s=1,s=1/2:p(0)=a,p(1)=a+A=a+b−a=b,p(1/2)=(a+b)/2得到的值。这些例子说明，对于$s ∈ [0,1]， p(s)$s∈[0,1]，p(s)表示线段$ab$ab上的所有点，$s$s的值表示端点间距离的比值; 特别地，$s$s的极值产生端点。

我们同样可以用$q(t) = c + tC, t ∈ [0,1]$q(t)=c+tC,t∈[0,1] 来表示第二段上的点。段与段之间的交点由满足$p(s)$p(s)等于$q(t)$q(t)的 $s$s 和$t$t的值指定: $a + sA = c + tC$a+sA=c+tC。这个向量方程也由两个未知数组成:$x$x和$y$y方程，都以$s$s和$t$t为未知数。用通常的下标0和1表示$x$x和$y$y坐标，它的解是

伪代码（C++）：

这段代码至少有三个弱点：

• 该代码不能处理平行线段。大多数应用程序需要知道这些线段是否重叠。
• 许多应用程序需要区分合适的和不合适的交点，就像我们在第一章中为三角化所做的那样。在输出中区分这些是有用的。
• 虽然使用了浮点变量，但在将结果转换为双精度之前，乘法仍然使用整数运算。下面是一个简单的示例，演示了此代码如何由于溢出而失败。设这四个端点为

线段在p =(0,0)处形成一个“X”形交点。计算表明D为$-4r^2$−4r2。对于$r = 10^5$r=105，这是$-4*10^{10}$−4∗1010，它超出了32位整数的范围。在这种情况下，我的机器返回p =(-267702.8， -267702.8)作为交点!

优化代码：
我们现在解决这三个问题。首先，我们将函数返回值从bool更改为char，并让它返回一个“标志”，该标志表示找到的交集的类型。需要根据交集是否正确进行决策的应用程序可以使用此标志。