AI面板识别算法：二维空间数据处理与排序实现

1. AI面板识别算法解析与实现

最近在准备华为OD机考时遇到一个有趣的题目——AI面板识别。这个题目考察了我们对二维空间数据处理和排序算法的理解，同时也模拟了真实场景中AI识别物体位置并进行排序的需求。下面我将详细解析这个问题的解决思路，并提供多种编程语言的实现方案。

2. 问题理解与建模

2.1 题目核心需求

我们需要处理的是AI识别到的N个指示灯面板数据，每个灯用矩形区域表示（左上角x1,y1和右下角x2,y2坐标）。目标是根据特定规则对这些灯进行排序：

1. 按行优先顺序排列（从上到下）
2. 同一行内的灯按从左到右顺序排列
3. 行的判定标准：两个灯垂直位置差不超过灯高度的一半

2.2 关键数据结构分析

每个灯包含以下属性：

• 编号（唯一标识）
• 左上角坐标(x1,y1)
• 右下角坐标(x2,y2)
• 高度（y2-y1）
• 中心点y坐标（用于行判定）

我们可以用结构体/类来表示每个灯的信息。以Python为例：

python复制class Light:
    def __init__(self, id, x1, y1, x2, y2):
        self.id = id
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        self.height = y2 - y1
        self.center_y = (y1 + y2) / 2

3. 算法设计与实现

3.1 排序算法流程

1. 初始化：读取所有灯的信息，存储在列表中
2. 循环处理：
   a. 在未排序的灯中找出y1最小的灯（最上面的灯）作为基准
   b. 找出与基准灯同一行的所有灯（垂直差≤高度/2）
   c. 对同一行的灯按x1从小到大排序
   d. 将这些灯加入结果列表并标记为已排序
3. 终止条件：所有灯都已排序

3.2 关键实现细节

行判定条件：
两个灯A和B属于同一行当且仅当：
|A.center_y - B.center_y| ≤ min(A.height, B.height)/2

这个条件确保了即使灯大小不同，只要它们的垂直位置足够接近，就视为同一行。

3.3 多语言实现

Python实现

python复制def sort_lights(lights):
    sorted_lights = []
    remaining_lights = lights.copy()
    
    while remaining_lights:
        # 找出y1最小的灯作为基准
        base = min(remaining_lights, key=lambda l: l.y1)
        base_height = base.height