04-数据结构与工程实现

# LPGS 数据结构与工程实现

> **文档版本**：v1.0.0 · **算法版本**：LPGS v1.0

## 1. 核心数据结构

### 1.1 ShapeData — 形状记录

```csharp
public record ShapeData
{
    public string Type = "circle";  // "circle" | "ellipse" | "line"
    public double X, Y;            // 中心坐标（像素空间）
    public double Radius;           // 圆形半径
    public double Rx, Ry;          // 椭圆/细线的半轴长
    public double Angle;           // 旋转角度（弧度，仅椭圆/细线有效）
    public int R, G, B;            // 颜色分量 [0, 255]
    public double A;               // 透明度 [0.01, 0.99]
}
```

`ShapeData` 是 LPGS 中最核心的数据结构，记录一个几何基元的完整参数。使用 C# 的 `record` 类型，天然支持 `with` 表达式进行不可变复制（用于变异）。

**设计要点**：
- `circle` 只使用 `Radius`，`Rx`/`Ry`/`Angle` 被忽略
- `ellipse` 和 `line` 使用 `Rx`/`Ry`/`Angle`，`Radius` 被忽略
- `line` 本质上是极扁的椭圆（`Rx >> Ry`），共享椭圆的所有几何逻辑
- 颜色使用整数 RGB + 浮点 Alpha，与像素格式解耦

### 1.2 EvalResult — 评估结果

```csharp
public class EvalResult
{
    public ShapeData Shape = null!;     // 填充了最优颜色的形状
    public double NewTotalSSD;          // 应用该形状后的全局总 SSD
    public double Improvement;          // oldSSD - newSSD（局部改进量）
}
```

`EvalResult` 封装了形状评估的输出。`NewTotalSSD` 是全局指标，用于候选间的横向比较；`Improvement` 是局部指标，反映形状在其覆盖区域内的误差削减量。

### 1.3 FittingSettings — 拟合参数

```csharp
public class FittingSettings
{
    public int MaxShapes = 500;
    public int Candidates = 64;
    public int Speed = 5;
    public double ReserveRatio = 20;
    public bool EnableCircle = true;
    public bool EnableEllipse = true;
    public bool EnableLine = true;
    public bool PreserveTransparency = false;
    public int BgColorIndex = 0;
    public int AlphaThreshold = 128;
    public bool EdgeAwareMode = false;
    public double ScaleFactor = 0;
}
```

---

## 2. 引擎状态管理

### 2.1 FittingEngine 核心字段

| 字段 | 类型 | 用途 |
|------|------|------|
| `_targetImage` | Bitmap | 目标图像（GDI+ 对象，用于显示） |
| `_currentImage` | Bitmap | 当前画布图像（GDI+ 对象，用于显示） |
| `_targetData` | byte[] | 目标图像的像素数据（BGRA 格式，直接操作） |
| `_currentData` | byte[] | 当前画布的像素数据（BGRA 格式，直接操作） |
| `_imgW, _imgH` | int | 工作图像尺寸（含边缘填充） |
| `_totalError` | double | 当前全局 SSD |
| `_initialError` | double | 初始 SSD（用于计算匹配百分比） |
| `_shapeCount` | int | 已应用的形状数 |
| `_appliedShapes` | List\<ShapeData\> | 已应用形状的有序列表 |
| `_errorGrid` | double[] | 16×16 误差网格 |
| `_originalAlpha` | byte[] | 原始图像的 Alpha 通道（用于透明度处理） |
| `_edgeDistMap` | float[] | 边缘距离图 |
| `_inPrecisionMode` | bool | 是否处于精度模式 |
| `_precisionRoi` | Rectangle | 精度模式的 ROI 区域 |
| `_running` | bool | 运行状态标志 |
| `_cts` | CancellationTokenSource | 异步取消令牌 |

### 2.2 双缓冲策略

LPGS 使用**字节数组 + Bitmap** 的双缓冲策略：

- **计算层**：直接操作 `_targetData` / `_currentData` 字节数组，避免 GDI+ 的封装开销
- **显示层**：每帧将字节数组通过 `Marshal.Copy` 写回 Bitmap，触发 UI 刷新

这种设计将像素级操作的性能提升到接近 C 语言的水平，同时保留了 GDI+ 的显示能力。

### 2.3 误差网格脏标记

`_errorGridDirty` 是一个简单的布尔标志，实现了**惰性重建**（Lazy Rebuild）模式：

- `ApplyShape()` 修改画布后，置 `_errorGridDirty = true`
- `SampleWeightedPosition()` 采样前检查，若脏则重建
- 避免了每次 `ApplyShape()` 后都重建网格的开销

---

## 3. 多线程实现

### 3.1 并行候选评估

`TryOneShape()` 在以下条件满足时可启用并行评估：

```
numCandidates > 16 && Environment.ProcessorCount > 1
```

并行策略：

1. 将候选数均匀分配到各线程：`perThread = (candidates + threads - 1) / threads`
2. 每个线程创建独立的 `Random` 实例（避免锁竞争）
3. 每个线程独立生成和评估候选形状
4. 收集各线程的局部最优，选择全局最优

### 3.2 线程安全考量

- **Random**：每个线程使用独立的 `Random` 实例（`new Random(_rng.Next())`），避免共享状态的锁竞争
- **误差网格**：`BuildErrorGrid()` 在采样前调用，不在并行区域内，无需同步
- **_targetData / _currentData**：只读访问，无需同步
- **_appliedShapes**：不在并行区域内修改，无需同步

---

## 4. 对象优化

### 4.1 优化流程

拟合完成后，可以对已生成的形状进行后处理优化：

- 逐个检查形状对总误差的贡献
- 移除对误差改进贡献为负的形状
- 支持全局优化和 ROI 范围内优化
- 优化后重建画布并更新误差

### 4.2 重建流程

移除形状后需要重建画布：

1. 清空 `_currentData` 为背景色
2. 按原始顺序重新应用所有存活形状
3. 重新计算总 SSD
4. 标记误差网格为脏

重建是必要的，因为形状之间存在 Alpha 混合的依赖关系——移除一个形状会影响后续所有形状的混合结果。

---

## 5. 性能特征

### 5.1 时间复杂度

设图像尺寸为 W × H，形状数为 N，候选数为 C：

- **单步复杂度**：O(C × A_shape)，其中 A_shape 是形状的像素面积
- **总复杂度**：O(N × C × Ā)，其中 Ā 是平均形状面积
- **误差网格**：O(W × H)，惰性重建
- **边缘距离图**：O(W × H)，仅构建一次

### 5.2 内存占用

| 数据 | 大小（500×500 图像） |
|------|---------------------|
| `_targetData` | 1 MB |
| `_currentData` | 1 MB |
| `_originalAlpha` | 250 KB |
| `_edgeDistMap` | 1 MB |
| `_errorGrid` | ~8 KB |
| `_appliedShapes` | ~20 KB（500 形状） |

总内存约 3.3 MB，对现代计算机无压力。

### 5.3 实际性能参考

在 500×500 图像上，默认参数（MaxShapes=500, Candidates=64, Speed=5）：

- 单步耗时：约 1~5ms（取决于形状大小）
- 500 形状总耗时：约 5~15 秒
- 匹配度：通常可达 85%~95%