如何基于固定点列表A拆分移动点列表B？

背景与需求 #

现有固定点列表A（共4个点），移动点序列B为点M的位置记录。M的完整移动路径包含6段：A0→A1、A1→A2、A2→A3、A3→A2、A2→A1、A1→A2，需要将B拆分为对应的6条路径。

给定数据 #

A = [[0, 0], [0, 5], [0, 10], [5, 10]]

B = [[0, 0], [0.01, 2], [0, 4.02], [0, 5.03],
     [0, 6], [0, 8], [0, 9], [0, 10.05],
     [1, 10], [2, 10], [3, 10], [4, 10], [5, 9.97],
     [4, 10], [3, 10], [2, 10], [1, 10], [0, 10.05],
     [0, 9], [0, 8], [0, 6], [0, 5], 
     [0, 6], [0, 8], [0, 9], [0, 10]]

期望输出 #

There are 6 moving paths:
[[0, 0], [0.01, 2], [0, 4.02], [0, 5.03]]
[[0, 5.03], [0, 6], [0, 8], [0, 9], [0, 10.05]]
[[0, 10.05], [1, 10], [2, 10], [3, 10], [4, 10], [5, 9.97]]
[[5, 9.97], [4, 10], [3, 10], [2, 10], [1, 10], [0, 10.05]]
[[0, 10.05], [0, 9], [0, 8], [0, 6], [0, 5]]
[[0, 5], [0, 6], [0, 8], [0, 9], [0, 10]]

现有问题代码 #

现有Python代码仅输出3条路径，无法满足需求：

# Initialize a list to store the paths
paths = []

# Loop through the fixed points in A
for i in range(len(A)-1):
    # Initialize a list to store the current path
    path = []
    # Loop through the points in B
    for j in range(len(B)):
        # Check if the current point is between the fixed points
        if A[i] <= B[j] <= A[i+1] or A[i+1] <= B[j] <= A[i]:
            # Add the current point to the current path
            path.append(B[j])
    # Add the current path to the list of paths
    paths.append(path)

# Print the number of moving paths and the paths themselves
print("There are", len(paths), "moving paths:")
for path in paths:
    print(path)

修正方案 #

问题分析 #

1. 原代码仅遍历A的相邻点对，只能生成3条路径，未考虑反向路径和重复的正向路径；
2. 直接用列表比较A[i] <= B[j] <= A[i+1]逻辑错误，列表逐元素对比无法准确判断点是否在两点间路径上；
3. 未按B的序列顺序拆分，而是将所有符合范围的点归为同一路径，导致路径顺序混乱。

修正代码 #

# 定义6段路径的起止点（严格对应移动顺序）
segments = [
    (A[0], A[1]),
    (A[1], A[2]),
    (A[2], A[3]),
    (A[3], A[2]),
    (A[2], A[1]),
    (A[1], A[2])
]

paths = []
current_segment_idx = 0
current_path = []

# 计算两点间欧氏距离，用于判断是否接近路径终点
def calc_distance(p1, p2):
    return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5

# 遍历移动点序列，按路径段拆分
for point in B:
    start, end = segments[current_segment_idx]
    current_path.append(point)
    
    # 用距离阈值（0.1）判断是否到达当前段终点（适配浮点误差）
    if calc_distance(point, end) < 0.1:
        paths.append(current_path)
        current_segment_idx += 1
        current_path = []
        if current_segment_idx >= len(segments):
            break

# 输出结果
print("There are", len(paths), "moving paths:")
for path in paths:
    print(path)

代码说明 #

• segments明确指定6段路径的起止顺序，完全匹配需求中的移动路径；
• 用欧氏距离判断替代列表比较，解决浮点精度问题，准确识别路径终点；
• 按B的顺序逐个收集点，到达当前段终点时自动切换下一段，保证路径顺序和完整性。

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