题目描述

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

• 要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：

• 输入：
  line1 = {0, 0}, {1, 0}
  line2 = {1, 1}, {0, -1}
• 输出： {0.5, 0}

示例 2：

• 输入：
  line1 = {0, 0}, {3, 3}
  line2 = {1, 1}, {2, 2}
• 输出： {1, 1}

示例 3：

• 输入：
  line1 = {0, 0}, {1, 1}
  line2 = {1, 0}, {2, 1}
  -输出： {}，两条线段没有交点

提示：

• 坐标绝对值不会超过 2^7
• 输入的坐标均是有效的二维坐标

解题思路与代码

这道题，乍一看是不是很简单，方法就是像初高中的一道数学题。让你去判断两条直线是否具有交点？

但是呢，这道题是让你去判断两条线段是否具有交点。并且，如果有多个交点，返回最小的那一个。（在多个交点中，有且只有一个交点，它的x的值最小，那么返回这个x最小的交点。如果交点的x值都相同，则返回y值最小的交点）

不要小看线段与直线的区别，就这一点区别，让整道题的难度激增。

并且，关于直线的方程式有好多种，比如一般式方程啦，点斜式方程啦，斜截式方程啦，截距式方程啦，参数式方程啦，选择用哪一个，这也是重中之重。因为这些方程式各有优缺点。选错了，你解题的步骤又可能激增，然后等于是难上加难再加难。对就是这样。

我这边，特地的选择了一种，最好理解的方式来解决这道题。也就是使用一般式方程进行求解。这种方式最大的好处就是，写出来的代码简单易懂。

并且，这道题实际上是很偏数学的，数学不好，或者说数学与代码的结合能力差，也是根本不可能做的出来的。

如果不是面试游戏公司，应该不会出这样的代数题来为难大家吧，hhhhh。

废话不多说了，开始带大家解题吧。

方法一 ： 直线的一般式方程求解

首先做这道题，需要你有一定的数学储备知识。不过你没有也没关系，就听我讲就完事了。

基础知识

首先我们解决这道题采用的是直线的一般式方程，也就是说形如Ax + By + C = 0；用到了这个方程的两个结论。

• 一个结论就是，如果两条直线平行，则 A1B2 = A2B1。

• 其次就是，任何直线Ax + By + C = 0 中的A，B，C，都可以用两个点的横轴坐标这么去表示：

  • A = y2 - y1；
  • B = x1 - x2；
  • C = x2y1 - x1y2；

• 如果你对这两个结论感到疑惑了话，可以去看这个文章，去补充自己的基础知识： 直线的一般式方程

还有一个知识就是关于克莱姆法则，这个涉及到大学的线性代数中的行列式的一点基础知识。也不难。如果你想要具体了解什么是克莱姆法则的话，可以去看这篇文章去补充相关的基础知识：克莱姆法则

• 如果大家懒的看这个百度百科的克莱姆法则，你也可以看看我说的简化版的。

• 克莱姆法则（Cramer’s Rule）是一种用于求解线性方程组的方法，适用于具有唯一解的线性方程组。克莱姆法则使用行列式（determinants）来求解方程组，它的基本思想是将原线性方程组的系数矩阵通过替换列的方法，变换成相应的行列式，然后通过计算这些行列式的值来求解未知数。

• 对于一个 n 阶线性方程组，如果系数行列式不为零（即方程组具有唯一解），那么可以使用克莱姆法则求解。具体求解方法是：将系数矩阵的第 i 列替换为方程组的右侧常数项构成的列向量，然后计算新的行列式，再将这个行列式与原系数行列式之比作为未知数 x_i 的解。

• 那么对于这道题来说，我们有4个点，也就是两条线段。我们可以把它先理解为两条直线，那么就会有两条一般式的直线方程。也就组成了一个二元的方程组。

  • A1x + B1y + C1 = 0; => A1x + B1y = -C1;（方程组右侧是-C1）
  • A2x + B2y + C2 = 0; => A2x + B2y = -C2;（方程组右侧是-C2）

• 在每一个方程里只有两个未知数，所以这个二元一次方程组的系数矩阵（记作：D)为：

  |A1 B1|
  |A2 B2|
  

• 计算行列式的方法是主对角线（从左上到右下）的乘积 - 副对角线（从左下到右上）的乘积。所以D这个系数矩阵的值为 ：A1B2 - A2B1;

• 我们将第一列替换为常数项列向量，得到矩阵：

| -c1  b1 |
| -c2  b2 |

• 设 Dx 为这个矩阵的行列式值，即 Dx = -c1 * b2 - (-c2 * b1)。那么解 x1 = Dx / D。

• 同理，我们将第二列替换为常数项列向量，得到矩阵：

  | a1  -c1 |
  | a2  -c2 |
  

• 设 Dy 为这个矩阵的行列式值，即 Dy = a1 * c2 - a2 * c1。那么解 x2 = Dy / D。

• 我们可以把这组解x1，x2看做是两条直线的交点的横纵坐标，x1 = x， x2 = y，

  • 所以 x = Dx/D
  • 所以 y = Dy/D

好，知道这么多数学知识，就够我们去解决这道代码题的了。还是强调一下，直线的一般式方程求解是众多直线方程中最好理解的一种了。但就这一种也够复杂的了，如果不是面游戏公司，注重几何的，没必要再深究这道题的其他解法。

解题步骤

对于这道题，我们需要写这么几个函数，分别是：

• 计算方程参数ABC的函数
• 寻找当线段平行时是否存在符合题目的交点的函数
• 判断交点是否在两条线段上的函数
• 然后就是用主函数集合这么几个函数来求得最终的解。
  • 我们在主函数里先这么去写逻辑，首先判断俩直线是否平行，如果平行则，调用寻找当线段平行时是否存在符合题目的交点的函数，去找符合的点，找不到则返回空
  • 其次用计算方程参数ABC的函数去计算两天线段的一般式方程的ABC参数分别是多少，分别存储在两个double的vector中。
  • 用克莱姆法则求出可能交点，再用判断交点是否在两条线段上的函数判断交点是否在两条线段上，若在，返回交点，否则返回空
  • 至此本题解完。

具体实现请看代码：

class Solution {
public:vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {//由一般式方程Ax + By + C = 0 的结论可知 A = y2 - y1; B = x1 - x2; C = x2y1 - x1y2;int A1 = end1[1] - start1[1];int B1 = start1[0] - end1[0];int A2 = end2[1] - start2[1];int B2 = start2[0] - end2[0];//如果线段平行，则去寻找是否有这样一个符合条件的点，找到则返回交点，否则返回空if(A1 * B2 == A2 * B1) return findPointOnTheParallelLine(start1,end1,start2,end2);//获取两条直线方程的参数ABCvector<double> p1 = getParm(start1,end1);vector<double> p2 = getParm(start2,end2);//根据克莱姆法则计算可能交点(x,y)的坐标;double x = (p2[2] * p1[1] - p1[2] * p2[1]) / (p1[0] * p2[1] - p2[0] * p1[1]);double y = (p1[2] * p2[0] - p2[2] * p1[0]) / (p1[0] * p2[1] - p2[0] * p1[1]);vector<double> result{x,y};return (isIntersectionPoint(result,start1,end1) && isIntersectionPoint(result,start2,end2)) ? result : vector<double>{};}vector<double>findPointOnTheParallelLine(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2){vector<vector<double>> result;if(isIntersectionPoint(start1,start2,end2)) result.push_back(vector<double>{double(start1[0]), double(start1[1])});if(isIntersectionPoint(start2,start1,end1)) result.push_back(vector<double>{double(start2[0]), double(start2[1])});if(isIntersectionPoint(end1,start2,end2)) result.push_back(vector<double>{double(end1[0]), double(end1[1])});if(isIntersectionPoint(end2,start1,end1)) result.push_back(vector<double>{double(end2[0]), double(end2[1])});if(result.empty()) return vector<double>{};sort(result.begin(),result.end(),[](vector<double>& l, vector<double>& q) -> bool{return l[0] < q[0];});return result[0];}vector<double> getParm(vector<int>& s, vector<int>& e){return {double(e[1] - s[1]),double(s[0] - e[0]),double(e[0] * s[1] - s[0] * e[1])};}template<typename T1, typename T2, typename T3>bool isIntersectionPoint(T1 &p, T2 &s, T3 &e){double flag = 1e-7;double d1 = sqrt((p[0] - s[0]) * (p[0] - s[0]) + (p[1] - s[1]) * (p[1] - s[1]));double d2 = sqrt((p[0] - e[0]) * (p[0] - e[0]) + (p[1] - e[1]) * (p[1] - e[1]));double d3 = sqrt((s[0] - e[0]) * (s[0] - e[0]) + (s[1] - e[1]) * (s[1] - e[1]));return fabs(d1 + d2 - d3) <= flag;}
};

复杂度分析

这段代码实现了一个计算两条线段交点的算法。以下是对主要函数的时间复杂度与空间复杂度的分析：

intersection() 函数：

• 时间复杂度：O(1)，因为这个函数中的所有操作都是常数时间操作，没有循环或递归。
• 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。

findPointOnTheParallelLine() 函数：

• 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
• 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。

getParm() 函数：

• 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
• 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。

isIntersectionPoint() 函数：

• 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
• 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。

整个算法的时间复杂度和空间复杂度都是 O(1)，因为所有函数都具有常数时间和空间复杂度。

总结

这道题确实是一道困难题，但也是一道十分有乐趣的题。因为它很巧妙的把数学的几何知识融入到了算法题中，让我见识到了数学与算法的结合。

• 最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。