如何移除图中相交线段仅保留最短线段？（Python实现）

问题根源 #

你循环删不干净的核心原因是遍历原列表时直接删除元素，导致后续元素索引偏移，部分线段被跳过检查。另外，原列表按长度降序排列的顺序，和你要保留最短线段的目标逻辑不匹配，这也是出错的关键。

具体实现步骤 #

1. 先写准确保的非端点相交判断函数 #

首先得有一个能区分「端点相交」和「非端点相交」的函数，避免误判。示例Python实现如下：

def is_non_endpoint_intersect(seg1, seg2):
    # 辅助函数：计算三个点的逆时针方向
    def ccw(A, B, C):
        return (B['x'] - A['x']) * (C['y'] - A['y']) - (B['y'] - A['y']) * (C['x'] - A['x'])
    
    # 拆解两条线段的端点
    A = {'x': seg1['x1'], 'y': seg1['y1']}
    B = {'x': seg1['x2'], 'y': seg1['y2']}
    C = {'x': seg2['x1'], 'y': seg2['y1']}
    D = {'x': seg2['x2'], 'y': seg2['y2']}
    
    # 第一步：判断两条线段是否相交（不包含端点共线的情况）
    intersect = (ccw(A, B, C) * ccw(A, B, D) < 0) and (ccw(C, D, A) * ccw(C, D, B) < 0)
    if not intersect:
        return False
    
    # 第二步：排除端点相交的情况
    def point_on_segment(P, seg):
        # 判断点P是否在线段seg上（含端点）
        return (min(seg['x1'], seg['x2']) <= P['x'] <= max(seg['x1'], seg['x2']) and
                min(seg['y1'], seg['y2']) <= P['y'] <= max(seg['y1'], seg['y2']) and
                ccw({'x': seg['x1'], 'y': seg['y1']}, P, {'x': seg['x2'], 'y': seg['y2']}) == 0)
    
    # 检查任意端点是否落在对方线段上
    if (point_on_segment(A, seg2) or point_on_segment(B, seg2) or
        point_on_segment(C, seg1) or point_on_segment(D, seg1)):
        return False
    
    return True

2. 调整遍历顺序，用新列表存储结果 #

不要在原列表上直接删除，而是创建一个新的保留列表。同时把原降序列表反转成升序（从短到长），优先保留短线段——后面的长线段如果和已保留的短线段非端点相交，直接丢弃即可。示例代码：

# 假设你的原线段列表是 sorted_segments（按长度降序排列）
ascending_segments = sorted_segments[::-1]  # 反转成升序
kept_segments = []

for seg in ascending_segments:
    # 检查当前线段和所有已保留线段是否有非端点相交
    conflict = False
    for kept_seg in kept_segments:
        if is_non_endpoint_intersect(seg, kept_seg):
            conflict = True
            break
    if not conflict:
        kept_segments.append(seg)

# 如需恢复降序排列，反转结果即可
final_kept_segments = kept_segments[::-1]

3. 为什么这方法能解决问题？ #

• 用新列表存储结果，完全避免了遍历原列表时删除元素导致的索引错乱问题，不会再跳过任何线段。
• 升序遍历的逻辑刚好匹配你的需求：只要有更短的线段已经被保留，后续更长的线段如果和它非端点相交，就会被丢弃，最终每个相交组里只会留下最短的那条线段。

优化建议（可选） #

如果线段数量极大，双重循环的O(n²)复杂度会变慢，可以用空间索引（比如四叉树）快速筛选出可能和当前线段相交的候选线段，减少检查次数。但对于小规模数据，上面的基础方法足够稳定好用。

内容的提问来源于stack exchange，提问作者FRY-9C