线段求交点

class Solution {
public:
    vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
        std::vector<int> r{end1[0]-start1[0], end1[1]-start1[1]};
        std::vector<int> s{end2[0]-start2[0], end2[1]-start2[1]};

        std::vector<int> v{start2[0]-start1[0], start2[1]-start1[1]};

        double t = 0, u = 0;
        if (cross(r,s) != 0) {
            t = cross(v, s)*1.f / cross(r, s);
            u = cross(v, r)*1.f / cross(r, s);
        }
        std::cout << "cross(r,s): " << cross(r,s) << std::endl;
        std::cout << t << ", " << u << std::endl;
        if (cross(r, s) == 0 ) {
            if (cross(v, r) == 0) { // 共线
                double t0 = dot(v,r)*1.f / dot(r,r);
                double t1 = t0 + dot(s,r) / dot(r,r);
                if (std::min(t0,t1) > 1 || std::max(t0,t1) < 0) { //共线但不重叠
                    return vector<double>();
                }
                else { // 共线且存在重叠部分，这部分求第二个最小点即为他们的交点，LeetCode上面没看懂定义
                    std::vector<std::vector<int>> v{{start1[0], start1[1]}, {end1[0], end1[1]}, {start2[0], start2[1]}, {end2[0], end2[1]}};
                    std::sort(v.begin(), v.end());
                    double x = v[1][0];
                    double y = v[1][1];
                    return {x, y};
                }          
            }
            else { // 平行不相交
                return vector<double>();
            }
        }
        // 相交
        if (cross(r, s) != 0 && (t <= 1.0 && t >= 0) && (u <= 1.0 && u >= 0)) {
            double x = start1[0] + t*r[0]; 
            double y = start1[1] + t*r[1];
            return {x, y};
        }
    // otherwise
    return vector<double>();
    }

    //  Define the 2-dimensional vector cross product v × w to be vx*wy − vy*wx.
    int cross(std::vector<int>& v1, std::vector<int>& v2) {
        return v1[0]*v2[1] - v1[1]*v2[0];
    }

    int dot(std::vector<int>& v1, std::vector<int>& v2) {
        return v1[0]*v2[0] + v1[1]*v2[1];
    }
};

reference

stackoverflow
leetcode