# PCB拼板算法详解

## 一、算法概述

本系统采用 **Nest算法（二维矩形装箱算法）** 作为核心算法，结合 **启发式算法** 和 **贪心算法**，实现PCB拼板的自动化优化计算。

### 核心目标

1. 在给定大料尺寸约束下，最大化PCB产出数量
2. 满足Panel尺寸范围限制（300×300 \~ 600×600 mm）
3. 提高大料利用率（目标≥60%）

***

## 二、算法流程

### 2.1 整体流程图

```
┌─────────────────────────────────────────────────────────────┐
│                     输入参数                                 │
│  PCB尺寸、大料尺寸、拼板间距、工艺边、Panel尺寸范围            │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 1: 生成所有可能的Panel配置                            │
│  - 遍历所有可能的行列组合                                   │
│  - 计算Panel尺寸并验证范围约束                              │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 2: 单一Panel方案计算                                  │
│  - 计算每个Panel在大料上的最大排版数量                       │
│  - 支持旋转优化（90°旋转）                                  │
│  - 计算利用率并过滤（≥60%）                                 │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 3: 多Panel组合方案计算                                │
│  - 2A+2B布局模式                                           │
│  - A+B布局模式                                             │
│  - 计算组合利用率并过滤                                     │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 4: 方案排序与去重                                    │
│  - 按利用率降序排序                                         │
│  - 利用率相同时按总PCB数降序                                │
│  - 去除重复方案                                            │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│                     输出结果                                 │
│  最多8个优化方案，按利用率排序                               │
└─────────────────────────────────────────────────────────────┘
```

***

## 三、核心算法详解

### 3.1 Panel配置生成算法

#### 3.1.1 尺寸计算公式

```python
# Panel宽度 = 横向PCB数 × PCB宽度 + (横向PCB数-1) × 间距 + 2 × 工艺边
panel_width = cols * pcb_w + (cols - 1) * gap + 2 * border

# Panel高度 = 纵向PCB数 × PCB高度 + (纵向PCB数-1) × 间距 + 2 × 工艺边  
panel_height = rows * pcb_h + (rows - 1) * gap + 2 * border

# Panel内PCB数量
pcb_count = cols * rows
```

#### 3.1.2 约束条件验证

```python
# Panel尺寸范围约束
valid_size = False

# 原始方向
if (panel_min_w <= panel_w <= panel_max_w) and (panel_min_h <= panel_h <= panel_max_h):
    valid_size = True
# 旋转方向
elif (panel_min_w <= panel_h <= panel_max_w) and (panel_min_h <= panel_w <= panel_max_h):
    valid_size = True

# 大料尺寸约束
if (panel.width <= material_w and panel.height <= material_h) or \
   (panel.height <= material_w and panel.width <= material_h):
    # Panel可以放入大料（考虑旋转）
```

#### 3.1.3 算法复杂度

| 维度    | 复杂度                      | 说明            |
| ----- | ------------------------ | ------------- |
| 时间复杂度 | O(max\_cols × max\_rows) | 遍历所有可能的行列组合   |
| 空间复杂度 | O(max\_cols × max\_rows) | 存储所有有效Panel配置 |

***

### 3.2 利用率计算算法

#### 3.2.1 计算公式

```python
# 利用率 = (总PCB面积 / 大料面积) × 100%
# 总PCB面积 = 总PCB数量 × 单个PCB面积
# 大料面积 = 大料宽度 × 大料高度

def calculate_utilization(total_pcb_count, pcb_w, pcb_h, material_w, material_h):
    total_pcb_area = total_pcb_count * pcb_w * pcb_h
    material_area = material_w * material_h
    return (total_pcb_area / material_area) * 100
```

#### 3.2.2 计算示例

以案例参数为例：

- PCB尺寸：130×250 mm
- 大料尺寸：1041×1245 mm
- 总PCB数：36个

```
总PCB面积 = 36 × 130 × 250 = 1,170,000 mm²
大料面积 = 1041 × 1245 = 1,296,045 mm²
利用率 = (1,170,000 / 1,296,045) × 100% ≈ 90.27%
```

***

### 3.3 单一Panel排版算法

#### 3.3.1 计算逻辑

```python
# 计算横向可放置数量
cols_in_material_w = material_w // panel.width

# 计算纵向可放置数量  
rows_in_material_h = material_h // panel.height

# 总拼板数
total_count = cols_in_material_w * rows_in_material_h

# 总PCB数
total_pcb = total_count * panel.pcb_count
```

#### 3.3.2 旋转优化

```python
# 旋转90°后重新计算
cols_in_material_w_rot = material_w // panel.height
rows_in_material_h_rot = material_h // panel.width
total_count_rot = cols_in_material_w_rot * rows_in_material_h_rot
```

#### 3.3.3 启发式策略

- **首次适应（First Fit）**：优先尝试原始方向
- **旋转优化（Rotation）**：尝试90°旋转以找到更优布局

***

### 3.4 多Panel组合算法

#### 3.4.1 2A+2B布局模式

```
布局示意图：
┌─────────┬─────────┐
│   A     │   B     │
│  Panel  │  Panel  │
├─────────┼─────────┤
│   A     │   B     │
│  Panel  │  Panel  │
└─────────┴─────────┘

布局尺寸计算：
layout_w = panel_a.width + panel_b.width
layout_h = panel_a.height + panel_b.height

总PCB数：2 × panel_a.pcb_count + 2 × panel_b.pcb_count
```

#### 3.4.2 A+B布局模式

```
布局示意图：
┌─────────┐
│   A     │
│  Panel  │
├─────────┤
│   B     │
│  Panel  │
└─────────┘

布局尺寸计算：
layout_w = max(panel_a.width, panel_b.width)
layout_h = panel_a.height + panel_b.height

总PCB数：panel_a.pcb_count + panel_b.pcb_count
```

#### 3.4.3 组合约束条件

```python
# 过滤条件1：Panel尺寸范围
(panel_min_w <= panel.width <= panel_max_w) 
and (panel_min_h <= panel.height <= panel_max_h)

# 过滤条件2：最大拼板数限制
total_count <= max_panel_count

# 过滤条件3：最小利用率限制  
utilization >= min_utilization
```

***

### 3.5 方案排序算法

#### 3.5.1 排序规则

```python
# 排序优先级（从高到低）：
# 1. 利用率（降序）
# 2. 总PCB数（降序）

results.sort(key=lambda x: (-x['utilization'], -x['total_pcb']))
```

#### 3.5.2 去重策略

```python
# 基于Panel尺寸和数量去重
unique_results = []
seen = set()

for result in results:
    if result['type'] == 'single':
        key = (result['panel_w'], result['panel_h'], result['count'])
    else:
        key = tuple((p['panel_w'], p['panel_h'], p['count']) for p in result['panels'])
    
    if key not in seen:
        seen.add(key)
        unique_results.append(result)
```

***

## 四、代码结构

### 4.1 核心类与函数

| 类/函数                                       | 功能说明               | 位置        |
| ------------------------------------------ | ------------------ | --------- |
| `Panel`                                    | Panel配置类，封装尺寸计算逻辑  | 第25-41行   |
| `generate_panels()`                        | 生成所有有效Panel配置      | 第44-95行   |
| `calculate_utilization()`                  | 计算大料利用率            | 第348-371行 |
| `optimize_panel_layout_with_utilization()` | 主优化函数，支持尺寸范围和利用率过滤 | 第374-550行 |
| `print_utilization_result()`               | 结果输出函数             | 第745-817行 |

### 4.2 关键数据结构

```python
# Panel配置
Panel = {
    'cols': 横向PCB数,
    'rows': 纵向PCB数,
    'width': Panel宽度,
    'height': Panel高度,
    'pcb_count': Panel内PCB数量
}

# 单一Panel方案
single_result = {
    'type': 'single',
    'cols': Panel横向数,
    'rows': Panel纵向数,
    'panel_w': Panel宽度,
    'panel_h': Panel高度,
    'pcb_count': 每Panel PCB数,
    'count': 大料出板数,
    'total_pcb': 总PCB数,
    'layout_w': 排版宽度,
    'layout_h': 排版高度,
    'utilization': 利用率(%),
    'rotation': 'normal' | 'rotated'
}

# 多Panel组合方案
multi_result = {
    'type': 'multi',
    'layout': '2A+2B' | 'A+B',
    'panels': [panel_info_1, panel_info_2],
    'total_pcb': 总PCB数,
    'layout_w': 排版宽度,
    'layout_h': 排版高度,
    'utilization': 利用率(%)
}
```

***

## 五、算法优化策略

### 5.1 剪枝优化

```python
# 提前终止无效搜索
if panel.width > material_w and panel.height > material_h:
    continue  # Panel过大，无法放入大料

# 最小PCB数量过滤
if panel.pcb_count < min_pcb_count:
    continue
```

### 5.2 缓存机制

```python
# 预计算所有有效Panel配置
panels = generate_panels(pcb_w, pcb_h, material_w, material_h, ...)

# 后续计算直接使用缓存结果
for panel in panels:
    # 无需重复计算Panel尺寸
```

### 5.3 优先级队列

```python
# 按利用率排序，优先处理高利用率方案
results.sort(key=lambda x: -x['utilization'])

# 限制输出数量，避免不必要的计算
return results[:max_results]
```

***

## 六、输入输出示例

### 6.1 输入参数

```python
# Panel拼板参数
pcb_w = 130          # PCB宽度
pcb_h = 250          # PCB高度
gap = 5              # 拼板间距
border = 5           # 工艺边

# Panel尺寸范围
panel_min_w = 300    # 最小宽度
panel_max_w = 600    # 最大宽度
panel_min_h = 300    # 最小高度
panel_max_h = 600    # 最大高度

# 大料参数
material_w = 1041    # 大料宽度
material_h = 1245    # 大料高度
max_panel_count = 10 # 最大拼板数
min_utilization = 60 # 最小利用率(%)
max_results = 8      # 最大输出方案数
```

### 6.2 输出结果

```
【方案1】单一Panel (利用率: 90.27%)
  Panel配置：横2 x 纵3
  Panel尺寸：515x410 mm
  每Panel PCB数：6个
  大料出板：6个
  总PCB数：36个
  排版尺寸：1030x1230 mm
  输出格式：Panel 515×410 (横2×纵3，6个PCB)，大料出板6个 → 总36个PCB
```

***

## 七、边界情况处理

### 7.1 极端尺寸约束

```python
# Panel尺寸超出范围
if panel.width > panel_max_w or panel.height > panel_max_h:
    continue

# 大料尺寸不足
if material_w < panel_min_w or material_h < panel_min_h:
    return []  # 无法生成有效方案
```

### 7.2 零值处理

```python
# 防止除零错误
if material_area == 0:
    return 0.0

# 空结果处理
if not results:
    print("错误：没有找到符合条件的Panel配置！")
```

### 7.3 重复方案去重

```python
# 基于关键特征去重
seen = set()
for result in results:
    key = generate_unique_key(result)
    if key not in seen:
        seen.add(key)
        unique_results.append(result)
```

***

## 八、性能分析

### 8.1 时间复杂度

| 步骤        | 复杂度                      | 说明                                   |
| --------- | ------------------------ | ------------------------------------ |
| Panel生成   | O(max\_cols × max\_rows) | 默认max\_cols=20, max\_rows=20，共400次迭代 |
| 单一Panel方案 | O(n)                     | n为有效Panel数量                          |
| 多Panel组合  | O(n²)                    | 双重循环遍历所有Panel组合                      |
| 排序        | O(m log m)               | m为方案总数                               |
| **总计**    | **O(n²)**                | 主要瓶颈在多Panel组合计算                      |

### 8.2 空间复杂度

| 存储对象      | 复杂度          | 说明          |
| --------- | ------------ | ----------- |
| Panel配置列表 | O(n)         | 存储所有有效Panel |
| 方案列表      | O(m)         | 存储所有候选方案    |
| **总计**    | **O(n + m)** | 线性空间复杂度     |

### 8.3 优化建议

1. **限制搜索范围**：合理设置max\_cols和max\_rows参数
2. **提前剪枝**：在生成阶段过滤无效配置
3. **并行计算**：多Panel组合计算可并行化
4. **启发式排序**：优先计算高潜力方案

***

## 九、扩展功能

### 9.1 支持的布局模式

| 模式     | 布局描述                         | 优先级 |
| ------ | ---------------------------- | --- |
| 2A+2B  | 2个A Panel + 2个B Panel（2×2布局） | 高   |
| A+B    | 1个A Panel + 1个B Panel（纵向堆叠）  | 中   |
| N×Same | N个相同Panel排版                  | 中   |
| Single | 单一Panel重复排版                  | 低   |

### 9.2 可扩展参数

| 参数        | 当前支持   | 扩展方向   |
| --------- | ------ | ------ |
| Panel尺寸范围 | 固定范围   | 可配置范围  |
| 利用率阈值     | 单一阈值   | 动态阈值   |
| 旋转角度      | 0°/90° | 任意角度   |
| 拼板间距      | 固定值    | 行列独立配置 |

***

## 十、总结

本算法系统通过以下核心技术实现PCB拼板的自动化优化：

1. **Nest算法**：实现二维矩形装箱，最大化空间利用率
2. **启发式算法**：支持旋转优化和多种布局模式
3. **贪心算法**：以利用率和PCB产出为目标进行方案选择
4. **约束过滤**：确保方案满足尺寸范围和利用率要求

算法具有良好的可扩展性，可根据实际生产需求调整参数和添加新的布局模式。