11.06_圆圆关系

圆圆关系

问题描述

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

基本操作

算法思想

使用圆心距离判断
基于半径关系判断
适用于相交和包含判断
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Solution {
public:
    // 判断两圆位置关系
    // 返回值: -2内含 -1内切 0相交 1外切 2相离
    int circlePosition(const Circle& c1, const Circle& c2) {
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        if (d < abs(r1 - r2) - EPS) return -2;  // 内含
        if (abs(d - abs(r1 - r2)) < EPS) return -1;  // 内切
        if (d < r1 + r2 + EPS) return 0;  // 相交
        if (abs(d - (r1 + r2)) < EPS) return 1;  // 外切
        return 2;  // 相离
    }
    
    // 计算两圆交点
    vector<Point> circleIntersection(const Circle& c1, const Circle& c2) {
        int pos = circlePosition(c1, c2);
        if (pos < 0 || pos > 1) return {};  // 内含、内切、相离、外切
        
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        // 余弦定理计算角度
        double angle = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
        Point v = (c2.center - c1.center).normalize() * r1;
        
        return {
            c1.center + v.rotate(angle),
            c1.center + v.rotate(-angle)
        };
    }
    
    // 计算两圆公共面积
    double commonArea(const Circle& c1, const Circle& c2) {
        int pos = circlePosition(c1, c2);
        if (pos == -2) {  // 内含
            double r = min(c1.radius, c2.radius);
            return M_PI * r * r;
        }
        if (pos >= 1) return 0;  // 外切或相离
        
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        // 余弦定理计算角度
        double angle1 = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
        double angle2 = acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d));
        
        // 扇形面积减去三角形面积
        return r1 * r1 * angle1 + r2 * r2 * angle2 - 
               d * r1 * sin(angle1);
    }
};

class Solution {
    static final double EPS = 1e-10;
    static final double PI = Math.PI;
    
    // 判断两圆位置关系
    // 返回值: -2内含 -1内切 0相交 1外切 2相离
    public int circlePosition(Circle c1, Circle c2) {
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        if (d < Math.abs(r1 - r2) - EPS) return -2;  // 内含
        if (Math.abs(d - Math.abs(r1 - r2)) < EPS) return -1;  // 内切
        if (d < r1 + r2 + EPS) return 0;  // 相交
        if (Math.abs(d - (r1 + r2)) < EPS) return 1;  // 外切
        return 2;  // 相离
    }
    
    // 计算两圆交点
    public List<Point> circleIntersection(Circle c1, Circle c2) {
        int pos = circlePosition(c1, c2);
        if (pos < 0 || pos > 1) return new ArrayList<>();
        
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        // 余弦定理计算角度
        double angle = Math.acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
        Point v = c2.center.subtract(c1.center).normalize().multiply(r1);
        
        return Arrays.asList(
            c1.center.add(v.rotate(angle)),
            c1.center.add(v.rotate(-angle))
        );
    }
    
    // 计算两圆公共面积
    public double commonArea(Circle c1, Circle c2) {
        int pos = circlePosition(c1, c2);
        if (pos == -2) {  // 内含
            double r = Math.min(c1.radius, c2.radius);
            return PI * r * r;
        }
        if (pos >= 1) return 0;  // 外切或相离
        
        double d = c1.center.distance(c2.center);
        double r1 = c1.radius, r2 = c2.radius;
        
        // 余弦定理计算角度
        double angle1 = Math.acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
        double angle2 = Math.acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d));
        
        // 扇形面积减去三角形面积
        return r1 * r1 * angle1 + r2 * r2 * angle2 - 
               d * r1 * Math.sin(angle1);
    }
}

class Solution:
    def __init__(self):
        self.EPS = 1e-10
        self.PI = math.pi
    
    # 判断两圆位置关系
    # 返回值: -2内含 -1内切 0相交 1外切 2相离
    def circle_position(self, c1: Circle, c2: Circle) -> int:
        d = c1.center.distance(c2.center)
        r1, r2 = c1.radius, c2.radius
        
        if d < abs(r1 - r2) - self.EPS:
            return -2  # 内含
        if abs(d - abs(r1 - r2)) < self.EPS:
            return -1  # 内切
        if d < r1 + r2 + self.EPS:
            return 0  # 相交
        if abs(d - (r1 + r2)) < self.EPS:
            return 1  # 外切
        return 2  # 相离
    
    # 计算两圆交点
    def circle_intersection(self, c1: Circle, c2: Circle) -> List[Point]:
        pos = self.circle_position(c1, c2)
        if pos < 0 or pos > 1:
            return []
        
        d = c1.center.distance(c2.center)
        r1, r2 = c1.radius, c2.radius
        
        # 余弦定理计算角度
        angle = math.acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d))
        v = (c2.center - c1.center).normalize() * r1
        
        return [
            c1.center + v.rotate(angle),
            c1.center + v.rotate(-angle)
        ]
    
    # 计算两圆公共面积
    def common_area(self, c1: Circle, c2: Circle) -> float:
        pos = self.circle_position(c1, c2)
        if pos == -2:  # 内含
            r = min(c1.radius, c2.radius)
            return self.PI * r * r
        if pos >= 1:
            return 0  # 外切或相离
        
        d = c1.center.distance(c2.center)
        r1, r2 = c1.radius, c2.radius
        
        # 余弦定理计算角度
        angle1 = math.acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d))
        angle2 = math.acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d))
        
        # 扇形面积减去三角形面积
        return r1 * r1 * angle1 + r2 * r2 * angle2 - \
               d * r1 * math.sin(angle1)

时间复杂度分析

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

位置关系判断	$\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:
    // 判断圆c1是否完全包含圆c2
    bool circleContains(const Circle& c1, const Circle& c2) {
        double d = c1.center.distance(c2.center);
        return d <= c1.radius - c2.radius + EPS;
    }
    
    // 计算多个圆的并集面积
    double unionArea(vector<Circle>& circles) {
        int n = circles.size();
        if (n == 0) return 0;
        
        double area = 0;
        for (int i = 0; i < (1 << n); i++) {
            double common = 0;
            int cnt = 0;
            Circle c;
            bool valid = true;
            
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    if (cnt == 0) {
                        c = circles[j];
                    } else {
                        common += commonArea(c, circles[j]);
                    }
                    cnt++;
                }
            }
            
            if (cnt > 0) {
                if (cnt % 2 == 1) {
                    area += c.area() - common;
                } else {
                    area -= common;
                }
            }
        }
        
        return area;
    }
};

class Solution {
    // 判断圆c1是否完全包含圆c2
    public boolean circleContains(Circle c1, Circle c2) {
        double d = c1.center.distance(c2.center);
        return d <= c1.radius - c2.radius + EPS;
    }
    
    // 计算多个圆的并集面积
    public double unionArea(Circle[] circles) {
        int n = circles.length;
        if (n == 0) return 0;
        
        double area = 0;
        for (int i = 0; i < (1 << n); i++) {
            double common = 0;
            int cnt = 0;
            Circle c = null;
            boolean valid = true;
            
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    if (cnt == 0) {
                        c = circles[j];
                    } else {
                        common += commonArea(c, circles[j]);
                    }
                    cnt++;
                }
            }
            
            if (cnt > 0) {
                if (cnt % 2 == 1) {
                    area += c.area() - common;
                } else {
                    area -= common;
                }
            }
        }
        
        return area;
    }
}

class Solution:
    # 判断圆c1是否完全包含圆c2
    def circle_contains(self, c1: Circle, c2: Circle) -> bool:
        d = c1.center.distance(c2.center)
        return d <= c1.radius - c2.radius + self.EPS
    
    # 计算多个圆的并集面积
    def union_area(self, circles: List[Circle]) -> float:
        n = len(circles)
        if n == 0:
            return 0
        
        area = 0
        for i in range(1 << n):
            common = 0
            cnt = 0
            c = None
            valid = True
            
            for j in range(n):
                if i & (1 << j):
                    if cnt == 0:
                        c = circles[j]
                    else:
                        common += self.common_area(c, circles[j])
                    cnt += 1
            
            if cnt > 0:
                if cnt % 2 == 1:
                    area += c.area() - common
                else:
                    area -= common
        
        return area

圆的相交集合

cpp
java
python

class Solution {
public:
    // 计算多个圆的交集面积
    double intersectionArea(vector<Circle>& circles) {
        int n = circles.size();
        if (n == 0) return 0;
        
        // 检查是否存在交集
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (circlePosition(circles[i], circles[j]) > 0) {
                    return 0;  // 存在不相交的圆
                }
            }
        }
        
        // 找到最小包含圆
        double area = circles[0].area();
        for (int i = 1; i < n; i++) {
            area = min(area, commonArea(circles[0], circles[i]));
        }
        
        return area;
    }
};

class Solution {
    // 计算多个圆的交集面积
    public double intersectionArea(Circle[] circles) {
        int n = circles.length;
        if (n == 0) return 0;
        
        // 检查是否存在交集
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (circlePosition(circles[i], circles[j]) > 0) {
                    return 0;  // 存在不相交的圆
                }
            }
        }
        
        // 找到最小包含圆
        double area = circles[0].area();
        for (int i = 1; i < n; i++) {
            area = Math.min(area, commonArea(circles[0], circles[i]));
        }
        
        return area;
    }
}

class Solution:
    # 计算多个圆的交集面积
    def intersection_area(self, circles: List[Circle]) -> float:
        n = len(circles)
        if n == 0:
            return 0
        
        # 检查是否存在交集
        for i in range(n):
            for j in range(i + 1, n):
                if self.circle_position(circles[i], circles[j]) > 0:
                    return 0  # 存在不相交的圆
        
        # 找到最小包含圆
        area = circles[0].area()
        for i in range(1, n):
            area = min(area, self.common_area(circles[0], circles[i]))
        
        return area