技术问询：如何高效测量线段与矩形的重叠长度？

这是个在计算机图形学、几何计算中很常见的问题，我来分享一套高效的分步解决方案，逻辑清晰且时间复杂度为O(1)，完全能满足大多数场景的需求：

核心思路概述 #

线段与矩形的重叠部分，本质上是原线段的一个子线段（或空集）。我们需要：

1. 找到所有线段与矩形的有效交点（排除延长线上的交点）
2. 找出线段上位于矩形内部的端点
3. 从这些点中确定重叠子线段的两个端点，计算其长度

分步实现细节 #

1. 先实现基础几何工具函数 #

这些是后续计算的基础，要注意浮点精度问题——用一个小epsilon（比如1e-8）来处理计算误差，避免误判：

① 判断点是否在线段上

def point_on_segment(p, seg):
    (x1,y1), (x2,y2) = seg
    # 叉积判断点是否在直线上
    cross = (p[0]-x1)*(y2-y1) - (p[1]-y1)*(x2-x1)
    if abs(cross) > 1e-8:
        return False
    # 判断坐标是否在线段的包围盒内
    min_x, max_x = min(x1, x2), max(x1, x2)
    min_y, max_y = min(y1, y2), max(y1, y2)
    return (min_x - 1e-8 <= p[0] <= max_x + 1e-8) and (min_y - 1e-8 <= p[1] <= max_y + 1e-8)

② 计算两条线段的交点

返回交点坐标（无有效交点则返回None）：

def segment_intersection(seg1, seg2):
    (x1,y1), (x2,y2) = seg1
    (x3,y3), (x4,y4) = seg2
    denominator = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
    
    # 平行或重合，暂时返回None（重合情况后续单独处理）
    if abs(denominator) < 1e-8:
        return None
    
    t_num = (x1-x3)*(y3-y4) - (y1-y3)*(x3-x4)
    u_num = (x1-x3)*(y1-y2) - (y1-y3)*(x1-x2)
    t = t_num / denominator
    u = u_num / denominator
    
    # 交点在线段范围内（考虑浮点误差）
    if 0-1e-8 <= t <= 1+1e-8 and 0-1e-8 <= u <= 1+1e-8:
        x = x1 + t*(x2-x1)
        y = y1 + t*(y2-y1)
        return (x, y)
    return None

③ 判断点是否在矩形内部（含边界）

利用向量叉积，判断点是否在矩形所有边的同侧（假设矩形顶点为顺时针/逆时针排列）：

def point_in_rect(p, rect):
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    
    sign = None
    for i in range(4):
        a, b = rect[i], rect[(i+1)%4]
        cr = cross(a, b, p)
        
        # 点在边上，视为在矩形内
        if abs(cr) < 1e-8:
            return True
        
        current_sign = 1 if cr > 0 else -1
        if sign is None:
            sign = current_sign
        elif current_sign != sign:
            # 点在矩形外部
            return False
    return True

2. 计算重叠长度的主函数 #

整合上面的工具函数，收集所有有效点，最终计算重叠长度：

def compute_overlap_length(line, rect):
    (x0, y0), (x1, y1) = line
    dx, dy = x1 - x0, y1 - y0
    t_values = []
    
    # 检查线段端点是否在矩形内
    if point_in_rect((x0, y0), rect):
        t_values.append(0.0)
    if point_in_rect((x1, y1), rect):
        t_values.append(1.0)
    
    # 计算线段与矩形四条边的交点
    for i in range(4):
        rect_seg = (rect[i], rect[(i+1)%4])
        intersect = segment_intersection(line, rect_seg)
        if intersect is not None:
            # 计算交点在线段上的参数t（t∈[0,1]对应线段上的点）
            if abs(dx) > abs(dy):
                t = (intersect[0] - x0) / dx if abs(dx) > 1e-8 else 0.0
            else:
                t = (intersect[1] - y0) / dy if abs(dy) > 1e-8 else 0.0
            t_values.append(t)
    
    # 过滤无效t值，去重并排序
    t_values = sorted(list(set([round(t, 8) for t in t_values if 0-1e-8 <= t <= 1+1e-8])))
    
    # 无有效重叠点，长度为0
    if not t_values or abs(t_values[0] - t_values[-1]) < 1e-8:
        return 0.0
    
    # 计算重叠子线段的两个端点
    min_t, max_t = t_values[0], t_values[-1]
    p_min = (x0 + min_t*dx, y0 + min_t*dy)
    p_max = (x0 + max_t*dx, y0 + max_t*dy)
    
    # 返回距离
    return ((p_max[0]-p_min[0])**2 + (p_max[1]-p_min[1])**2)**0.5

特殊情况说明 #

• 线段完全在矩形内部：此时t_values会包含0和1，返回的长度就是原线段的长度
• 线段与矩形边重合：通过point_in_rect会把边上的点视为内部，结合交点计算，能正确返回重合部分的长度
• 线段与矩形相切：返回长度为0
• 无交集：返回长度为0

内容的提问来源于stack exchange，提问作者John M.