如何基于货架箱体质心坐标实现符合货架顺序的图排序？

问题说明 #

货架共三排，每个箱子的质心用$(x,y)$坐标表示，输入为29个$(x,y)$元组的列表，需要将其按1<<2<<3<<4……的货架顺序输出。

最初尝试用字典序排序，规则为：$(a,b) << (c,d)$ 当且仅当 $a < c$ 或 ($a = c$ 且 $b < d$)，但该方式会出现1<<3<<2这类不符合货架顺序的结果。以下是字典序排序的示例代码（注：原示例数据存在笔误，已修正）：

# 示例数据
data = [(1, 1), (2, 1), (1, 3), (2, 3)]

# 字典序排序实现
for i in range(len(data)):
    for j in range(i, len(data) - 1):
        if data[i][0] > data[j][0]:
            temp = data[j]
            data[j] = data[i]
            data[i] = temp
        else:
            if data[i][1] > data[j][1]:
                temp = data[j]
                data[j] = data[i]
                data[i] = temp

图结构思路的代码实现 #

基于图结构的思路核心：将每个箱子作为节点，同层（y坐标相同）相邻的箱子节点间建立双向边；通过节点度数或同一x列的y值数量判断是否存在垂直堆叠，最终按列优先、列内按y排序的规则输出。

步骤1：构建图结构 #

遍历所有坐标，为同层且x坐标差为固定步长的相邻箱子建立边：

def build_graph(data):
    graph = {node: [] for node in data}
    # 计算x方向的相邻步长
    x_coords = sorted({x for x, y in data})
    x_step = min(x2 - x1 for x1, x2 in zip(x_coords[:-1], x_coords[1:])) if len(x_coords) > 1 else 0

    for i in range(len(data)):
        x1, y1 = data[i]
        for j in range(i+1, len(data)):
            x2, y2 = data[j]
            # 同层且x差为步长，视为相邻节点
            if y1 == y2 and abs(x1 - x2) == x_step:
                graph[(x1, y1)].append((x2, y2))
                graph[(x2, y2)].append((x1, y1))
    return graph

步骤2：识别垂直堆叠的列 #

通过节点度数和同一x列的y值数量，确定存在垂直堆叠的列：

def find_stacked_columns(graph, data):
    stacked_x = set()
    # 度数>2的节点所在列存在垂直堆叠
    for node in graph:
        if len(graph[node]) > 2:
            stacked_x.add(node[0])
    # 同一x列有多个y值，也判定为垂直堆叠列
    x_to_ys = {}
    for x, y in data:
        x_to_ys.setdefault(x, []).append(y)
    for x, ys in x_to_ys.items():
        if len(ys) > 1:
            stacked_x.add(x)
    return stacked_x

步骤3：按货架顺序排序 #

按x列从小到大排列，每列内按y坐标从小到大排序（对应货架从下到上的堆叠顺序）：

def sort_shelf_order(data):
    graph = build_graph(data)
    # 此处stacked_x用于验证逻辑，实际排序可直接基于x分组
    stacked_x = find_stacked_columns(graph, data)
    
    # 按x分组，组内按y排序
    x_groups = {}
    for coord in data:
        x, y = coord
        x_groups.setdefault(x, []).append(coord)
    # 组内按y从小到大排序
    for x in x_groups:
        x_groups[x].sort(key=lambda item: item[1])
    # 按x顺序合并各组
    sorted_x = sorted(x_groups.keys())
    result = []
    for x in sorted_x:
        result.extend(x_groups[x])
    return result

测试示例 #

# 测试数据
data = [(1, 1), (2, 1), (1, 3), (2, 3)]
# 获取排序结果
sorted_result = sort_shelf_order(data)
print(sorted_result)
# 输出：[(1, 1), (1, 3), (2, 1), (2, 3)]，对应货架顺序1<<2<<3<<4

技术参考 #

• 基础图结构可通过Python原生字典实现，无需额外工具包；若需处理更复杂的图遍历、连通性分析，可使用networkx库。
• 核心逻辑是通过节点关系和坐标分组，区分水平相邻与垂直堆叠的箱子，最终实现符合货架摆放逻辑的排序。

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