LeetCode 面试题 16.03. 交点

2020-11-18 HGNULB 约 9 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 困难未解决 2-5 程序员面试金典（第 6 版）字节美团

题目描述

✅ 面试题 16.03. 交点

题意分析

求两条有限线段的公共点，没有交点返回空数组。若重叠产生多个交点，返回横坐标最小、横坐标相同时纵坐标最小的公共点；端点相接也算相交。题目要求浮点误差不超过 10^-6。

解法：直线交点 + 线段判定

核心思路

[!blue]

先将每条线段的两个端点按“横坐标优先、纵坐标其次”排列，让起点不大于终点。这个顺序主要用于共线重叠：非竖直线段沿横坐标比较位置，竖直线段则沿纵坐标比较，统一成有序区间。

两端点 (x1, y1)、(x2, y2) 对应的直线可以写成 A*x + B*y = C，其中 A = y2 - y1、B = x1 - x2、C = A*x1 + B*y1。这种形式不需要求斜率，因此水平线和竖直线也能直接处理。两条直线系数的行列式为 det = A1*B2 - A2*B1。

若 det 不为零，两条直线只有一个交点。消元得到 x = (C1*B2 - C2*B1) / det、y = (A1*C2 - A2*C1) / det。这个点已经满足两条直线方程，但可能落在延长线上，所以还要检查它的横、纵坐标是否分别处于每条线段的端点范围内。两条线段都通过范围检查，才返回该点。

若 det 为零，就不能除以它求交点。先用叉积检查两段是否共线：cross(a, b, c) 为向量 b-a 与 c-a 的叉积，非零说明 c 不在 ab 所在直线上。代码对两个方向都检查一次，也能覆盖其中一条线段退化成点时，另一条线段是否经过这个点的情况。

共线后，交集起点是两个起点中较大的 maxStart，交集终点是两个终点中较小的 minEnd。若前者大于后者，则两段分离；否则公共区间非空，返回 maxStart。按此前统一的坐标顺序，它恰好是公共区间中横坐标最小、必要时纵坐标最小的点，起终点相等时也能返回唯一公共端点。两段都退化成点时，这个区间判断同样只接受坐标相同的情况。

输入是绝对值不超过 128 的整数坐标，代码用 double 或 float64 求交点，并用 EPS = 1e-9 容忍边界附近的浮点误差；不需要对输入端点或最终答案取整。

解题步骤

将四个端点转换成浮点坐标，并分别规范两条线段的起终点顺序。

计算两条直线的系数以及行列式 det。

非平行时联立求交点，再检查它是否同时落在两段的有限范围内。

平行或退化时检查共线性；共线则比较较大起点与较小终点，返回最小公共点或空数组。

代码实现

// 非平行时计算直线交点，再判断是否落在两条线段内。
class Solution {
    private static final double EPS = 1e-9;

    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        double[] a1 = toPoint(start1);
        double[] a2 = toPoint(end1);
        double[] b1 = toPoint(start2);
        double[] b2 = toPoint(end2);

        // 每段按坐标字典序规范起终点，重叠时才能统一取最小公共点。
        if (greater(a1, a2)) {
            swap(a1, a2);
        }

        if (greater(b1, b2)) {
            swap(b1, b2);
        }

        double A1 = a2[1] - a1[1];
        double B1 = a1[0] - a2[0];
        double C1 = A1 * a1[0] + B1 * a1[1];

        double A2 = b2[1] - b1[1];
        double B2 = b1[0] - b2[0];
        double C2 = A2 * b1[0] + B2 * b1[1];

        double det = A1 * B2 - A2 * B1;

        if (Math.abs(det) < EPS) {
            if (Math.abs(cross(a1, a2, b1)) > EPS || Math.abs(cross(b1, b2, a1)) > EPS) {
                return new double[0];
            }

            // 共线部分由较大起点与较小终点夹出。
            double[] maxStart = a1;

            if (greater(b1, a1)) {
                maxStart = b1;
            }

            double[] minEnd = a2;

            if (greater(a2, b2)) {
                minEnd = b2;
            }

            if (greater(maxStart, minEnd)) {
                return new double[0];
            }

            return maxStart;
        }

        double x = (C1 * B2 - C2 * B1) / det;
        double y = (A1 * C2 - A2 * C1) / det;
        double[] p = new double[] {
            x,
            y,
        };

        // 直线交点只有同时落在两条线段的有限范围内才有效。
        if (onSegment(p, a1, a2) && onSegment(p, b1, b2)) {
            return p;
        }

        return new double[0];
    }

    private boolean onSegment(double[] p, double[] s, double[] e) {
        return p[0] >= Math.min(s[0], e[0]) - EPS
                && p[0] <= Math.max(s[0], e[0]) + EPS
                && p[1] >= Math.min(s[1], e[1]) - EPS
                && p[1] <= Math.max(s[1], e[1]) + EPS;
    }

    private double cross(double[] a, double[] b, double[] c) {
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
    }

    private boolean greater(double[] p, double[] q) {
        return p[0] > q[0] || (Math.abs(p[0] - q[0]) < EPS && p[1] > q[1]);
    }

    private double[] toPoint(int[] p) {
        return new double[] {
            p[0],
            p[1],
        };
    }

    private void swap(double[] a, double[] b) {
        double t0 = a[0];
        double t1 = a[1];

        a[0] = b[0];
        a[1] = b[1];
        b[0] = t0;
        b[1] = t1;
    }
}

import "math"

// 非平行时计算直线交点，再判断是否落在两条线段内。
func intersection(start1 []int, end1 []int, start2 []int, end2 []int) []float64 {
    const eps = 1e-9
    p1 := []float64{
        float64(start1[0]),
        float64(start1[1]),
    }
    p2 := []float64{
        float64(end1[0]),
        float64(end1[1]),
    }
    p3 := []float64{
        float64(start2[0]),
        float64(start2[1]),
    }
    p4 := []float64{
        float64(end2[0]),
        float64(end2[1]),
    }

    // 每段按坐标字典序规范起终点，重叠时才能统一取最小公共点。
    if greater(p1, p2, eps) {
        swapPoint(p1, p2)
    }
    if greater(p3, p4, eps) {
        swapPoint(p3, p4)
    }

    A1 := p2[1] - p1[1]
    B1 := p1[0] - p2[0]
    C1 := A1*p1[0] + B1*p1[1]

    A2 := p4[1] - p3[1]
    B2 := p3[0] - p4[0]
    C2 := A2*p3[0] + B2*p3[1]

    det := A1*B2 - A2*B1
    if math.Abs(det) < eps {
        if math.Abs(cross(p1, p2, p3)) > eps || math.Abs(cross(p3, p4, p1)) > eps {
            return []float64{}
        }

        // 共线部分由较大起点与较小终点夹出。
        maxStart := p1
        if greater(p3, p1, eps) {
            maxStart = p3
        }
        minEnd := p2
        if greater(p2, p4, eps) {
            minEnd = p4
        }
        if greater(maxStart, minEnd, eps) {
            return []float64{}
        }
        return []float64{
            maxStart[0],
            maxStart[1],
        }
    }

    x := (C1*B2 - C2*B1) / det
    y := (A1*C2 - A2*C1) / det
    p := []float64{
        x,
        y,
    }

    // 直线交点只有同时落在两条线段的有限范围内才有效。
    if onSegment(p, p1, p2, eps) && onSegment(p, p3, p4, eps) {
        return p
    }
    return []float64{}
}

func onSegment(p []float64, a []float64, b []float64, eps float64) bool {
    return p[0] >= math.Min(a[0], b[0])-eps && p[0] <= math.Max(a[0], b[0])+eps &&
        p[1] >= math.Min(a[1], b[1])-eps && p[1] <= math.Max(a[1], b[1])+eps
}

func cross(a []float64, b []float64, c []float64) float64 {
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
}

func greater(p []float64, q []float64, eps float64) bool {
    return p[0] > q[0] || (math.Abs(p[0]-q[0]) < eps && p[1] > q[1])
}

func swapPoint(a []float64, b []float64) {
    a[0], b[0] = b[0], a[0]
    a[1], b[1] = b[1], a[1]
}

复杂度分析

时间复杂度：$O(1)$，只对四个端点执行固定数量的算术运算和范围判断。

空间复杂度：$O(1)$，只保存固定数量的坐标与直线系数。

关键点总结

[!green]

直线方程负责求候选交点，端点范围负责排除延长线交点。

行列式为零时转入共线判断，不能直接判无解或继续做除法。

共线后按坐标顺序求区间交集，较大起点就是题目要求的最小公共点。

易错点总结

[!yellow]

仅判断两条直线相交，会接受线段范围外的交点；必须检查两段的横、纵范围。

平行就返回空，会漏掉共线重叠与端点相接。

直接采用输入给定的起终点顺序，可能把反向给出的线段误判为不相交。

共线时取较小起点，可能选到只属于其中一条线段的位置。

相似题目

题目	难度	关联与区别
补充题 19. 判断一个点是否在三角形内	中等	同样利用叉积判断点相对边的方向，本题还要处理两条线段的共线重叠与端点交集。
1232. 缀点成线	简单	共线判定是特殊分支基础，本题共线时还必须检查两线段的投影范围是否相交。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/60425322

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！