LeetCode 面试题 16.03. 交点

Categories:

题目描述
思路分析
1. 解法一：直线交点 + 线段判定（推荐）
相似题目

题目描述

✅ 面试题 16.03. 交点

思路分析

解法一：直线交点 + 线段判定（推荐）

核心思路：

先判断两线段是否平行；平行且共线则检查重叠部分。

非平行时计算直线交点，再判断是否落在两条线段内。

对坐标使用双精度并设置误差判断。

复杂度分析：

时间复杂度：O(1)。

空间复杂度：O(1)。

import java.util.Arrays;

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) {
                return new double[0];
            }

            double[] maxStart = greater(a1, b1) ? a1 : b1;
            double[] minEnd = greater(a2, b2) ? b2 : a2;
            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 {
			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]
}

相似题目

题目	难度	考察点
228. 汇总区间	简单	线段
223. 矩形面积	中等	几何
149. 直线上最多的点数	困难	几何
593. 有效的正方形	中等	几何
836. 矩形重叠	简单	几何

本文作者: HGNULB

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