题解 | #直线与圆交点间距#

题目链接

直线与圆交点间距

题目描述

给定一个圆心为 $O(o_x, o_y)$ 、半径为 $r$ 的圆，以及一条由两点 $P_A, P_B$ 确定的直线 $L$ 。该直线与圆交于两点（可能重合），你需要计算这两点之间的距离（即弦长）。

题目以核心代码模式提供，你需要实现 getDistance 函数。
题目保证直线与圆至少有一个交点（即不相离）。
返回值是一个 double 类型的浮点数。

示例: 输入:

Circle: center (0, 0), radius 1
Line: defined by (0, 0) and (0, 1) 输出: 2.000000 (直线穿过圆心，弦长等于直径)

解题思路

直接计算直线与圆的交点坐标会涉及复杂的二次方程求解。一个更优雅、更简单的几何方法是利用勾股定理。

我们可以将弦长、圆心到直线的距离和圆的半径联系起来，它们可以构成一个直角三角形：

斜边 (Hypotenuse): 圆的半径 $r$ 。
一个直角边 (Leg): 圆心 $O$ 到直线 $L$ 的垂直距离，记为 $d$ 。
另一个直角边 (Leg): 弦长的一半，记为 $l/2$ 。

根据勾股定理，我们有： $r^2 = d^2 + (l/2)^2$

我们的目标是求弦长 $l$ 。从上述公式可以推导出： $(l/2)^2 = r^2 - d^2$ $l/2 = \sqrt{r^2 - d^2}$ $l = 2 \times \sqrt{r^2 - d^2}$

因此，整个问题被简化为以下步骤：

计算圆心 $O$ 到直线 $L$ 的距离 $d$ 。这和我们在 noob102 中解决的点到直线距离问题完全一样。
将 $r$ 和 $d$ 代入公式 $l = 2 \sqrt{r^2 - d^2}$ 即可求出弦长。
由于题目保证直线与圆不相离，所以我们总是有 $d \le r$ ，因此 $r^2 - d^2$ 不会是负数。

算法步骤：

提取圆心 $O$ 的坐标、半径 $r$ ，以及定义直线的两点 $P_A, P_B$ 的坐标。
计算点 $O$ 到由 $P_A, P_B$ 定义的直线 $L$ 的距离 $d$ 。
计算弦长的一半：half_l = sqrt(r*r - d*d)。
返回 2 * half_l。

代码

cpp
java
python

// 辅助函数：计算点到直线的距离
double dist_point_to_line(const point& p, const line& l) {
    double xp = p.x, yp = p.y;
    double xA = l.point_A.x, yA = l.point_A.y;
    double xB = l.point_B.x, yB = l.point_B.y;
    
    double line_base = std::hypot(xA - xB, yA - yB);
    if (line_base == 0) { // 直线退化为一个点
        return std::hypot(xp - xA, yp - yA);
    }
    double numerator = std::abs((xp - xA) * (yB - yA) - (yp - yA) * (xB - xA));
    return numerator / line_base;
}

double getDistance(const Circle& circle, const line& l) {
    double d = dist_point_to_line(circle.O, l);
    double r = circle.r;
    
    double half_chord_sq = r * r - d * d;
    
    // 考虑到浮点数误差，如果结果略小于0，则视为0
    if (half_chord_sq < 0) {
        half_chord_sq = 0;
    }
    
    return 2.0 * std::sqrt(half_chord_sq);
}

// 辅助方法：计算点到直线的距离
public static double distPointToLine(Point p, Line l) {
    double xp = p.x, yp = p.y;
    double xA = l.point_A.x, yA = l.point_A.y;
    double xB = l.point_B.x, yB = l.point_B.y;

    double lineBase = Math.hypot(xA - xB, yA - yB);
    if (lineBase == 0) { // 直线退化为一个点
        return Math.hypot(xp - xA, yp - yA);
    }
    double numerator = Math.abs((xp - xA) * (yB - yA) - (yp - yA) * (xB - xA));
    return numerator / lineBase;
}

public static double getDistance(Circle circle, Line l) {
    double d = distPointToLine(circle.O, l);
    double r = circle.r;

    double halfChordSq = r * r - d * d;
    
    // 题目保证不相离，但为健壮性处理浮点误差
    if (halfChordSq < 0) {
        halfChordSq = 0;
    }

    return 2.0 * Math.sqrt(halfChordSq);
}

import math

# 辅助函数：计算点到直线的距离
def dist_point_to_line(p: Point, l: Line) -> float:
    xp, yp = p.x, p.y
    xA, yA = l.point_A.x, l.point_A.y
    xB, yB = l.point_B.x, l.point_B.y
    
    line_base = math.hypot(xA - xB, yA - yB)
    if line_base == 0:  # 直线退化为一个点
        return math.hypot(xp - xA, yp - yA)
    
    numerator = math.fabs((xp - xA) * (yB - yA) - (yp - yA) * (xB - xA))
    return numerator / line_base

def getDistance(circle: Circle, l: Line) -> float:
    d = dist_point_to_line(circle.O, l)
    r = circle.r
    
    half_chord_sq = r*r - d*d
    
    # 题目保证不相离，但为健壮性处理浮点误差
    if half_chord_sq < 0:
        half_chord_sq = 0
        
    return 2.0 * math.sqrt(half_chord_sq)

算法及复杂度

算法: 几何法（勾股定理 + 点到直线距离）
时间复杂度: $\mathcal{O}(1)$ 。所有计算都是常数次算术运算。
空间复杂度: $\mathcal{O}(1)$ 。没有使用与输入规模相关的额外空间。