266 lines
9.5 KiB
Markdown
266 lines
9.5 KiB
Markdown
# 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.
|