计算几何-线线相交

线线相交

几何图元中定义的线包括: 线段(LineSegment2), 圆(Circle2), 圆弧(Arc2), 直线(Line2), 射线(Ray2), 本文中的线线相交包含以下几种情况:

• line_segment_2_line_segment_2_intersection: 线段与线段相交
• line_segment_2_circle_2_intersection: 线段与圆相交
• line_segment_2_arc_2_intersection: 线段与圆弧相交
• line_segment_2_line_2_intersection: 线段与直线相交
• line_segment_2_ray_2_intersection: 线段与射线相交
• circle_2_circle_2_intersection: 圆与圆相交
• circle_2_arc_2_intersection: 圆与圆弧相交
• arc_2_arc_2_intersection: 圆弧与圆弧相交
• line_2_line_2_intersection: 直线与直线相交
• line_2_ray_2_intersection: 直线与射线相交

线段与线段相交

线段与线段相交的情况有以下几种:

• 有一个交点: 交点不是线段的端点
• 有一个交点: 交点是线段的端点
• 没有交点
• 有两个交点: 交点是线段的端点

  线段与线段 重叠(overlap) 是特殊情况, 本文中认为 overlap 相交, 交点是线段的端点

1. 初始化存储交点的数组
2. 使用叉乘判断是否相交:

$$({\overrightarrow{AB} \times \overrightarrow{AC}}) \cdot ({\overrightarrow{AB} \times \overrightarrow{AD}}) \le 0$$

• 线段AB与线段CD相交, 且交点不是线段的端点, 端点C和端点D位于线段AB两侧, 所以叉乘的结果为负数
• 线段AB与线段CD相交, 且交点是线段的端点, 叉乘的结果为 0
• 线段AB与线段CD不相交, 端点C和端点D位于线段AB同一侧, 叉乘的结果为正数
• 线段AB与线段CD重叠, 叉乘的结果为 0

3. 如果相交, 判断端点是否在另一条线段上, 如果在, 则添加到交点数组中
4. 如果交点数组不为空, 则返回交点数组, 结束
5. 如果交点数组为空, 则说明交点不是端点, 计算交点

   线段AB上的任何点可以表示为: $\vec{P} = \vec{A} + t \cdot \overrightarrow{AB} (0 \le t \le 1)$
   线段CD上的任何点可以表示为: $\vec{Q} = \vec{C} + s \cdot \overrightarrow{CD} (0 \le s \le 1)$
   两条线段相交时, 有: $\vec{P} = \vec{Q}$, 即: $\vec{A} + t \cdot \overrightarrow{AB} = \vec{C} + s \cdot \overrightarrow{CD}$, 解方程得到交点
   $\vec{A} - \vec{C} = s \cdot \overrightarrow{CD} - t \cdot \overrightarrow{AB} \leftrightarrow \overrightarrow{CA} = s \cdot \overrightarrow{CD} - t \cdot \overrightarrow{AB}$
   两边同时叉乘 $\overrightarrow{AB}$, 得到: $\overrightarrow{AB} \times \overrightarrow{CA} = s \cdot \overrightarrow{AB} \times \overrightarrow{CD}$
   所以 $s = \frac{\overrightarrow{AB} \times \overrightarrow{CA}}{\overrightarrow{AB} \times \overrightarrow{CD} }$, 代入 $\vec{Q} = \vec{C} + s \cdot \overrightarrow{CD}$, 得到交点

线段与圆相交

线段与圆相交的情况有以下几种:

• 有两个交点: 圆心到线段的距离小于半径, 线段端点都不在圆内
• 有一个交点: 圆心到线段的距离等于半径
• 有一个交点: 圆心到线段的距离小于半径, 一个端点在圆内, 一个端点在圆外
• 没有交点: 圆心到线段的距离大于半径且线段端点都在圆外,或者圆心到线段的距离小于半径, 两个端点都在圆内

1. 先判断线段的端点与圆的位置关系

   如果两个端点都在圆内, 则没有交点, 结束
   如果两个端点都在圆上, 则有两个交点, 结束

2. 如果两个端点至少有一个在圆内(必定是一个在圆内, 另一个在圆上或圆外)

   设圆内的点为 $A$, 另一个点为 $B$, 构造直线 $l$ 过 $A$ 和 $B$, $v$ = $\hat{\overrightarrow{AB}}$($\hat{A}$ 为 $A$ 的归一化)
   求圆心 $O$ 投影到 $l$ 上的点 $Q$, 毕达哥拉斯定理求交点 $P$ 与 $Q$ 的距离 $D$
   $P$ = $A + v \cdot D$

3. 两个端点至少有一个在圆外(必定是一个在圆外, 另一个在圆外或圆上)

   构造直线 $l$ 过 $A$ 和 $B$, $v$ = $\hat{\overrightarrow{AB}}$($\hat{A}$ 为 $A$ 的归一化)
   求圆心 $O$ 投影到 $l$ 上的点 $Q$, 毕达哥拉斯定理求交点 $P$ 与 $Q$ 的距离 $D$
   $P_1$ = $A + v \cdot D$, $P_2$ = $A - v \cdot D$
   如果 $P$ 在线段上, 则 $P$ 为交点

线段与圆弧相交

线段与圆弧相交的情况与圆类似, 区别在于线段与圆弧相交时, 交点可能在圆弧的起点和终点之间, 也可能在圆弧的起点和终点之外. 因此, 需要判断交点是否在圆弧上.

1. 获取线段与圆的交点
2. 判断交点是否在圆弧上

线段与直线相交

将线段构造成直线, 判断直线与直线的交点是否在线段上, 重叠情况认为有两个交点, 具体实现见下文.

线段与射线相交

将线段构造成直线, 判断直线与射线的交点是否在线段上, 重叠情况认为有两个交点, 具体实现见下文.

圆与圆相交

圆与圆相交的情况有以下几种:

• 有两个交点: 两圆的圆心距小于两圆的半径之和, 且大于两圆的半径之差
• 有一个交点: 内切或外切, 两圆的圆心距等于两圆的半径之和或之差
• 没有交点: 内含或外离, 两圆的圆心距大于两圆的半径之和或之差
• 圆心和半径相同(overlap)是特殊情况, 本文中认为 overlap 不相交

1. 计算两圆的圆心距 $d$, 两圆半径分别为 $R_1$ 和 $R_2$, 半径之和 $S$, 半径之差的绝对值 $D$
2. 如果 $d = 0$, 不相交, 结束
3. 如果 $d = S$, 外切, 有一个交点, 结束

   $\vec{v} = \overrightarrow{O_1O_2}$
   $P = O_1 + \hat{v} \cdot R_1$

4. 如果 $d = D$, 内切, 有一个交点, 结束

   如果 $R_1 > R_2$: $\vec{v} = \overrightarrow{O_1O_2}$, $P = O_2 + \hat{v} \cdot R_2$
   如果 $R_1 < R_2$: $\vec{v} = \overrightarrow{O_2O_1}$, $P = O_1 + \hat{v} \cdot R_1$

5. 如果 $d < S$ 且 $d > D$, 有两个交点, 结束

   直线 $O_1O_2$ 垂直平分 线段 $PQ$, 根据余弦定理求解 $PQ$ 的长度, 进而求解交点

6. 没有交点, 结束

圆与圆弧相交

先求圆与圆的交点, 再判断交点是否在圆弧上, 圆心和半径相同(overlap)不相加.

圆弧与圆弧相交

先求圆与圆的交点, 再判断交点是否都在两个圆弧上, 圆心和半径相同(overlap)不相加.

直线与直线相交

直线与直线相交的情况有以下几种:

• 有一个交点: 两直线相交
• 不相交: 两直线平行或重合

直线的一般方程为: $Ax + By + C = 0$, 两直线相交时, 有: $A_1x + B_1y + C_1 = 0$, $A_2x + B_2y + C_2 = 0$, 解方程得到交点.
$d$ = $A_1 \cdot B_2 - A_2 \cdot B_1$, 如果 $d$ = $0$, 两直线平行或重合, 否则有一个交点.
$x$ = $\frac{B_1 \cdot C_2 - B_2 \cdot C_1}{d}$
$y$ = $\frac{A_2 \cdot C_1 - A_1 \cdot C_2}{d}$

直线与射线相交

先求直线与直线的交点, 再判断交点是否在射线上, overlap 不相交.