D4 canonicalization and orientation analysis for polyominoes

polyomino.js

/*
 * polyomino.js — D4 canonicalization and orientation analysis for polyominoes.
 *
 * A polyomino is represented as an array of [row, col] integer pairs.
 * No assumption about the grid it came from; coordinates can be any integers.
 *
 * Signatures are strings like "0,0|0,1|1,0" (an L-tromino), produced by
 * normalizing cells to origin and sorting them lexicographically. Two shapes
 * have the same signature iff they have the same cell layout at the same
 * translation; they have the same CANONICAL signature iff they are related
 * by any rotation or reflection (D4 group).
 *
 * The 8 transforms of the D4 group, indexed 0..7:
 *   0: identity         [ r,  c]
 *   1: rotate 90° CW    [ c, -r]
 *   2: rotate 180°      [-r, -c]
 *   3: rotate 270° CW   [-c,  r]
 *   4: reflect (h-flip) [ r, -c]
 *   5: reflect + rot 90 [ c,  r]
 *   6: reflect + rot180 [-r,  c]
 *   7: reflect + rot270 [-c, -r]
 */
(function (root) {
    'use strict';

    // ---- core transforms ----

    function normalize(cells) {
        let minR = Infinity, minC = Infinity;
        for (const [r, c] of cells) {
            if (r < minR) minR = r;
            if (c < minC) minC = c;
        }
        return cells
            .map(([r, c]) => [r - minR, c - minC])
            .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    }

    function toSig(cells) {
        return normalize(cells).map(([r, c]) => r + ',' + c).join('|');
    }

    function parseSig(sig) {
        return sig.split('|').map(s => {
            const p = s.split(',');
            return [+p[0], +p[1]];
        });
    }

    function rotate90(cells) {
        return cells.map(([r, c]) => [c, -r]);
    }

    function reflect(cells) {
        return cells.map(([r, c]) => [r, -c]);
    }

    // The 8 D4 transforms as pure functions, indexed to match the doc above.
    const D4 = [
        cells => cells.map(([r, c]) => [ r,  c]),
        cells => cells.map(([r, c]) => [ c, -r]),
        cells => cells.map(([r, c]) => [-r, -c]),
        cells => cells.map(([r, c]) => [-c,  r]),
        cells => cells.map(([r, c]) => [ r, -c]),
        cells => cells.map(([r, c]) => [ c,  r]),
        cells => cells.map(([r, c]) => [-r,  c]),
        cells => cells.map(([r, c]) => [-c, -r]),
    ];

    // ---- canonicalization ----

    /**
     * Canonical signature = lex-smallest signature across all 8 D4 transforms.
     * Two cell sets produce the same canonical signature iff they are the same
     * shape up to rotation and reflection.
     */
    function canonical(cells) {
        let best = null;
        for (let i = 0; i < 8; i++) {
            const s = toSig(D4[i](cells));
            if (best === null || s < best) best = s;
        }
        return best;
    }

    // ---- orientation analysis ----

    /**
     * Given a cell set, return an 8-bit mask indicating which D4 transforms
     * of the canonical form reproduce the input orientation. For asymmetric
     * shapes exactly one bit is set. For symmetric shapes (e.g. a square)
     * multiple bits are set because several transforms map to the same layout.
     */
    function orientationMask(cells) {
        const canonCells = parseSig(canonical(cells));
        const target = toSig(cells);
        let mask = 0;
        for (let i = 0; i < 8; i++) {
            if (toSig(D4[i](canonCells)) === target) {
                mask |= (1 << i);
            }
        }
        return mask >>> 0;
    }

    /**
     * The full set of distinct orientations a shape's family produces.
     * For a fully asymmetric polyomino this is 0xFF (all 8 orientations distinct).
     * For shapes with symmetry, fewer bits are set — e.g. a 2x2 square returns
     * 0x01 because every D4 transform produces the same layout.
     *
     * popcount(familyMask(cells)) is the size of the orbit under D4, i.e. the
     * number of visually distinct orientations of this shape.
     */
    function familyMask(cells) {
        const canonCells = parseSig(canonical(cells));
        const seen = new Set();
        let mask = 0;
        for (let i = 0; i < 8; i++) {
            const sig = toSig(D4[i](canonCells));
            if (seen.has(sig)) continue;
            seen.add(sig);
            mask |= (1 << i);
        }
        return mask >>> 0;
    }

    // ---- bit helpers (generic, but useful when working with the masks above) ----

    function popcount(v) {
        v = v >>> 0;
        v = v - ((v >>> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >>> 2) & 0x33333333);
        return (((v + (v >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
    }

    // ---- export ----

    const Polyomino = {
        normalize,
        toSig,
        parseSig,
        rotate90,
        reflect,
        canonical,
        orientationMask,
        familyMask,
        popcount,
        D4,
    };

    if (typeof module !== 'undefined' && module.exports) {
        module.exports = Polyomino;
    } else {
        root.Polyomino = Polyomino;
    }
})(typeof self !== 'undefined' ? self : this);