11.03_线线关系

线线关系

问题描述

线线关系处理平面上两条直线/线段之间的基本关系，包括相交判断、交点计算等。常用于几何判定和相交问题。

基本操作

算法思想

使用向量表示直线方向
基于叉积判断相交
适用于相交和平行判断
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Solution {
public:
    // 判断两线段相交
    bool segmentIntersect(const Line& l1, const Line& l2) {
        Point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2;
        
        // 快速排斥实验
        if (max(a.x, b.x) < min(c.x, d.x) ||
            max(c.x, d.x) < min(a.x, b.x) ||
            max(a.y, b.y) < min(c.y, d.y) ||
            max(c.y, d.y) < min(a.y, b.y)) {
            return false;
        }
        
        // 跨立实验
        double d1 = (b - a).cross(c - a);
        double d2 = (b - a).cross(d - a);
        double d3 = (d - c).cross(a - c);
        double d4 = (d - c).cross(b - c);
        
        return d1 * d2 <= 0 && d3 * d4 <= 0;
    }
    
    // 计算两直线交点
    Point lineIntersection(const Line& l1, const Line& l2) {
        Point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2;
        double s1 = (b - a).cross(c - a);
        double s2 = (b - a).cross(d - a);
        return Point(
            (c.x * s2 - d.x * s1) / (s2 - s1),
            (c.y * s2 - d.y * s1) / (s2 - s1)
        );
    }
    
    // 判断两直线平行
    bool isParallel(const Line& l1, const Line& l2) {
        Point dir1 = l1.p2 - l1.p1;
        Point dir2 = l2.p2 - l2.p1;
        return abs(dir1.cross(dir2)) < EPS;
    }
};

class Solution {
    static final double EPS = 1e-10;
    
    // 判断两线段相交
    public boolean segmentIntersect(Line l1, Line l2) {
        Point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2;
        
        // 快速排斥实验
        if (Math.max(a.x, b.x) < Math.min(c.x, d.x) ||
            Math.max(c.x, d.x) < Math.min(a.x, b.x) ||
            Math.max(a.y, b.y) < Math.min(c.y, d.y) ||
            Math.max(c.y, d.y) < Math.min(a.y, b.y)) {
            return false;
        }
        
        // 跨立实验
        double d1 = b.subtract(a).cross(c.subtract(a));
        double d2 = b.subtract(a).cross(d.subtract(a));
        double d3 = d.subtract(c).cross(a.subtract(c));
        double d4 = d.subtract(c).cross(b.subtract(c));
        
        return d1 * d2 <= 0 && d3 * d4 <= 0;
    }
    
    // 计算两直线交点
    public Point lineIntersection(Line l1, Line l2) {
        Point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2;
        double s1 = b.subtract(a).cross(c.subtract(a));
        double s2 = b.subtract(a).cross(d.subtract(a));
        return new Point(
            (c.x * s2 - d.x * s1) / (s2 - s1),
            (c.y * s2 - d.y * s1) / (s2 - s1)
        );
    }
    
    // 判断两直线平行
    public boolean isParallel(Line l1, Line l2) {
        Point dir1 = l1.p2.subtract(l1.p1);
        Point dir2 = l2.p2.subtract(l2.p1);
        return Math.abs(dir1.cross(dir2)) < EPS;
    }
}

class Solution:
    def __init__(self):
        self.EPS = 1e-10
    
    # 判断两线段相交
    def segment_intersect(self, l1: Line, l2: Line) -> bool:
        a, b = l1.p1, l1.p2
        c, d = l2.p1, l2.p2
        
        # 快速排斥实验
        if (max(a.x, b.x) < min(c.x, d.x) or
            max(c.x, d.x) < min(a.x, b.x) or
            max(a.y, b.y) < min(c.y, d.y) or
            max(c.y, d.y) < min(a.y, b.y)):
            return False
        
        # 跨立实验
        d1 = (b - a).cross(c - a)
        d2 = (b - a).cross(d - a)
        d3 = (d - c).cross(a - c)
        d4 = (d - c).cross(b - c)
        
        return d1 * d2 <= 0 and d3 * d4 <= 0
    
    # 计算两直线交点
    def line_intersection(self, l1: Line, l2: Line) -> Point:
        a, b = l1.p1, l1.p2
        c, d = l2.p1, l2.p2
        s1 = (b - a).cross(c - a)
        s2 = (b - a).cross(d - a)
        return Point(
            (c.x * s2 - d.x * s1) / (s2 - s1),
            (c.y * s2 - d.y * s1) / (s2 - s1)
        )
    
    # 判断两直线平行
    def is_parallel(self, l1: Line, l2: Line) -> bool:
        dir1 = l1.p2 - l1.p1
        dir2 = l2.p2 - l2.p1
        return abs(dir1.cross(dir2)) < self.EPS

时间复杂度分析

操作时间复杂度空间复杂度

线段相交判断	$\mathcal{O}(1)$	$\mathcal{O}(1)$
直线交点计算	$\mathcal{O}(1)$	$\mathcal{O}(1)$
平行判断	$\mathcal{O}(1)$	$\mathcal{O}(1)$
重合判断	$\mathcal{O}(1)$	$\mathcal{O}(1)$

应用场景

相交判断
交点计算
平行判断
重合判断
几何构造

注意事项

浮点数精度
除零判断
边界情况
平行处理
重合处理

常见变形

多线段相交

cpp
java
python

class Solution {
public:
    // 判断多条线段是否存在相交
    bool hasIntersection(vector<Line>& segments) {
        int n = segments.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (segmentIntersect(segments[i], segments[j])) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 计算所有相交点
    vector<Point> findAllIntersections(vector<Line>& segments) {
        vector<Point> intersections;
        int n = segments.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (segmentIntersect(segments[i], segments[j])) {
                    intersections.push_back(
                        lineIntersection(segments[i], segments[j])
                    );
                }
            }
        }
        return intersections;
    }
};

class Solution {
    // 判断多条线段是否存在相交
    public boolean hasIntersection(Line[] segments) {
        int n = segments.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (segmentIntersect(segments[i], segments[j])) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 计算所有相交点
    public List<Point> findAllIntersections(Line[] segments) {
        List<Point> intersections = new ArrayList<>();
        int n = segments.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (segmentIntersect(segments[i], segments[j])) {
                    intersections.add(
                        lineIntersection(segments[i], segments[j])
                    );
                }
            }
        }
        return intersections;
    }
}

class Solution:
    # 判断多条线段是否存在相交
    def has_intersection(self, segments: List[Line]) -> bool:
        n = len(segments)
        for i in range(n):
            for j in range(i + 1, n):
                if self.segment_intersect(segments[i], segments[j]):
                    return True
        return False
    
    # 计算所有相交点
    def find_all_intersections(self, segments: List[Line]) -> List[Point]:
        intersections = []
        n = len(segments)
        for i in range(n):
            for j in range(i + 1, n):
                if self.segment_intersect(segments[i], segments[j]):
                    intersections.append(
                        self.line_intersection(segments[i], segments[j])
                    )
        return intersections

线段集合处理

cpp
java
python

class Solution {
public:
    // 计算线段集合的总长度（处理重叠）
    double totalLength(vector<Line>& segments) {
        // 按左端点排序
        sort(segments.begin(), segments.end(),
             [](const Line& a, const Line& b) {
                 return a.p1.x < b.p1.x;
             });
        
        double total = 0;
        double right = -DBL_MAX;
        
        for (const Line& seg : segments) {
            if (seg.p1.x > right) {
                total += seg.p2.x - seg.p1.x;
            } else if (seg.p2.x > right) {
                total += seg.p2.x - right;
            }
            right = max(right, seg.p2.x);
        }
        
        return total;
    }
};

class Solution {
    // 计算线段集合的总长度（处理重叠）
    public double totalLength(Line[] segments) {
        // 按左端点排序
        Arrays.sort(segments, (a, b) -> Double.compare(a.p1.x, b.p1.x));
        
        double total = 0;
        double right = Double.NEGATIVE_INFINITY;
        
        for (Line seg : segments) {
            if (seg.p1.x > right) {
                total += seg.p2.x - seg.p1.x;
            } else if (seg.p2.x > right) {
                total += seg.p2.x - right;
            }
            right = Math.max(right, seg.p2.x);
        }
        
        return total;
    }
}

class Solution:
    # 计算线段集合的总长度（处理重叠）
    def total_length(self, segments: List[Line]) -> float:
        # 按左端点排序
        segments.sort(key=lambda seg: seg.p1.x)
        
        total = 0
        right = float('-inf')
        
        for seg in segments:
            if seg.p1.x > right:
                total += seg.p2.x - seg.p1.x
            elif seg.p2.x > right:
                total += seg.p2.x - right
            right = max(right, seg.p2.x)
        
        return total

牛客代码笔记-牛栋文章被收录于专栏

汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。