Python实现圆内相交弦计数：代码返回结果异常求助

我尝试用Python实现线扫描算法计算圆内相交弦的数量，但测试示例返回6，正确结果应为1。输入是两个平行列表：第一个是升序排列的弧度值，第二个是弦的标识符（sX代表起点，eX代表终点）。原代码如下：

def count_intersections(radians, identifiers):
    events = []
    for i in range(len(radians)):
        events.append((radians[i], 'start', identifiers[0][i]))
        events.append((radians[i], 'end', identifiers[0][i]))

    events.sort(key=lambda x: (x[0], x[1]))

    active_chords = []
    intersections = 0

    for event in events:
        _, event_type, identifier = event

        if event_type == 'start':
            intersections += len(active_chords)
            active_chords.append(identifier)
        else:
            if identifier in active_chords:
                active_chords.remove(identifier)

    return intersections

# Example usage:
radians = [0.78, 1.47, 1.77, 3.92]
identifiers = [["s1", "s2", "e1", "e2"]]
result = count_intersections(radians, identifiers)
print(result)

错误分析 #

原代码的核心问题在于事件生成逻辑完全错误：

• 每个弧度点被重复生成了start和end两个事件，导致事件数量翻倍，后续排序和处理逻辑彻底混乱。
• 没有正确区分每个标识符对应的事件类型（sX是起点，eX是终点），而是强行给每个点绑定两种事件。
• 活跃列表存储的是原始标识符（如s1、e1），而非统一的弦ID，导致终点事件无法匹配到对应的起点。

修复后的代码 #

def count_intersections(radians, identifiers):
    events = []
    # 正确生成事件：每个点对应一个事件，区分起点/终点，提取统一弦ID
    for i in range(len(radians)):
        id_str = identifiers[0][i]
        chord_id = id_str[1:]  # 从s1/e1中提取弦编号1
        event_type = 'start' if id_str.startswith('s') else 'end'
        events.append((radians[i], event_type, chord_id))
    
    # 排序规则：按弧度升序；弧度相同时，终点事件优先于起点事件（避免同点误判）
    events.sort(key=lambda x: (x[0], 0 if x[1] == 'end' else 1))
    
    active_chords = []
    intersections = 0

    for event in events:
        _, event_type, chord_id = event

        if event_type == 'start':
            # 起点事件：加入活跃列表
            active_chords.append(chord_id)
        else:
            # 终点事件：找到当前弦在活跃列表中的位置，统计其后方的弦数量（这些就是相交的弦）
            if chord_id in active_chords:
                idx = active_chords.index(chord_id)
                # 活跃列表中在当前弦起点之后加入的弦，必然与当前弦相交
                intersections += len(active_chords) - idx - 1
                active_chords.pop(idx)

    return intersections

# 测试示例
radians = [0.78, 1.47, 1.77, 3.92]
identifiers = [["s1", "s2", "e1", "e2"]]
result = count_intersections(radians, identifiers)
print(result)  # 输出：1

关键修改说明 #

1. 正确生成事件：根据标识符前缀s/e判断事件类型，提取统一的弦ID（如s1和e1都对应弦1），每个弧度点仅生成一个事件。
2. 优化排序规则：当两个事件弧度相同时，终点事件优先处理，避免同位置的点被误判为相交。
3. 修正相交计数逻辑：处理终点事件时，找到该弦在活跃列表中的位置，其后方的弦都是起点在当前弦起点之后、尚未结束的弦，这些弦必然与当前弦相交，统计数量即可。

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