如何从非直排坐标数组中筛选指定数量的相邻座位点？

核心思路 #

曲线排列的座位无法通过单一轴排序筛选相邻点，核心判断依据是点之间的空间距离足够近，且形成连续的2-4个点的群组。具体步骤如下：

• 先将嵌套的坐标数组拆分为单个(x,y)点的列表（忽略第三个无关值）
• 根据实际座位间距设置距离阈值，判定两个点是否相邻
• 构建点的邻接关系，找出所有连续连通的点群
• 筛选出长度在2-4之间的点群

代码实现（纯Python，无第三方依赖） #

def filter_adjacent_seats(arr, min_count=2, max_count=4, distance_threshold=30):
    # 1. 扁平化坐标，提取(x,y)
    all_points = []
    for sublist in arr:
        for point in sublist:
            all_points.append((point[0], point[1]))
    
    # 2. 计算每个点的相邻点
    adjacency = [[] for _ in range(len(all_points))]
    for i in range(len(all_points)):
        x1, y1 = all_points[i]
        for j in range(i+1, len(all_points)):
            x2, y2 = all_points[j]
            # 用曼哈顿距离判定，更贴合"并排"的空间逻辑
            distance = abs(x2 - x1) + abs(y2 - y1)
            if distance <= distance_threshold:
                adjacency[i].append(j)
                adjacency[j].append(i)
    
    # 3. 找出所有符合数量要求的连通点群
    visited = [False] * len(all_points)
    valid_groups = []
    for i in range(len(all_points)):
        if not visited[i]:
            # BFS遍历连通点
            queue = [i]
            visited[i] = True
            group = []
            while queue:
                idx = queue.pop(0)
                group.append(all_points[idx])
                for neighbor in adjacency[idx]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            # 筛选数量在2-4之间的组
            if min_count <= len(group) <= max_count:
                valid_groups.append(group)
    
    return valid_groups

# 测试示例曲线坐标
curve_arr = [[(534, 647, 9), (556, 647, 16), (567, 647, 9)], [(387, 644, 12), (398, 644, 9)], [(369, 613, 12), (609, 613, 28)], [(337, 597, 12)], [(658, 591, 12)], [(684, 547, 12)], [(685, 530, 20)], [(688, 525, 9)], [(693, 483, 12)], [(653, 423, 12)], [(649, 426, 180)], [(662, 432, 240)], [(652, 420, 12)], [(605, 413, 9), (637, 413, 49)], [(631, 410, 12), (653, 410, 90)], [(441, 376, 9), (450, 376, 12)], [(456, 373, 20), (567, 373, 9)]]

result = filter_adjacent_seats(curve_arr)
for group in result:
    print(group)

关键调整说明 #

• 距离阈值：可根据实际座位的间距修改distance_threshold，如果更看重直线距离，可替换为欧氏距离((x2-x1)**2 + (y2-y1)**2)**0.5
• 左右侧筛选：如果只需要右侧的合格点，可在筛选连通组时增加判断，比如只保留组内点的x坐标平均值大于某个阈值的群组
• 去重处理：若原始数组存在重复坐标，可在扁平化步骤中通过set去重后再转回列表

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