镜面反射红蓝激光束交点计数算法问题求助

核心问题 #

红蓝两束激光从起点（位置0）射入镜面后不断反射，需要计算它们的路径交点数量。以下是两个示例：

示例1 #

red = [2, 7, 8, 15, 20]
blue = [3, 4, 5, 7, 10, 16, 21]

预期结果：7

示例2 #

red = [10, 20, 30]
blue = [1, 10, 20]

预期结果：3

我的尝试与问题 #

我通过构建起止点区间并逐一检查的方式解决了第二个示例，但这个方法无法处理第一个示例中的情况——比如当red = [2]和blue = [3]时，两者路径之间存在2个交点（已在图中标出）。希望能得到改进思路或解决方案。

现有代码 #

def count_intersections(red, blue):
    intersections = 0

    # 0 as the starting point
    red_points = [0] + red
    blue_points = [0] + blue

    # Create intervals for red beam
    red_intervals = []
    for i in range(len(red_points) - 1):
        if i % 2 == 0:
            red_intervals.append((red_points[i], red_points[i + 1], "Top"))
        else:
            red_intervals.append((red_points[i], red_points[i + 1], "Bottom"))

    # Create intervals for blue beam
    blue_intervals = []
    for i in range(len(blue_points) - 1):
        if i % 2 == 0:
            blue_intervals.append((blue_points[i], blue_points[i + 1], "Top"))
        else:
            blue_intervals.append((blue_points[i], blue_points[i + 1], "Bottom"))


    # Check all red intervals against all blue intervals
    for r_start, r_end, r_start_pos in red_intervals:
        for b_start, b_end, b_start_pos in blue_intervals:

            # Check if the intervals overlap and the paths cross
            if (r_start <= b_start and r_end >= b_end) or (r_start >= b_start and r_end <= b_end):

                print("check intersects")
                print(r_start, r_end)
                print(b_start, b_end)
                print("next")

                intersections += 1

    return intersections


red = [2, 7, 8, 15, 20]
blue = [3, 4, 5, 7, 10, 16, 21]

# red = [10, 20, 30]
# blue = [1, 10, 20]
# [(0, 10), (10, 20), (20, 30)]
# [(0, 1), (1, 10), (10, 20)]
print(count_intersections(red, blue))

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