求解不重叠线段的最大数量及Python代码实现

问题描述 #

给定若干线段的坐标（格式为x1, y1, x2, y2），需要选出数量最多的互不重叠线段集合（两条线段有公共点，包括端点，即视为重叠）。

示例输入：

n=3
4 5 9 5
7 2 7 12
9 4 9 5

示例说明：三条线段分别为一条水平线段、两条垂直线段。水平线段与两条垂直线段都存在交点，而两条垂直线段无重叠，因此最多可选择2条线段。

解决思路 #

1. 线段重叠判断：实现通用的线段相交（含端点接触）判断函数，用于检测任意两条线段是否重叠。
2. 冲突矩阵构建：基于重叠判断结果，构建一个矩阵记录每对线段是否存在冲突（重叠）。
3. 最大独立集求解：通过回溯法遍历所有可能的线段组合，筛选出数量最多的无冲突线段集合（适用于线段数量较少的场景）。

Python 代码实现 #

def is_point_on_segment(px, py, x1, y1, x2, y2):
    """判断点(px, py)是否在线段(x1,y1)-(x2,y2)上"""
    # 先判断点是否在 bounding box 内
    if min(x1, x2) <= px <= max(x1, x2) and min(y1, y2) <= py <= max(y1, y2):
        # 叉积为0说明共线
        cross = (px - x1) * (y2 - y1) - (py - y1) * (x2 - x1)
        return abs(cross) < 1e-8  # 浮点精度容错
    return False

def is_overlapping(seg1, seg2):
    """判断两条线段是否重叠（含端点接触）"""
    x1, y1, x2, y2 = seg1
    x3, y3, x4, y4 = seg2

    def cross(o, a, b):
        """计算向量OA和OB的叉积"""
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    o1 = (x1, y1)
    a1 = (x2, y2)
    o2 = (x3, y3)
    a2 = (x4, y4)

    # 计算四个叉积
    c1 = cross(o1, a1, o2)
    c2 = cross(o1, a1, a2)
    c3 = cross(o2, a2, o1)
    c4 = cross(o2, a2, a1)

    # 标准相交情况：跨立
    if (c1 * c2 < -1e-8) and (c3 * c4 < -1e-8):
        return True

    # 判断端点是否在另一条线段上
    if is_point_on_segment(x3, y3, x1, y1, x2, y2):
        return True
    if is_point_on_segment(x4, y4, x1, y1, x2, y2):
        return True
    if is_point_on_segment(x1, y1, x3, y3, x4, y4):
        return True
    if is_point_on_segment(x2, y2, x3, y3, x4, y4):
        return True

    return False

def max_non_overlapping_segments(segments):
    n = len(segments)
    # 构建冲突矩阵：conflict[i][j] = True 表示线段i和j重叠
    conflict = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if is_overlapping(segments[i], segments[j]):
                conflict[i][j] = True
                conflict[j][i] = True

    max_count = 0

    def backtrack(index, current_selected):
        nonlocal max_count
        if index == n:
            if len(current_selected) > max_count:
                max_count = len(current_selected)
            return
        # 情况1：不选当前线段
        backtrack(index+1, current_selected)
        # 情况2：选当前线段，前提是和已选的都不冲突
        can_select = True
        for seg_idx in current_selected:
            if conflict[index][seg_idx]:
                can_select = False
                break
        if can_select:
            backtrack(index+1, current_selected + [index])

    backtrack(0, [])
    return max_count

# 示例测试
if __name__ == "__main__":
    # 解析输入
    n = 3
    segments = [
        (4,5,9,5),
        (7,2,7,12),
        (9,4,9,5)
    ]
    result = max_non_overlapping_segments(segments)
    print(f"最多可选择的不重叠线段数量：{result}")

代码说明 #

• is_point_on_segment：辅助函数，通过 bounding box 范围检查和叉积共线判断，确认点是否落在目标线段上。
• is_overlapping：核心判断函数，先通过叉积判断线段是否跨立相交，再检查端点是否落在另一条线段上，覆盖所有重叠场景。
• max_non_overlapping_segments：通过回溯法遍历所有可选线段组合，记录无冲突线段的最大数量，适合线段数量较少的场景；若处理大规模数据，可考虑动态规划或基于图论最大匹配转最大独立集的优化方案。

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