交点 交点"/>
两条线段的交点 交点
两条线段的交点
- 解题思路
- 下面分别讨论三种情况
- 四点组成四边形
- 四点组成三角形
- 四点共线
- 代码
题目: 面试题 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;}
};
更多推荐
两条线段的交点 交点
发布评论