# Design: `@suaveplan/emblem-solver`

> Non-normative companion to `specs/emblem-solver/spec.md`. Architecture,
> algorithm sketches, file layout, and rationale. The requirements live in
> the spec delta.

## Goals

- Pure, universal-tier TypeScript. Zero browser / Node / React APIs in the
  runtime hot path.
- Single public entry point `convert(pixels, width, height, options?)` that
  decomposes an opaque-pixel grid into the minimum number of axis-aligned
  rectangles, layered with z-index, and serialised to a `<svg>` string.
- Deterministic given inputs + an injected `Rng` (defaults to `Math.random`).
- Tree-shakeable: subpath exports for `./types`, `./errors`, `./grid`,
  `./io`, `./svg`.

## Tier discipline

Universal means no `window`, `document`, `navigator`, `fs`, `path`,
`process`. All inputs are JS values (`RGBA[]`, `Uint8Array`, `number[][]`);
output is a `string` + plain data structures. No DOM is created.

## Public surface

Exported from the package root (`@suaveplan/emblem-solver`):

| Symbol | Kind | Purpose |
|---|---|---|
| `convert` | fn | Decompose grid → `ConvertResult` |
| `analyseGrid` | fn | Diagnostic colour/island analysis |
| `parseRGBABuffer` | fn | `Uint8Array` (RGBA bytes) → `RGBA[]` |
| `fromIndexedGrid` | fn | `number[][]` + palette → grid |
| `buildSVG` | fn | `ColourLayer[]` → `<svg>` string |
| `EmblemSolverError` | class | Base error |
| `EMBLEM_SOLVER_CODES` | const | `defineCodes("EMBLEM_SOLVER", …)` |
| `ConvertOptionsSchema` | const | Zod schema for `ConvertOptions` |
| `RGBA`, `Rect`, `Island`, `ColourAnalysis`, `ColourLayer`, `ConvertOptions`, `ConvertResult`, `GridAnalysis` | types | Public type surface |

Subpath exports: `./types`, `./errors`, `./schemas`, `./grid`, `./io`,
`./svg`, `./solver` (for advanced consumers wiring custom orderings).

## File layout

```text
packages/media/image/emblem-solver/
  package.json                          # 0.1.0, sideEffects: false
  tsconfig.lib.json
  vite.config.ts
  vitest.config.ts
  README.md
  src/
    index.ts                            # root barrel (named re-exports)
    types/
      types.ts                          # RGBA, Rect, Island, ColourAnalysis, …
      types.md
    errors/
      errors.ts                         # defineCodes + EmblemSolverError
      errors.test.ts
      errors.md
      index.ts
    schemas/
      schemas.ts                        # Zod schemas (ConvertOptionsSchema)
      schemas.test.ts
      schemas.md
      index.ts
    helpers/
      helpers.ts                        # pack/unpack/keys/grids/bounds
      helpers.test.ts
      helpers.md
      index.ts
    grid/
      analyse/
        analyse.ts                      # analyseGrid + flood-fill islands
        analyse.test.ts
        analyse.md
        index.ts
      index.ts
    io/
      parse/
        parse.ts                        # parseRGBABuffer + fromIndexedGrid
        parse.test.ts
        parse.md
        index.ts
      index.ts
    solver/
      greedy/
        greedy.ts                       # enhancedGreedyCover + perIslandCover
        greedy.test.ts
        greedy.md
        index.ts
      histogram/
        histogram.ts                    # dualAxisMaximalRects
        histogram.test.ts
        histogram.md
        index.ts
      strip/
        strip.ts                        # stripDecomposition (h + v)
        strip.test.ts
        strip.md
        index.ts
      ordering/
        ordering.ts                     # permutations + factorial + getStaticOrdering
        ordering.test.ts
        ordering.md
        index.ts
      layer/
        layer.ts                        # processLayerMultiStrategy
        layer.test.ts
        layer.md
        index.ts
      index.ts
    optimizer/
      merge/
        merge.ts                        # mergeAdjacentRects
        merge.test.ts
        merge.md
        index.ts
      overlap/
        overlap.ts                      # bboxMerge, extendToSubsume, crossReplace
        overlap.test.ts
        overlap.md
        index.ts
      redundancy/
        redundancy.ts                   # eliminateRedundant across layers
        redundancy.test.ts
        redundancy.md
        index.ts
      index.ts
    svg/
      build/
        build.ts                        # buildSVG
        build.test.ts
        build.md
        index.ts
      index.ts
    telemetry/
      telemetry.ts                      # lazy OTel counter + histogram
      telemetry.test.ts
      telemetry.md
      index.ts
    fixtures/
      fixtures.ts                       # canonical test grids
      fixtures.md
      index.ts
    converter/
      converter.ts                      # public convert() orchestrator
      converter.test.ts                 # the canonical regression suite
      converter.md
      index.ts
```

Each non-`.test.ts` `.ts` has a sibling `.md` ≥ 200 words.

## Algorithm overview

Upstream's pipeline, preserved verbatim:

1. **`analyseGrid`** — Walk the RGBA grid. For each opaque pixel
   (`a === 1`), record it in `opaquePixels` and bucket by colour key
   (`"r,g,b"`). For each colour bucket, flood-fill with 4-connected BFS to
   recover `Island[]`, compute bounds, density (`pixels / bbox area`), and
   fragmentation (`islands / pixels`).
2. **Ordering search** — pick a z-stacking order over the colours.
   - `auto` mode: if `colourCount! ≤ maxPermutations` (default 40320 = 8!),
     enumerate all permutations via Heap's algorithm. Otherwise evaluate the
     four static heuristics plus up to 1000 random shuffles (using the
     injected `Rng`).
   - Explicit modes: `area-desc`, `area-asc`, `island-aware`,
     `perimeter-desc`.
3. **Per-ordering layer build** — for each colour in the ordering, build an
   `available` grid (opaque pixels minus earlier-layer pixels) and a
   `required` grid (this colour's pixels). Run four covering strategies:
   - **A. Dual-axis histogram → greedy → overlap optimise**:
     `dualAxisMaximalRects` enumerates every maximal rect in `available` by
     sweeping both axes via the classic "largest rectangle in histogram"
     stack algorithm; `enhancedGreedyCover` selects rects with a three-key
     score (covered count, efficiency, centroid proximity);
     `optimiseOverlap` pairwise-merges bboxes, extends rects to subsume
     neighbours, and replaces 3 rects with 2 cross/T/L patterns.
   - **B. Per-island cover** (only if >1 island): same greedy, run
     independently on each island so spanning rects between disconnected
     islands aren't considered.
   - **C. Strip decomposition**: maximal horizontal runs merged vertically
     when same-extent + adjacent, and the transposed variant; keep whichever
     produces fewer rects, but only adopt it if the strips fully cover the
     required pixels.
   - **D. Adjacent-rect merge pass** on the best result so far.

   Best = fewest rects.
4. **Redundancy elimination across layers** — after all layers are built,
   composite them top-down into a per-pixel colour grid and remove any rect
   that is fully occluded by higher-z rects of any colour or by other rects
   in the same layer.
5. **`buildSVG`** — sort layers by `zIndex` ascending and emit
   `<svg viewBox="0 0 W H" shape-rendering="crispEdges">…</svg>` with one
   `<rect>` per layer-rect, fill = `rgb(r,g,b)`. Bottom layer is drawn
   first, so layer 0 is the background and higher z-indexes overdraw.

## Options + validation

```ts
import z from "zod";

export const ConvertOptionsSchema = z
    .object({
        layerOrder: z
            .enum(["auto", "area-desc", "area-asc", "island-aware", "perimeter-desc"])
            .default("auto"),
        maxPermutations: z.number().int().min(1).default(40320),
        rng: z.custom<() => number>((v) => typeof v === "function").optional(),
    })
    .strict();
```

`convert` calls `ConvertOptionsSchema.safeParse`; failure → `EmblemSolverError(INVALID_OPTIONS, …)`.
Invalid grid dimensions (`width ≤ 0`, `height ≤ 0`, `pixels.length !== width*height`) → `INVALID_GRID`.

## Error codes

```ts
defineCodes("EMBLEM_SOLVER", [
    "INVALID_GRID",
    "INVALID_OPTIONS",
    "INVALID_PIXEL",
] as const);
```

Each code is reachable from a test.

## OTel instrumentation

Lazy-initialised on first `convert()` call (no module-load side effects):

- Counter `emblem_solver.convert.total`
- Histogram `emblem_solver.convert.duration_ms` (unit: `ms`)

## Determinism

The only random site upstream is the `auto`-mode shuffle for >8 colours. We
inject `rng: () => number` (default `Math.random`); tests pass a seeded
Mulberry32 to verify the heuristic branch is reachable + stable.

## Tests

- Port the upstream regression suite verbatim (chessboard 8×8 ≤ 33,
  cross 3×3 ≤ 2, cross 6×6 ≤ 2, T-shape ≤ 2, donut 5×5 ≤ 4, circle 16 ≤ 5,
  star ratio > 3, flag crosses ≤ 5, multi-island stripes ≤ 3, shield 32×32
  ratio > 50, crest 12×12 ratio > 3).
- Edge cases: solid 4×4 = 1, all-transparent = 0, single pixel = 1, SVG
  structure contains required tags, `auto` evaluates 3! = 6 orderings on
  the 3-colour flag, `auto` beats any single static strategy on the crest.
- Property-based via `fast-check`: any random solid-colour grid satisfies
  "every required pixel is covered by at least one rect in its layer and
  no rect leaks outside the opaque mask"; SVG output round-trips the
  composited layers back to the original pixel grid.
- Schema tests: every error code is reachable; Zod refines `maxPermutations
  ≥ 1`; unknown options rejected by `.strict()`.

## Out of scope

- PNG decoding: callers feed `RGBA[]` directly or via `parseRGBABuffer`.
- Path-based SVG (curves / `<path d>`): emblems are pixel-grid → axis-aligned
  rects only.
- Multi-frame animation.