Some bitmask helpers

bitmaskHelpers.ts

import SparseBitmask, {
  unionRunEnds,
  intersectionRunEnds,
  subtractionRunEnds,
} from "./SparseBitmask";
import Bitmask from "./Bitmask";
import { memoized, numberHasher } from "./memo";
import { OrderedSet } from "./OrderedCollections";

interface TransformedPolygon {
  toOutline(): Bitmask;
  toFill(): Bitmask;
  computeFlipsFromPolygonToMask(mask: Bitmask): number[][];
}

interface TransformedToSparse {
  toOutline(): SparseBitmask;
  toFill(): SparseBitmask;
}

const enum FillState {
  Green,
  Red,
  Yellow,
  Blue,
}

const FILL_STATE_MACHINE: Record<FillState, Record<number, FillState>> = {
  [FillState.Green]: {
    3: FillState.Blue,
    5: FillState.Red,
    6: FillState.Yellow,
  },
  [FillState.Red]: {
    3: FillState.Yellow,
    5: FillState.Green,
    6: FillState.Blue,
  },
  [FillState.Yellow]: {
    12: FillState.Green,
    15: FillState.Blue,
    9: FillState.Red,
    10: FillState.Yellow,
  },
  [FillState.Blue]: {
    12: FillState.Red,
    15: FillState.Yellow,
    9: FillState.Green,
    10: FillState.Blue,
  },
};

const memoizedDrawLine = memoized(drawLine, numberHasher(4), 500);

export function transformPolygonToSparse(
  polygon: [number, number][][],
  width: number,
  height: number
): TransformedToSparse {
  const visited: number[][] = polygon.map(() => []);
  const startIndices: number[][] = polygon.map(() => []);

  polygon.forEach((ring, ringIndex) => {
    for (let k = 0; k < ring.length; k += 1) {
      const [x1, y1] = ring[k];
      const [x2, y2] = k < ring.length - 1 ? ring[k + 1] : ring[0];
      startIndices[ringIndex].push(visited[ringIndex].length);
      memoizedDrawLine(x1, y1, x2, y2).forEach(([i, j]) =>
        visited[ringIndex].push(j * width + i)
      );
    }
  });

  const adjacentPixels = new Map<number, number>();
  visited.forEach(ring => {
    adjacentPixelsFromRing(ring, width, adjacentPixels);
  });

  return outlineAndFillFromAdjacentPixels(adjacentPixels, width, height);
}

export function transformPolygon(
  polygon: [number, number][][],
  width: number,
  height: number
): TransformedPolygon {
  const visited: number[][] = polygon.map(() => []);
  const startIndices: number[][] = polygon.map(() => []);

  polygon.forEach((ring, ringIndex) => {
    for (let k = 0; k < ring.length; k += 1) {
      const [x1, y1] = ring[k];
      const [x2, y2] = k < ring.length - 1 ? ring[k + 1] : ring[0];
      startIndices[ringIndex].push(visited[ringIndex].length);
      memoizedDrawLine(x1, y1, x2, y2).forEach(([i, j]) =>
        visited[ringIndex].push(j * width + i)
      );
    }
  });

  const pixelToNode = new Uint16Array(width * height);
  const adjacentPixel = new Bitmask(width * height * 4);
  let node = 0;
  let j = 0;
  visited.forEach((ring, ringIndex) => {
    ring.forEach((pixel, i) => {
      if (
        j < startIndices[ringIndex].length &&
        i === startIndices[ringIndex][j]
      ) {
        node += 1;
        j += 1;
      }
      if (pixelToNode[pixel] === 0) pixelToNode[pixel] = node;

      const prevPixel = i > 0 ? ring[i - 1] : ring[ring.length - 1];
      if (pixel - prevPixel === width) {
        adjacentPixel.flip(pixel * 4);
        adjacentPixel.flip(prevPixel * 4 + 2);
      }
      if (pixel - prevPixel === 1) {
        adjacentPixel.flip(pixel * 4 + 3);
        adjacentPixel.flip(prevPixel * 4 + 1);
      }
      if (prevPixel - pixel === width) {
        adjacentPixel.flip(pixel * 4 + 2);
        adjacentPixel.flip(prevPixel * 4);
      }
      if (prevPixel - pixel === 1) {
        adjacentPixel.flip(pixel * 4 + 1);
        adjacentPixel.flip(prevPixel * 4 + 3);
      }
    });
  });

  let outline!: Bitmask;
  let fill!: Bitmask;
  const cachedFlips = new Map<Bitmask, number[][]>();

  return {
    toOutline() {
      if (!outline) {
        outline = new Bitmask(width * height);
        pixelToNode.forEach((n, pixel) => {
          if (n > 0) outline.set(pixel, 1);
        });
      }
      return outline;
    },
    toFill() {
      if (!fill) {
        fill = this.toOutline().clone();
        for (let j = 0; j < height; j += 1) {
          let state = FillState.Green;
          for (let i = 0; i < width; i += 1) {
            const pixel = j * width + i;
            const painted = fill.get(pixel);
            if (painted) {
              const junction = adjacentPixel.get(pixel * 4, 4);
              state = FILL_STATE_MACHINE[state][junction] ?? state;
            } else if (state !== FillState.Green) {
              fill.set(pixel, 1);
            }
          }
        }
      }
      return fill;
    },
  };
}

export function drawLine(
  x1: number,
  y1: number,
  x2: number,
  y2: number
): [number, number][] {
  let i = Math.floor(x1);
  let j = Math.floor(y1);
  const iEnd = Math.floor(x2);
  const jEnd = Math.floor(y2);

  const dx = Math.abs(x2 - x1);
  const dy = Math.abs(y2 - y1);
  const di = x2 >= x1 ? 1 : -1;
  const dj = y2 >= y1 ? 1 : -1;

  let lhs = dx * (y2 >= y1 ? j + 1 - y1 : y1 - j);
  let rhs = dy * (x2 >= x1 ? i + 1 - x1 : x1 - i);

  const visited: [number, number][] = [];

  visited.push([i, j]);
  while (i !== iEnd || j !== jEnd) {
    if (lhs < rhs) {
      j += dj;
      lhs += dx;
    } else if (lhs > rhs) {
      i += di;
      rhs += dy;
    } else if (dj > 0) {
      j += dj;
      lhs += dx;
    } else {
      i += di;
      rhs += dy;
    }
    visited.push([i, j]);
  }

  return visited;
}

export function drawCircle(n: number): number[] {
  /*
    Using a digital differential analyzer to compute the circle edge efficiently without trigonometry, or Pythagoras.
    Start from the left edge and draw in a clockwise direction one pixel at a time until x = y line is reached.
    (i.e 9 o'clock to 10:30)
    Fill in rest of the circle by mirroring the edges.
    topStack holds the values from 12 o'clock to 10:30.
    bottomStack holds the values from 9 o'clock to 6 o'clock.
  */

  const indices: number[] = [];
  const topStack: number[] = [];
  const bottomStack: number[] = [];
  const offset = (n - 1) / 2;
  let x = -offset;
  let y = n & 1 ? 0 : -0.5;
  let row = 0;

  let d = x * x + y * y - (n * n) / 4;
  let deltaUp = 1 - 2 * y;
  let deltaRight = 2 * x + 1;

  // can shift origin first as subsequent digital differential analyzer operations were decoupled from exact value of xy
  x += offset;
  y += offset;

  let lastPushed = -1;

  const push = (index: number) => {
    if (index === lastPushed) indices.pop();
    else {
      indices.push(index);
      lastPushed = index;
    }
  };

  while (y > x) {
    topStack.push(x);
    y -= 1;
    d += deltaUp;
    deltaUp += 2;

    while (d > 0) {
      push(row * n + (y + 1));
      push((row + 1) * n - (y + 1));
      bottomStack.push(y + 1);
      row += 1;
      x += 1;
      d += deltaRight;
      deltaRight += 2;
    }
  }

  if (y === x) {
    push(row * n + y);
    push((row + 1) * n - y);
    bottomStack.push(y);
    row += 1;
  }
  while (topStack.length > 0) {
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    const x = topStack.pop()!;
    push(row * n + x);
    push((row + 1) * n - x);
    bottomStack.push(x);
    row += 1;
  }
  if (n & 1) bottomStack.pop();
  while (bottomStack.length > 0) {
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    const x = bottomStack.pop()!;
    push(row * n + x);
    push((row + 1) * n - x);
    row += 1;
  }

  return indices;
}

export function adjacentPixelsFromRing(
  ring: number[],
  width: number,
  adjacentPixels = new Map<number, number>()
): Map<number, number> {
  ring.forEach((pixel, i) => {
    const prevPixel = i > 0 ? ring[i - 1] : ring[ring.length - 1];
    let currAdjacent = adjacentPixels.get(pixel) ?? 0;
    let prevAdjacent = adjacentPixels.get(prevPixel) ?? 0;

    // 1248 correspond to North, East, South, West
    if (pixel - prevPixel === width) {
      currAdjacent ^= 1;
      prevAdjacent ^= 4;
    }
    if (pixel - prevPixel === 1) {
      currAdjacent ^= 8;
      prevAdjacent ^= 2;
    }
    if (prevPixel - pixel === width) {
      currAdjacent ^= 4;
      prevAdjacent ^= 1;
    }
    if (prevPixel - pixel === 1) {
      currAdjacent ^= 2;
      prevAdjacent ^= 8;
    }

    adjacentPixels.set(pixel, currAdjacent);
    adjacentPixels.set(prevPixel, prevAdjacent);
  });
  return adjacentPixels;
}

export function outlineAndFillFromAdjacentPixels(
  adjacentPixels: Map<number, number>,
  width: number,
  height: number
): TransformedToSparse {
  let outline: SparseBitmask;
  let fill: SparseBitmask;

  return {
    toOutline() {
      if (!outline) {
        outline = new SparseBitmask(width * height, false);
        for (const pixel of adjacentPixels.keys()) {
          outline.set(pixel, 1);
        }
      }
      return outline;
    },
    toFill() {
      if (!fill) {
        fill = new SparseBitmask(width * height, true);
        let runState = FillState.Green;
        let nextRowStart = width;

        for (const pixel of this.toOutline().getIndices()) {
          if (pixel >= nextRowStart) {
            if (runState !== FillState.Green) {
              fill.flip(nextRowStart);
            }
            runState = FillState.Green;
            while (pixel >= nextRowStart) {
              nextRowStart += width;
            }
          }

          const junction = adjacentPixels.get(pixel) ?? 0;
          const nextState: FillState =
            FILL_STATE_MACHINE[runState][junction] ?? runState;
          if (runState === FillState.Green) {
            fill.flip(pixel);
          }
          if (nextState === FillState.Green && pixel + 1 < width * height) {
            fill.flip(pixel + 1);
          }
          runState = nextState;
        }
      }
      return fill;
    },
  };
}

export function pasteBitmask(
  from: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  x: number,
  y: number,
  toWidth: number,
  toHeight: number,
  outputRunEnds = true
): SparseBitmask {
  // skip empty rows at the top
  const indices = from.getIndices() as OrderedSet<number>;
  if (indices.size === 0) {
    return new SparseBitmask(toWidth * toHeight, outputRunEnds);
  }
  // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
  const first = indices.at(0)!;
  const firstRow = Math.trunc(first / fromWidth);

  // compute the part of the pasted window that is within the output canvas
  const sMinX = Math.max(-x, 0);
  const sMinY = Math.max(-y, firstRow);
  const sMaxX = Math.min(toWidth - x, fromWidth);
  const sMaxY = Math.min(toHeight - y, fromHeight);

  // sprite completely outside bound
  if (sMinX >= sMaxX || sMinY >= sMaxY) {
    return new SparseBitmask(toWidth * toHeight, outputRunEnds);
  }

  // convert to run lengths windowed by row for subsequent interlacing
  const windowedRunLengths = getWindowedRunLengths(
    from,
    fromWidth,
    fromHeight,
    sMinX,
    sMinY,
    sMaxX,
    sMaxY
  );

  // interlace run lengths with zero filled gaps
  function* interlace(runLengths: Iterable<number>) {
    const windowLength = sMaxX - sMinX;
    const gapLength = toWidth - windowLength;
    const interlaceStart = (y + sMinY) * toWidth + x + sMinX;
    const interlaceEnd = (y + sMaxY - 1) * toWidth + (x + sMaxX - 1) + 1;
    yield interlaceStart;
    let rowLength = 0;
    for (const runLength of runLengths) {
      if (rowLength >= windowLength) {
        yield gapLength;
        rowLength = 0;
      }
      yield runLength;
      if (runLength < 0) rowLength -= runLength;
      else rowLength += runLength;
    }
    yield toWidth * toHeight - interlaceEnd;
  }
  const interlacedRunLengths = interlace(windowedRunLengths);

  // recompose run end indices from run lengths
  return new SparseBitmask(toWidth * toHeight, outputRunEnds).setIndices(
    outputRunEnds
      ? runLengthsToRunEndIndices(interlacedRunLengths)
      : runLengthsToOneBitIndices(interlacedRunLengths),
    outputRunEnds
  );
}

export function cutBitmask(
  from: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  x: number,
  y: number,
  toWidth: number,
  toHeight: number,
  outputRunEnds = true
): SparseBitmask {
  return pasteBitmask(
    from,
    fromWidth,
    fromHeight,
    -x,
    -y,
    toWidth,
    toHeight,
    outputRunEnds
  );
}

export function offsetBitmask(
  mask: SparseBitmask,
  offsetX: number,
  offsetY: number,
  width: number,
  height: number
): SparseBitmask {
  return pasteBitmask(
    mask,
    width,
    height,
    offsetX,
    offsetY,
    width,
    height,
    mask.isRunEnds
  );
}

/**
 * Decompose from bitmask into 1 or 0 run lengths that are windowed by each row
 * Negative run length means 1, positive run length means 0
 * Unlike run end indices that always indicate a change of sign, adjacent run lengths can be of the same sign
 * Useful for windowing operations
 */
function* getWindowedRunLengths(
  mask: SparseBitmask,
  width: number,
  height: number,
  minX = 0,
  minY = 0,
  maxX = width,
  maxY = height
): Iterable<number> {
  if (minX >= maxX || minY >= maxY) return;
  let sign = 1;
  let currRowStart = minY * width + minX;
  let currRowEnd = minY * width + maxX;
  const endIndex = (maxY - 1) * width + maxX;
  let lastIndex = currRowStart;

  for (const index of mask.getIndices(true)) {
    while (index >= currRowEnd) {
      yield sign * (currRowEnd - lastIndex);
      currRowStart += width;
      currRowEnd += width;
      lastIndex = currRowStart;
      if (currRowEnd > endIndex) return;
    }
    if (index >= currRowStart) {
      yield sign * (index - lastIndex);
      lastIndex = index;
    }
    sign = -sign;
  }
  if (sign < 0) {
    while (lastIndex < endIndex) {
      yield lastIndex - currRowEnd;
      currRowStart += width;
      currRowEnd += width;
      lastIndex = currRowStart;
    }
  } else if (lastIndex < currRowEnd) {
    yield currRowEnd - lastIndex;
    // ignore empty rows at the bottom
  }
}

export function* runLengthsToRunEndIndices(
  runLengths: Iterable<number>
): Iterable<number> {
  let expectedSign = -1;
  let offset = 0;
  for (const runLength of runLengths) {
    if (runLength < 0) {
      if (expectedSign < 0) {
        yield offset;
        expectedSign = 1;
      }
      offset -= runLength;
    } else if (runLength > 0) {
      if (expectedSign > 0) {
        yield offset;
        expectedSign = -1;
      }
      offset += runLength;
    }
  }
}

export function* runLengthsToOneBitIndices(
  runLengths: Iterable<number>
): Iterable<number> {
  let offset = 0;
  for (const runLength of runLengths) {
    if (runLength < 0) {
      const runEnd = offset - runLength;
      while (offset < runEnd) {
        yield offset;
        offset += 1;
      }
    } else if (runLength > 0) {
      offset += runLength;
    }
  }
}

export function getWeight(
  mask: SparseBitmask,
  width: number,
  height: number
): number {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  if (!mask.isRunEnds) return mask.getIndicesCount();
  let lastIndex = -1;
  let weight = 0;
  for (const index of mask.getIndices()) {
    if (lastIndex >= 0) {
      weight += index - lastIndex;
      lastIndex = -1;
    } else {
      lastIndex = index;
    }
  }
  if (lastIndex >= 0) {
    weight += width * height - lastIndex;
  }
  return weight;
}

export function getFilledRatio(
  mask: SparseBitmask,
  width: number,
  height: number
): number {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  return getWeight(mask, width, height) / (width * height);
}

export function getCentroid(
  mask: SparseBitmask,
  width: number,
  height: number
): [number, number] {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  let sumX = 0;
  let sumY = 0;
  let weight = 0;
  if (mask.isRunEnds) {
    const indices = mask.getIndices() as OrderedSet<number>;
    if (indices.size === 0) return [width / 2, height / 2];
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    const first = indices.at(0)!;
    let x = 0;
    let y = Math.trunc(first / width);
    const runLengths = getWindowedRunLengths(mask, width, height, x, y);
    for (const runLength of runLengths) {
      if (x >= width) {
        x = 0;
        y += 1;
      }
      if (runLength < 0) {
        const dw = -runLength;
        sumX += (x + dw * 0.5) * dw;
        sumY += (y + 0.5) * dw;
        weight += dw;
        x -= runLength;
      } else {
        x += runLength;
      }
    }
  } else {
    for (const index of mask.getIndices()) {
      const x = index % width;
      const y = Math.trunc(index / width);
      sumX += x + 0.5;
      sumY += y + 0.5;
      weight += 1;
    }
  }
  if (weight === 0) return [width / 2, height / 2];
  return [sumX / weight, sumY / weight];
}

export function getBoundingBox(
  mask: SparseBitmask,
  width: number,
  height: number
): [number, number, number, number] {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  let minX = width;
  let minY = height;
  let maxX = 0;
  let maxY = 0;
  if (mask.isRunEnds) {
    const indices = mask.getIndices() as OrderedSet<number>;
    if (indices.size === 0) return [minX, minY, maxX, maxY];
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    const first = indices.at(0)!;
    let x = 0;
    let y = Math.trunc(first / width);
    const runLengths = getWindowedRunLengths(mask, width, height, x, y);
    for (const runLength of runLengths) {
      if (x >= width) {
        x = 0;
        y += 1;
      }
      if (runLength < 0) {
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, x - runLength);
        maxY = Math.max(maxY, y);
        x -= runLength;
      } else {
        x += runLength;
      }
    }
  } else {
    for (const index of mask.getIndices()) {
      const x = index % width;
      const y = Math.trunc(index / width);
      minX = Math.min(minX, x);
      minY = Math.min(minY, y);
      maxX = Math.max(maxX, x + 1);
      maxY = Math.max(maxY, y);
    }
  }
  return [minX, minY, maxX, maxY];
}

export function getOutlineFromFill(
  mask: SparseBitmask,
  width: number,
  height: number
): SparseBitmask {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  const p4 = mask.asRunEndIndices();

  // filter pixels where at least one adjacent pixel is unpainted
  const p0 = offsetBitmask(p4, -1, -1, width, height);
  const p1 = offsetBitmask(p4, 0, -1, width, height);
  const p2 = offsetBitmask(p4, 1, -1, width, height);
  const p3 = offsetBitmask(p4, -1, 0, width, height);
  const p5 = offsetBitmask(p4, 1, 0, width, height);
  const p6 = offsetBitmask(p4, -1, 1, width, height);
  const p7 = offsetBitmask(p4, 0, 1, width, height);
  const p8 = offsetBitmask(p4, 1, 1, width, height);

  let intersect: Iterable<number> = p0.getIndices();
  intersect = intersectionRunEnds(intersect, p1.getIndices());
  intersect = intersectionRunEnds(intersect, p2.getIndices());
  intersect = intersectionRunEnds(intersect, p3.getIndices());
  intersect = intersectionRunEnds(intersect, p5.getIndices());
  intersect = intersectionRunEnds(intersect, p6.getIndices());
  intersect = intersectionRunEnds(intersect, p7.getIndices());
  intersect = intersectionRunEnds(intersect, p8.getIndices());

  const outline = new SparseBitmask(width * height, true).setIndices(
    subtractionRunEnds(p4.getIndices(), intersect),
    true
  );
  return outline;
}

export function getExtOutlineFromFill(
  mask: SparseBitmask,
  width: number,
  height: number
): SparseBitmask {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  const p4 = mask.asRunEndIndices();

  // merge all adjacent pixels and remove the original mask
  const p0 = offsetBitmask(p4, -1, -1, width, height);
  const p1 = offsetBitmask(p4, 0, -1, width, height);
  const p2 = offsetBitmask(p4, 1, -1, width, height);
  const p3 = offsetBitmask(p4, -1, 0, width, height);
  const p5 = offsetBitmask(p4, 1, 0, width, height);
  const p6 = offsetBitmask(p4, -1, 1, width, height);
  const p7 = offsetBitmask(p4, 0, 1, width, height);
  const p8 = offsetBitmask(p4, 1, 1, width, height);

  let union: Iterable<number> = p0.getIndices();
  union = unionRunEnds(union, p1.getIndices());
  union = unionRunEnds(union, p2.getIndices());
  union = unionRunEnds(union, p3.getIndices());
  union = unionRunEnds(union, p5.getIndices());
  union = unionRunEnds(union, p6.getIndices());
  union = unionRunEnds(union, p7.getIndices());
  union = unionRunEnds(union, p8.getIndices());

  return new SparseBitmask(width * height, true).setIndices(
    subtractionRunEnds(union, p4.getIndices()),
    true
  );
}