04-Data-Structures-and-Implementation

# LPGS Data Structures & Engineering Implementation

> **Doc Version**: v1.0.0 · **Algorithm Version**: LPGS v1.0

## 1. Core Data Structures

### 1.1 ShapeData — Shape Record

```csharp
public record ShapeData
{
    public string Type = "circle";  // "circle" | "ellipse" | "line"
    public double X, Y;            // Center coordinates (pixel space)
    public double Radius;           // Circle radius
    public double Rx, Ry;          // Ellipse/line semi-axis lengths
    public double Angle;           // Rotation angle (radians, ellipse/line only)
    public int R, G, B;            // Color components [0, 255]
    public double A;               // Opacity [0.01, 0.99]
}
```

`ShapeData` is the most fundamental data structure in LPGS, recording the complete parameters of a geometric primitive. Using C#'s `record` type, it natively supports `with` expressions for immutable copying (used in mutation).

**Design notes**:
- `circle` only uses `Radius`; `Rx`/`Ry`/`Angle` are ignored
- `ellipse` and `line` use `Rx`/`Ry`/`Angle`; `Radius` is ignored
- `line` is essentially an extremely flat ellipse (`Rx >> Ry`), sharing all ellipse geometry logic
- Colors use integer RGB + floating-point Alpha, decoupled from pixel format

### 1.2 EvalResult — Evaluation Result

```csharp
public class EvalResult
{
    public ShapeData Shape = null!;     // Shape with optimal color filled in
    public double NewTotalSSD;          // Global total SSD after applying this shape
    public double Improvement;          // oldSSD - newSSD (local improvement)
}
```

`EvalResult` encapsulates the output of shape evaluation. `NewTotalSSD` is a global metric for cross-candidate comparison; `Improvement` is a local metric reflecting the error reduction within the shape's coverage area.

### 1.3 FittingSettings — Fitting Parameters

```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. Engine State Management

### 2.1 FittingEngine Core Fields

| Field | Type | Purpose |
|-------|------|---------|
| `_targetImage` | Bitmap | Target image (GDI+ object, for display) |
| `_currentImage` | Bitmap | Current canvas image (GDI+ object, for display) |
| `_targetData` | byte[] | Target image pixel data (BGRA format, direct access) |
| `_currentData` | byte[] | Current canvas pixel data (BGRA format, direct access) |
| `_imgW, _imgH` | int | Working image dimensions (including edge padding) |
| `_totalError` | double | Current global SSD |
| `_initialError` | double | Initial SSD (for computing match percentage) |
| `_shapeCount` | int | Number of applied shapes |
| `_appliedShapes` | List\<ShapeData\> | Ordered list of applied shapes |
| `_errorGrid` | double[] | 16×16 error grid |
| `_originalAlpha` | byte[] | Original image alpha channel (for transparency processing) |
| `_edgeDistMap` | float[] | Edge distance map |
| `_inPrecisionMode` | bool | Whether in precision mode |
| `_precisionRoi` | Rectangle | ROI region for precision mode |
| `_running` | bool | Running state flag |
| `_cts` | CancellationTokenSource | Async cancellation token |

### 2.2 Double Buffering Strategy

LPGS uses a **byte array + Bitmap** double buffering strategy:

- **Computation layer**: Directly operates on `_targetData` / `_currentData` byte arrays, avoiding GDI+ encapsulation overhead
- **Display layer**: Each frame copies byte array data back to Bitmap via `Marshal.Copy`, triggering UI refresh

This design brings pixel-level operation performance close to C-level speed while retaining GDI+ display capabilities.

### 2.3 Error Grid Dirty Flag

`_errorGridDirty` is a simple boolean flag implementing a **Lazy Rebuild** pattern:

- `ApplyShape()` sets `_errorGridDirty = true` after modifying the canvas
- `SampleWeightedPosition()` checks the flag before sampling; if dirty, triggers a rebuild
- Avoids the overhead of rebuilding the grid after every `ApplyShape()` call

---

## 3. Multi-threading Implementation

### 3.1 Parallel Candidate Evaluation

`TryOneShape()` can enable parallel evaluation when the following conditions are met:

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

Parallel strategy:

1. Distribute candidates evenly across threads: `perThread = (candidates + threads - 1) / threads`
2. Each thread creates an independent `Random` instance (avoiding lock contention)
3. Each thread independently generates and evaluates candidate shapes
4. Collect each thread's local best, then select the global best

### 3.2 Thread Safety Considerations

- **Random**: Each thread uses an independent `Random` instance (`new Random(_rng.Next())`), avoiding lock contention on shared state
- **Error grid**: `BuildErrorGrid()` is called before sampling, outside the parallel region — no synchronization needed
- **_targetData / _currentData**: Read-only access — no synchronization needed
- **_appliedShapes**: Not modified within the parallel region — no synchronization needed

---

## 4. Shape Optimization

### 4.1 Optimization Process

After fitting is complete, post-processing optimization can be applied to the generated shapes:

- Check each shape's contribution to total error
- Remove shapes with negative error improvement contribution
- Support global optimization and ROI-scoped optimization
- Rebuild the canvas and update errors after optimization

### 4.2 Rebuild Process

After removing shapes, the canvas must be rebuilt:

1. Clear `_currentData` to the background color
2. Re-apply all surviving shapes in their original order
3. Recompute the total SSD
4. Mark the error grid as dirty

Rebuilding is necessary because shapes have Alpha blending dependencies — removing one shape affects the blending results of all subsequent shapes.

---

## 5. Performance Characteristics

### 5.1 Time Complexity

Given image dimensions W × H, shape count N, and candidate count C:

- **Per-step complexity**: O(C × A_shape), where A_shape is the shape's pixel area
- **Total complexity**: O(N × C × Ā), where Ā is the average shape area
- **Error grid**: O(W × H), lazy rebuild
- **Edge distance map**: O(W × H), built once

### 5.2 Memory Usage

| Data | Size (500×500 image) |
|------|---------------------|
| `_targetData` | 1 MB |
| `_currentData` | 1 MB |
| `_originalAlpha` | 250 KB |
| `_edgeDistMap` | 1 MB |
| `_errorGrid` | ~8 KB |
| `_appliedShapes` | ~20 KB (500 shapes) |

Total memory approximately 3.3 MB — negligible for modern computers.

### 5.3 Practical Performance Reference

On a 500×500 image with default parameters (MaxShapes=500, Candidates=64, Speed=5):

- Per-step time: approximately 1~5ms (depending on shape size)
- Total time for 500 shapes: approximately 5~15 seconds
- Match quality: typically 85%~95%