11.05_线圆关系

线圆关系

问题描述

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

基本操作

算法思想

  1. 使用点到直线距离
  2. 基于判别式判断相交
  3. 适用于相交和切线计算
  4. 时间复杂度

代码实现

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

时间复杂度分析

操作 时间复杂度 空间复杂度
相交判断
交点计算
切线计算
相切判断

应用场景

  1. 碰撞检测
  2. 几何构造
  3. 相交判断
  4. 切线计算
  5. 路径规划

注意事项

  1. 浮点数精度
  2. 特殊情况处理
  3. 相切判断
  4. 交点计算
  5. 数值稳定性

常见变形

  1. 线段与圆相交
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
  1. 两圆公切线
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/> 学习算法，从牛栋开始。

全部评论

相关推荐

昨天 16:32
中南大学 Java
点赞 评论 收藏
分享
05-19 07:36
清华大学 BSP工程师
点赞 评论 收藏
分享
03-31 15:04
黑龙江科技大学 Java
每日一绷
牛大宝儿236：还没入职就PUA，[发火我之前遇到一个月给500块钱的
点赞 评论 收藏
分享
03-26 23:55
合肥大学 医疗器械研发
大佬，求带
醉蟀：你是我今年见过的最美牛客女孩
点赞 评论 收藏
分享
05-19 23:03
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我的求职总结 #
22814次浏览 430人参与
# 我的工作日记 #
96065次浏览 1261人参与
# 毕业季，给职场新人一些建议 #
18979次浏览 355人参与
# 晒一晒你收到的礼盒 #
61345次浏览 369人参与
# 我的实习日记 #
2432476次浏览 25371人参与
# 辞职之后最想做的一件事 #
9616次浏览 156人参与
# Offer比较，求稳定还是求发展 #
48671次浏览 235人参与
# 薪资一样，你会选择去大厂还是小公司 #
15850次浏览 99人参与
# 你想吐槽公司的哪些规定 #
16707次浏览 66人参与
# 选offer应该考虑哪些因素 #
16745次浏览 272人参与
# 你见过最离谱的招聘要求是什么？ #
187854次浏览 1401人参与
# 机械人还在等华为开奖吗？ #
216831次浏览 1097人参与
# 第一份工作应该只看薪资吗 #
138198次浏览 1455人参与
# 秋招想进国企该如何准备 #
57489次浏览 374人参与
# 为了秋招你都做了哪些准备？ #
10442次浏览 160人参与
# 在国企工作的人，躺平了吗？ #
327249次浏览 3841人参与
# 你怀疑过自己的专业选择吗？ #
17099次浏览 201人参与
# 牛客十周岁生日快乐 #
129259次浏览 1516人参与
# 你想留在一线还是回老家？ #
37391次浏览 447人参与
# 你小时候最想从事什么职业 #
90999次浏览 1700人参与
牛客网
牛客企业服务