线圆关系

问题描述

线圆关系处理平面上直线/线段与圆之间的基本关系，包括相交判断、交点计算等。常用于碰撞检测和几何构造问题。

基本操作

算法思想

使用点到直线距离
基于判别式判断相交
适用于相交和切线计算
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Solution {
public:
    // 判断直线与圆相交
    int lineCircleIntersect(const Line& line, const Circle& circle) {
        double dist = line.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return 0;  // 不相交
        if (abs(dist - circle.radius) < EPS) return 1;  // 相切
        return 2;  // 相交
    }
    
    // 计算直线与圆的交点
    vector<Point> lineCircleIntersection(const Line& line, const Circle& circle) {
        double dist = line.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return {};
        
        Point proj = line.projectPoint(circle.center);
        if (abs(dist - circle.radius) < EPS) return {proj};
        
        double len = sqrt(circle.radius * circle.radius - dist * dist);
        Point dir = (line.p2 - line.p1).normalize();
        
        return {
            proj + dir * len,
            proj - dir * len
        };
    }
    
    // 计算圆的切线
    vector<Line> circleTangentLines(const Point& p, const Circle& circle) {
        vector<Line> result;
        double d = p.distance(circle.center);
        if (d < circle.radius - EPS) return result;  // 点在圆内
        
        if (abs(d - circle.radius) < EPS) {
            // 点在圆上，只有一条切线
            Point normal = (p - circle.center).rotate90();
            result.push_back(Line(p, p + normal));
            return result;
        }
        
        // 点在圆外，有两条切线
        double angle = asin(circle.radius / d);
        Point v = (circle.center - p).normalize() * d;
        result.push_back(Line(p, p + v.rotate(angle)));
        result.push_back(Line(p, p + v.rotate(-angle)));
        return result;
    }
};

class Solution {
    static final double EPS = 1e-10;
    
    // 判断直线与圆相交
    public int lineCircleIntersect(Line line, Circle circle) {
        double dist = line.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return 0;  // 不相交
        if (Math.abs(dist - circle.radius) < EPS) return 1;  // 相切
        return 2;  // 相交
    }
    
    // 计算直线与圆的交点
    public List<Point> lineCircleIntersection(Line line, Circle circle) {
        double dist = line.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return new ArrayList<>();
        
        Point proj = line.projectPoint(circle.center);
        if (Math.abs(dist - circle.radius) < EPS) {
            return Arrays.asList(proj);
        }
        
        double len = Math.sqrt(circle.radius * circle.radius - dist * dist);
        Point dir = line.p2.subtract(line.p1).normalize();
        
        return Arrays.asList(
            proj.add(dir.multiply(len)),
            proj.subtract(dir.multiply(len))
        );
    }
    
    // 计算圆的切线
    public List<Line> circleTangentLines(Point p, Circle circle) {
        List<Line> result = new ArrayList<>();
        double d = p.distance(circle.center);
        if (d < circle.radius - EPS) return result;  // 点在圆内
        
        if (Math.abs(d - circle.radius) < EPS) {
            // 点在圆上，只有一条切线
            Point normal = p.subtract(circle.center).rotate90();
            result.add(new Line(p, p.add(normal)));
            return result;
        }
        
        // 点在圆外，有两条切线
        double angle = Math.asin(circle.radius / d);
        Point v = circle.center.subtract(p).normalize().multiply(d);
        result.add(new Line(p, p.add(v.rotate(angle))));
        result.add(new Line(p, p.add(v.rotate(-angle))));
        return result;
    }
}

class Solution:
    def __init__(self):
        self.EPS = 1e-10
    
    # 判断直线与圆相交
    def line_circle_intersect(self, line: Line, circle: Circle) -> int:
        dist = line.distance_to_point(circle.center)
        if dist > circle.radius + self.EPS:
            return 0  # 不相交
        if abs(dist - circle.radius) < self.EPS:
            return 1  # 相切
        return 2  # 相交
    
    # 计算直线与圆的交点
    def line_circle_intersection(self, line: Line, 
                               circle: Circle) -> List[Point]:
        dist = line.distance_to_point(circle.center)
        if dist > circle.radius + self.EPS:
            return []
        
        proj = line.project_point(circle.center)
        if abs(dist - circle.radius) < self.EPS:
            return [proj]
        
        len = math.sqrt(circle.radius * circle.radius - dist * dist)
        dir = (line.p2 - line.p1).normalize()
        
        return [
            proj + dir * len,
            proj - dir * len
        ]
    
    # 计算圆的切线
    def circle_tangent_lines(self, p: Point, circle: Circle) -> List[Line]:
        result = []
        d = p.distance(circle.center)
        if d < circle.radius - self.EPS:
            return result  # 点在圆内
        
        if abs(d - circle.radius) < self.EPS:
            # 点在圆上，只有一条切线
            normal = (p - circle.center).rotate90()
            result.append(Line(p, p + normal))
            return result
        
        # 点在圆外，有两条切线
        angle = math.asin(circle.radius / d)
        v = (circle.center - p).normalize() * d
        result.append(Line(p, p + v.rotate(angle)))
        result.append(Line(p, p + v.rotate(-angle)))
        return result

时间复杂度分析

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

相交判断	$\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 segmentCircleIntersect(const Line& segment, const Circle& circle) {
        if (circle.contains(segment.p1) || circle.contains(segment.p2)) {
            return true;
        }
        
        double dist = segment.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return false;
        
        Point proj = segment.projectPoint(circle.center);
        return segment.onSegment(proj);
    }
    
    // 计算线段与圆的交点
    vector<Point> segmentCircleIntersection(const Line& segment, 
                                          const Circle& circle) {
        vector<Point> result;
        vector<Point> intersections = lineCircleIntersection(segment, circle);
        
        for (const Point& p : intersections) {
            if (segment.onSegment(p)) {
                result.push_back(p);
            }
        }
        return result;
    }
};

class Solution {
    // 判断线段与圆相交
    public boolean segmentCircleIntersect(Line segment, Circle circle) {
        if (circle.contains(segment.p1) || circle.contains(segment.p2)) {
            return true;
        }
        
        double dist = segment.distanceToPoint(circle.center);
        if (dist > circle.radius + EPS) return false;
        
        Point proj = segment.projectPoint(circle.center);
        return segment.onSegment(proj);
    }
    
    // 计算线段与圆的交点
    public List<Point> segmentCircleIntersection(Line segment, Circle circle) {
        List<Point> result = new ArrayList<>();
        List<Point> intersections = lineCircleIntersection(segment, circle);
        
        for (Point p : intersections) {
            if (segment.onSegment(p)) {
                result.add(p);
            }
        }
        return result;
    }
}

class Solution:
    # 判断线段与圆相交
    def segment_circle_intersect(self, segment: Line, 
                               circle: Circle) -> bool:
        if (circle.contains(segment.p1) or 
            circle.contains(segment.p2)):
            return True
        
        dist = segment.distance_to_point(circle.center)
        if dist > circle.radius + self.EPS:
            return False
        
        proj = segment.project_point(circle.center)
        return segment.on_segment(proj)
    
    # 计算线段与圆的交点
    def segment_circle_intersection(self, segment: Line, 
                                 circle: Circle) -> List[Point]:
        result = []
        intersections = self.line_circle_intersection(segment, circle)
        
        for p in intersections:
            if segment.on_segment(p):
                result.append(p)
        return result

两圆公切线

cpp
java
python

class Solution {
public:
    // 计算两圆的公切线
    vector<Line> commonTangentLines(const Circle& c1, const Circle& c2) {
        vector<Line> result;
        Point d = c2.center - c1.center;
        double dist = d.length();
        
        if (dist < abs(c1.radius - c2.radius) - EPS) {
            return result;  // 一个圆在另一个圆内
        }
        
        // 外切线
        if (abs(c1.radius - c2.radius) < EPS) {
            // 半径相等，切线平行
            Point normal = d.rotate90().normalize();
            result.push_back(Line(
                c1.center + normal * c1.radius,
                c2.center + normal * c2.radius
            ));
            result.push_back(Line(
                c1.center - normal * c1.radius,
                c2.center - normal * c2.radius
            ));
        } else {
            // 半径不等，切线相交
            Point v = d * (c1.radius / (c1.radius - c2.radius));
            double angle = acos(c1.radius / v.length());
            result.push_back(Line(
                c1.center + v.rotate(angle).normalize() * c1.radius,
                c2.center + v.rotate(angle).normalize() * c2.radius
            ));
            result.push_back(Line(
                c1.center + v.rotate(-angle).normalize() * c1.radius,
                c2.center + v.rotate(-angle).normalize() * c2.radius
            ));
        }
        
        // 内切线
        if (dist > c1.radius + c2.radius - EPS) {
            Point v = d * (c1.radius / (c1.radius + c2.radius));
            double angle = acos(c1.radius / v.length());
            result.push_back(Line(
                c1.center + v.rotate(angle).normalize() * c1.radius,
                c2.center - v.rotate(angle).normalize() * c2.radius
            ));
            result.push_back(Line(
                c1.center + v.rotate(-angle).normalize() * c1.radius,
                c2.center - v.rotate(-angle).normalize() * c2.radius
            ));
        }
        
        return result;
    }
};

class Solution {
    // 计算两圆的公切线
    public List<Line> commonTangentLines(Circle c1, Circle c2) {
        List<Line> result = new ArrayList<>();
        Point d = c2.center.subtract(c1.center);
        double dist = d.length();
        
        if (dist < Math.abs(c1.radius - c2.radius) - EPS) {
            return result;  // 一个圆在另一个圆内
        }
        
        // 外切线
        if (Math.abs(c1.radius - c2.radius) < EPS) {
            // 半径相等，切线平行
            Point normal = d.rotate90().normalize();
            result.add(new Line(
                c1.center.add(normal.multiply(c1.radius)),
                c2.center.add(normal.multiply(c2.radius))
            ));
            result.add(new Line(
                c1.center.subtract(normal.multiply(c1.radius)),
                c2.center.subtract(normal.multiply(c2.radius))
            ));
        } else {
            // 半径不等，切线相交
            Point v = d.multiply(c1.radius / (c1.radius - c2.radius));
            double angle = Math.acos(c1.radius / v.length());
            result.add(new Line(
                c1.center.add(v.rotate(angle).normalize().multiply(c1.radius)),
                c2.center.add(v.rotate(angle).normalize().multiply(c2.radius))
            ));
            result.add(new Line(
                c1.center.add(v.rotate(-angle).normalize().multiply(c1.radius)),
                c2.center.add(v.rotate(-angle).normalize().multiply(c2.radius))
            ));
        }
        
        // 内切线
        if (dist > c1.radius + c2.radius - EPS) {
            Point v = d.multiply(c1.radius / (c1.radius + c2.radius));
            double angle = Math.acos(c1.radius / v.length());
            result.add(new Line(
                c1.center.add(v.rotate(angle).normalize().multiply(c1.radius)),
                c2.center.subtract(v.rotate(angle).normalize().multiply(c2.radius))
            ));
            result.add(new Line(
                c1.center.add(v.rotate(-angle).normalize().multiply(c1.radius)),
                c2.center.subtract(v.rotate(-angle).normalize().multiply(c2.radius))
            ));
        }
        
        return result;
    }
}

class Solution:
    # 计算两圆的公切线
    def common_tangent_lines(self, c1: Circle, c2: Circle) -> List[Line]:
        result = []
        d = c2.center - c1.center
        dist = d.length()
        
        if dist < abs(c1.radius - c2.radius) - self.EPS:
            return result  # 一个圆在另一个圆内
        
        # 外切线
        if abs(c1.radius - c2.radius) < self.EPS:
            # 半径相等，切线平行
            normal = d.rotate90().normalize()
            result.append(Line(
                c1.center + normal * c1.radius,
                c2.center + normal * c2.radius
            ))
            result.append(Line(
                c1.center - normal * c1.radius,
                c2.center - normal * c2.radius
            ))
        else:
            # 半径不等，切线相交
            v = d * (c1.radius / (c1.radius - c2.radius))
            angle = math.acos(c1.radius / v.length())
            result.append(Line(
                c1.center + v.rotate(angle).normalize() * c1.radius,
                c2.center + v.rotate(angle).normalize() * c2.radius
            ))
            result.append(Line(
                c1.center + v.rotate(-angle).normalize() * c1.radius,
                c2.center + v.rotate(-angle).normalize() * c2.radius
            ))
        
        # 内切线
        if dist > c1.radius + c2.radius - self.EPS:
            v = d * (c1.radius / (c1.radius + c2.radius))
            angle = math.acos(c1.radius / v.length())
            result.append(Line(
                c1.center + v.rotate(angle).normalize() * c1.radius,
                c2.center - v.rotate(angle).normalize() * c2.radius
            ))
            result.append(Line(
                c1.center + v.rotate(-angle).normalize() * c1.radius,
                c2.center - v.rotate(-angle).normalize() * c2.radius
            ))
        
        return result

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

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

全部评论

推荐最新楼层

11-03 16:48

已编辑

百度_高级研发工程师

摸爬滚打，我也一定要离开华为

事实是检验真理的唯一标准。 无论我们怎么去说，去讲述，去证明，都抵不过一个offer来得实在，无论我们怎么去复现求职中的摸爬滚打、扒皮抽筋、狼狈不堪，都抵不过你在简历写上大厂的名字（外包不算）。 所以在我求职期间，我什么话都不说，什么话都不讲，因为没有意义，虽然我总讲过程才是意义，但只有当你上岸的那一刻，你才有资格回想在水里的挣扎，只有等你出了山，你才知道山的全貌。 我为什么一定要离开华为OD，难道它不稳定吗，不能赚钱吗。为了证明自己，那肯定有的。其实更多的是印证我的认知是否真的正确。 （给不了解我的人交代一下背景，在下双非一本，gap一年，华为OD外包，摸爬滚打4个月，艰难上岸百度正编）一、...

先锋战士：说得很真诚。鄙视链自古有之，学历，家庭背景，财富，权利。从小有之，小学羡慕那些当班委的，中学羡慕那些学生会的，高中羡慕尖子班拿教学金的，大学羡慕高绩点，毕业了羡慕进大厂的。工作了，又羡慕高职级的，再后来又羡慕别人早早结婚的。我想表达的观点很简单，无论是华为od还是百度，都是经历，没有孰高孰低，为了抵达下一个风景，总会付出更多东西，但不就是人生吗？正如登山，每个阶段的山，都要想办法攀登，在博主的文字中，见到了坚持和积极寻找问题解决办法的心态