LEETCODE算法:16.03. Intersection LCCI

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any. If there's no intersection, return an empty array.

The absolute error should not exceed 10^-6. If there are more than one intersections, return the one with smallest X axis value. If there are more than one intersections that have same X axis value, return the one with smallest Y axis value. Example 1:

Input: line1 = {0, 0}, {1, 0} line2 = {1, 1}, {0, -1} Output: {0.5, 0} Example 2:

Input: line1 = {0, 0}, {3, 3} line2 = {1, 1}, {2, 2} Output: {1, 1} Example 3:

Input: line1 = {0, 0}, {1, 1} line2 = {1, 0}, {2, 1} Output: {} (no intersection) Note:

The absolute value of coordinate value will not exceed 2^7. All coordinates are valid 2D coordinates.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
        int x1=start1[0],y1=start1[1];
        int x2=end1[0],y2=end1[1];
        int x3=start2[0],y3=start2[1];
        int x4=end2[0],y4=end2[1];
        //把x值小的坐标放在x1中，x相同比较y值
        if(x1>x2)
        {
            swap(x1,x2);
            swap(y1,y2);
        }else if(x1==x2&&y1>y2)
        {
            swap(y1,y2);
        }
        if(x3>x4)
        {
            swap(x3,x4);
            swap(y3,y4);
        }else if(x3==x4&&y3>y4)
        {
            swap(y3,y4);
        }
        //hy=kx+b,一般情况h=1，即为斜截式，只有当x=0情况下才会改变h值
        double k1,k2,b1,b2,h1=1,h2=1;
        if(x1-x2==0)
        {
            h1=0;
            k1=-1;
            b1=x1;
        }else{
            k1=(y1-y2)/(x1*1.0-x2);
            b1=y1-k1*x1;
        }
        
        if(x3-x4==0)
        {
            h2=0;
            k2=-1;
            b2=x3;
        }else{
            k2=(y3-y4)/(x3*1.0-x4);
            b2=y3-k2*x3;
        }

        //解方程
        vector<double> ans;
        if(h1==1&&h2==1){
        if(k1==k2)
        {//斜率相同
            if(b1!=b2) return ans; //平行不重合无解
            else{//重合，取两线段起点较大的一个，最后判断是否越界
                if(x1<x3)
                {
                    ans.push_back(x3);
                    ans.push_back(y3);
                }else{
                    ans.push_back(x1);
                    ans.push_back(y1);
                }
            }
        }else{//不平行，常规求解
            double x=(b2-b1)/(k1-k2);
            double y=k1*x+b1;
            ans.push_back(x);
            ans.push_back(y);
        }
        }else{//至少有一条线段垂直x轴
            if(h1==0&&h2==0){//两条线段都垂直x轴
                if(b1!=b2) return ans;//平行不重合无解
                else{//平行重合，可能有解
                    ans.push_back(x1);
                    ans.push_back(max(y1,y3));
                }
            }else if(h1==0){//第一条线段垂直x轴求解
                ans.push_back(-1*b1/k1);
                ans.push_back((k2*ans[0])+b2);
            }else if(h2==0){//第二条线段垂直x轴求解
                ans.push_back(-1*b2/k2);
                ans.push_back((k1*ans[0])+b1);
            }
        }
        if(ans[0]<x1||ans[1]<min(y1,y2)||ans[0]>x2||ans[1]>max(y1,y2)||ans[0]<x3||ans[1]<min(y3,y4)||ans[0]>x4||ans[1]>max(y3,y4))
        {//判断是否越界
            vector<double> tmp;
            return tmp;
        }else{
            return ans;
        } 
    }
};

说明

  • 第一反应使用斜截式求解，但是需要考虑太多情况加了许多判断，虽然完成，但是比较繁琐。