两条线段的交点 交点

交点 交点"/>

两条线段的交点 交点

两条线段的交点

• • • 解题思路
    • 下面分别讨论三种情况
  • 四点组成四边形
  • 四点组成三角形
  • 四点共线
  • • 代码

题目: 面试题 16.03. 交点

解题思路

思路：

• 两条直线相交：叉乘,向量叉乘 符号为逆时针旋转共线为正，顺时针旋转为负。值为向量组成的三角形面积的2倍。
• 点 (X, Y)在线段上 (X1,Y1) (X2,Y2): X>=min(X1,X2)&&X<=max(X1,X2)&&Y>=min(Y1,Y2)&&Y<=min(X2,Y2)
• 判断两条线段是否相交：

如果四个点组成一个四边形，则必然存在交点
如果四个点组成三角形，则一端端点必为交点
如果四个点共线，如果有交点，答案必然是两条线段中X较小的点，然后判断该点是否在另一条直线上即可，否则两条共线的线段不相交。

• 定比分点：点(x,y)在线段内部时，求(x,y)的坐标

x=(x1+ax2)/(1+a);y=(y1+ay2)/(1+a);

下面分别讨论三种情况

用线段 L1 = (X1, Y1) (X2, Y2)表示第一条线段
L2 = (A1, B1) (A2, B2)表示第二条线段

四点组成四边形

线段L1的端点必然存在线段L2的两侧
线段L2的端点必然存在线段L1的两侧
且交点在必然存在线段的内部，根据定比分点公式计算即可
判断两个点是否处于线段两侧
根据叉乘的性质，如果在其线段两侧，叉乘符号必然相反，相乘符号为负；如在同侧，乘积必然大于0；如一端端点在线段上，其叉乘必然为0。
以 判断(X1,Y1)(X2,Y2)是否处于线段L2的两侧 为例

• 构造向量L=(A2-A1,B2-B1),L1=(X1-A1,Y1-B1),L2=(X2-A1,X2-B1)
• 判断(L x L1) * (L x L2)的符号即可
• 此处需要注意同时需要判断另一条线段是否能把两个端点放在两侧，否则不能保证四点组成四边形。

// 判断(X1,Y1)(X2,Y2)是否处于线段L2的两侧
int crossA1X1 = cross(A2 - A1, B2 - B1, X1 - A1, Y1 - B1), crossA1X2 = cross(A2 - A1, B2 - B1, X2 - A1, Y2 - B1);

四点组成三角形

如一端端点在线段上，其叉乘必然为0，利用叉乘判断哪个点在线段上，即为答案

四点共线

• 分别找出L1 L2线段中x较小的点(X,Y),(A,B)
• 判断(X,Y)是否在线段L2上，判断(A,B)是否在L1上
• 若存在一个点在另一条线段上即为答案，否则两条线段相离，无交点

代码

class Solution {
public:vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {vector<double> ans;int X1 = start1[0], X2 = end1[0], A1 = start2[0], A2 = end2[0];int Y1 = start1[1], Y2 = end1[1], B1 = start2[1], B2 = end2[1];int V1 = X2 - X1, P1 = Y2 - Y1;int L1 = A1 - X1, M1 = B1 - Y1;int L2 = A2 - X1, M2 = B2 - Y1;int crossX1A1 = cross(V1, P1, L1, M1), crossX1A2 = cross(V1, P1, L2, M2);//需要注意同时需要判断另一条线段是否能把两个端点放在两侧int crossA1X1 = cross(A2 - A1, B2 - B1, X1 - A1, Y1 - B1), crossA1X2 = cross(A2 - A1, B2 - B1, X2 - A1, Y2 - B1);int crossSign =  crossX1A1 * crossX1A2;int crossSign2 = crossA1X1 * crossA1X2;if (crossSign < 0 && crossSign2 < 0) {// 有交点 且端点不在线上double s1 = abs(crossX1A1), s2 = abs(crossX1A2);// 此时 ans1 ans2必不为0double x1 = (A1 + (s1/s2)*A2) / (1 + (s1/s2));double y1 = (B1 + (s1/s2)*B2) / (1 + (s1/s2));ans.push_back(x1);ans.push_back(y1);return ans;} else if (crossSign == 0 || crossSign2 == 0) {// 不共线一端端点在线上if (crossX1A1 == 0 && crossX1A2 != 0) {// (A1, B1)交点ans.push_back((double)A1);ans.push_back((double)B1);return ans;}if (crossX1A1 != 0 && crossX1A2 == 0) {// (A1, B1)交点ans.push_back((double)A2);ans.push_back((double)B2);return ans;}if (crossA1X1 == 0 && crossA1X2 != 0) {ans.push_back((double)X1);ans.push_back((double)Y1);return ans;}if (crossA1X1 != 0 && crossA1X2 == 0) {ans.push_back((double)X2);ans.push_back((double)Y2);return ans;}// 共线// 四个点(X1, Y1) (X2, Y2) (A1, B1) (A2, B2)int X = 0, Y = 0, A = 0, B = 0;getMiniCoor(X, Y, X1, Y1, X2, Y2);getMiniCoor(A, B, A1, B1, A2, B2);// 最小交点必在(X, Y) 或者 (A, B)int ANSX = 0, ANSY = 0;// 相交bool b1 = inside(X, Y, A1, B1, A2, B2), b2 = inside(A, B, X1, Y1, X2, Y2);if (b1 || b2) {if (b1 && b2) getMiniCoor(ANSX, ANSY, X, Y, A, B);else if (b1) {ANSX = X;ANSY = Y;} else {ANSX = A;ANSY = B;}ans.push_back((double)ANSX);ans.push_back((double)ANSY);return ans;}// 相离return ans;} else{// 不相交return ans;}}// (X1, Y1) x (X2, Y2)int cross(int X1, int Y1, int X2, int Y2) {return X1*Y2 - X2*Y1; // 叉乘为0则共线 (X1,Y1)逆时针旋转共线为正 顺时针旋转共线为负}// 判断点(ux, uy)是否在(X1, Y1) (X2, Y2) 线段上bool inside(int ux, int uy, int X1, int Y1, int X2, int Y2) {return ux >= min(X1, X2) && ux <= max(X1, X2) && uy >= min(Y1, Y2) && uy <= max(Y1, Y2);}void getMiniCoor(int &X, int &Y, int X1, int Y1, int X2, int Y2) {if (X1 == X2 && Y1 <= Y2 || X1 < X2) {X = X1;Y = Y1;} else {X = X2;Y = Y2;}return;}
};