Python实现含垂直段的两条2D线段相减方案问询

需求描述 #

计算两条2D线段的差值（即line1的Y值减去line2的Y值），输出结果线段的顶点集合。输入输出线段均允许包含垂直段（X值无需严格单调递增，但不会出现X值回溯的情况）。

示例 #

输入：

# 线段以(X,Y)坐标数组表示
line1 = [(0,2), (4,2), (5,10), (15,10), (16,0), (20,0)]
line2 = [(0,2), (5,2), (10,5), (15,5), (15,0), (20,0)]

期望输出：

[(0,0), (4,0), (5,8), (10,5), (15,5), (15,10), (16,0), (20,0)]

数据说明 #

• 线段由直线段连接而成，非曲线；
• line1与line2的X值不完全重合；
• 线段X值不会回溯，但相邻点可能有相同X值（代表垂直段，如line2中X=15的两点）；
• 输出结果需支持表示垂直段。

已调研方案及问题 #

作为Python生态新手，已调研以下库，但存在局限：

• Pandas Series：仅能处理X值严格单调递增的场景，不符合当前需求；
• SymPy Geometry：理论上可能支持线段运算，但未找到明确的实现方法；
• SciPy：使用scipy.interpolate.interp1d可处理含重复X值的线段，但存在以下问题：

  # 会丢失代表垂直段的重复X值
  all_x_values = sorted(set(line1_x_values + line2_x_values))
  # 重复X值处无法区分不同Y值
  new_line_y_values = [line1(x) - line2(x) for x in all_x_values]
  # 无法提取含垂直段的结果顶点
  new_line = scipy.interpolate.interp1d(all_x_values, new_line_y_values)
  

解决方案 #

核心思路 #

1. 收集所有关键X坐标：包括两条线段的所有X值，以及两条线段中每对直线段的交点X值（若交点X在两段的X范围内）；
2. 对每个关键X坐标，分别计算line1和line2在该X处的Y值，得到差值Y；
3. 保留垂直段的重复X值（同一X对应不同Y值）；
4. 去除冗余点：若连续三点共线，则移除中间点，简化结果线段。

Python实现代码 #

def get_y_at_x(line, x):
    """给定线段和X坐标，计算对应的Y值（处理垂直段）"""
    for i in range(len(line)-1):
        x1, y1 = line[i]
        x2, y2 = line[i+1]
        
        x_min = min(x1, x2)
        x_max = max(x1, x2)
        if not (x_min <= x <= x_max):
            continue
            
        if x1 == x2:
            # 垂直段，返回对应顶点的Y值（关键X均来自顶点或交点，无需处理中间值）
            return y1 if x == x1 and i == 0 else y2
        else:
            # 非垂直段，计算线性插值Y值
            slope = (y2 - y1) / (x2 - x1)
            return y1 + slope * (x - x1)
    return None

def find_segment_intersection_x(seg1, seg2):
    """计算两条直线段的交点X坐标（仅返回在两段X范围内的有效交点）"""
    (x1, y1), (x2, y2) = seg1
    (x3, y3), (x4, y4) = seg2
    
    denom = (y2 - y1)*(x4 - x3) - (x2 - x1)*(y4 - y3)
    if denom == 0:
        # 平行或重合，无有效交点
        return None
    
    t_num = (x1 - x3)*(y4 - y3) - (y1 - y3)*(x4 - x3)
    t = t_num / denom
    u_num = (x1 - x3)*(y2 - y1) - (y1 - y3)*(x2 - x1)
    u = -u_num / denom
    
    if 0 <= t <= 1 and 0 <= u <= 1:
        return x1 + t*(x2 - x1)
    else:
        return None

def subtract_lines(line1, line2):
    """计算line1 - line2的结果线段"""
    # 收集所有关键X值
    key_x = set()
    for x, _ in line1 + line2:
        key_x.add(x)
    
    # 添加所有线段段的交点X
    for i in range(len(line1)-1):
        seg1 = (line1[i], line1[i+1])
        for j in range(len(line2)-1):
            seg2 = (line2[j], line2[j+1])
            x_intersect = find_segment_intersection_x(seg1, seg2)
            if x_intersect is not None:
                key_x.add(x_intersect)
    
    # 按X排序，生成每个X对应的Y差值集合
    sorted_x = sorted(key_x)
    x_to_ys = {}
    for x in sorted_x:
        y1 = get_y_at_x(line1, x)
        y2 = get_y_at_x(line2, x)
        if y1 is not None and y2 is not None:
            y_diff = round(y1 - y2, 6)
            x_to_ys.setdefault(x, set()).add(y_diff)
    
    # 生成初始点列表（同一X的Y值按顺序排列）
    initial_points = []
    for x in sorted_x:
        for y in sorted(x_to_ys[x]):
            initial_points.append((round(x, 6), y))
    
    # 去除共线冗余点
    def are_collinear(p1, p2, p3):
        (x1,y1), (x2,y2), (x3,y3) = p1,p2,p3
        return (y2 - y1)*(x3 - x2) == (y3 - y2)*(x2 - x1)
    
    if len(initial_points) <= 2:
        return initial_points
    
    cleaned_points = [initial_points[0]]
    for i in range(1, len(initial_points)-1):
        if not are_collinear(cleaned_points[-1], initial_points[i], initial_points[i+1]):
            cleaned_points.append(initial_points[i])
    cleaned_points.append(initial_points[-1])
    
    return cleaned_points

# 测试示例
line1 = [(0,2), (4,2), (5,10), (15,10), (16,0), (20,0)]
line2 = [(0,2), (5,2), (10,5), (15,5), (15,0), (20,0)]
result = subtract_lines(line1, line2)
print(result)

代码说明 #

• get_y_at_x：针对输入X坐标，计算线段对应位置的Y值，兼容垂直段逻辑；
• find_segment_intersection_x：检测两条直线段的有效交点，仅返回落在两段X范围内的交点X；
• subtract_lines：核心处理函数，完成关键X收集、Y差值计算、冗余点清理全流程；
• 加入四舍五入处理浮点计算误差，避免无效点生成；
• 保留垂直段的重复X值，完全符合需求格式要求。

内容的提问来源于stack exchange，提问作者asibs