Some helpers functions for manipulating bitmask in sparse (run-based) format

bitmaskHelpers.ts

import SparseBitmask, {
  unionRunEnds,
  intersectionRunEnds,
  subtractionRunEnds,
} from "./SparseBitmask";
import {
  cutAndPasteBitmask3d,
  getBoundingBox3d,
  getCentroid3d,
  getWindowedRunLengths3d,
  resizeBitmask3d,
  switchPrimaryAxis,
} from "./bitmaskHelpers3d";
import { OrderedMap } from "./OrderedCollections";
import { memoized, numberHasher } from "./memo";
import { range } from "./base";

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

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

export function transformPolygonToSparse(
  polygon: [number, number][][],
  width: number,
  height: number
): TransformedToSparse {
  const bbox: [number, number, number, number] = [0, 0, width - 1, height - 1];

  const rings = polygon.map(vertices => {
    const ring: [number, number][] = [];
    for (const k of range(vertices.length)) {
      const [x1, y1] = vertices[k];
      const [x2, y2] = k < vertices.length - 1 ? vertices[k + 1] : vertices[0];
      const i1 = Math.floor(x1);
      const j1 = Math.floor(y1);
      const i2 = Math.floor(x2);
      const j2 = Math.floor(y2);

      if (i1 - i2 > 1 || i2 - i1 > 1 || j1 - j2 > 1 || j2 - j1 > 1) {
        memoizedDrawLine(x1, y1, x2, y2).forEach(pt => ring.push(pt));
        ring.pop();
      } else {
        ring.push([i1, j1]);
      }
    }
    ring.forEach(pt => {
      if (pt[0] < bbox[0]) bbox[0] = pt[0];
      if (pt[1] < bbox[1]) bbox[1] = pt[1];
      if (pt[0] > bbox[2]) bbox[2] = pt[0];
      if (pt[1] > bbox[3]) bbox[3] = pt[1];
    });
    return ring;
  });

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

  return outlineAndFillFromAdjacentPixels(adjacentPixels, width, height, bbox);
}

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.
  */

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

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

  while (y > x) {
    indices.push(y * n + x, y * n - x + 1);
    if (y !== 0) indices.push(-y * n + x, -y * n - x + 1);
    y -= 1;
    d += deltaUp;
    deltaUp += 2;

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

  if (y === x) {
    indices.push(y * n + x, y * n - x + 1);
    if (y !== 0) indices.push(-y * n + x, -y * n - x + 1);
  }

  const indexOffset = offset * (n + 1);

  let lastIndex = -1;
  const sortedIndices: number[] = [];
  indices
    .sort((a, b) => a - b)
    .forEach(index => {
      const properIndex = index + indexOffset;
      if (properIndex === lastIndex) {
        sortedIndices.pop();
        lastIndex = -1;
      } else {
        sortedIndices.push(properIndex);
        lastIndex = properIndex;
      }
    });
  return sortedIndices;
}

export function adjacentPixelsFromRing(
  ring: [number, number][],
  bbox: [number, number, number, number],
  adjacentPixels = new Map<number, number>()
): Map<number, number> {
  const offsetX = -bbox[0];
  const offsetY = -bbox[1];
  const width = bbox[2] - bbox[0] + 1;
  ring.forEach(([i, j], k) => {
    const [prevI, prevJ] = k > 0 ? ring[k - 1] : ring[ring.length - 1];
    const pixel = (j + offsetY) * width + (i + offsetX);
    const prevPixel = (prevJ + offsetY) * width + (prevI + offsetX);

    let currAdjacent = adjacentPixels.get(pixel) ?? 0;
    let prevAdjacent = adjacentPixels.get(prevPixel) ?? 0;

    // 1/2/4/8/16/32/64/128 correspond to North, East, South, West, NE, NW, SW, SE
    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;
    }
    if (pixel - prevPixel === width + 1) {
      currAdjacent ^= 16;
      prevAdjacent ^= 64;
    }
    if (pixel - prevPixel === width - 1) {
      currAdjacent ^= 32;
      prevAdjacent ^= 128;
    }
    if (prevPixel - pixel === width + 1) {
      currAdjacent ^= 64;
      prevAdjacent ^= 16;
    }
    if (prevPixel - pixel === width - 1) {
      currAdjacent ^= 128;
      prevAdjacent ^= 32;
    }

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

export function outlineAndFillFromAdjacentPixels(
  adjacentPixels: Map<number, number>,
  width: number,
  height: number,
  bbox: [number, number, number, number] = [0, 0, width - 1, height - 1]
): TransformedToSparse {
  let outline: SparseBitmask;
  let fill: SparseBitmask;

  return {
    toOutline() {
      if (!outline) {
        const overflowWidth = bbox[2] - bbox[0] + 1;
        outline = new SparseBitmask(width * height, false);
        adjacentPixels.forEach((_, pixel) => {
          const i = Math.min(Math.max(0, pixel % overflowWidth), width - 1);
          const j = Math.min(
            Math.max(0, Math.trunc(pixel / overflowWidth)),
            height - 1
          );
          outline.set(j * width + i, 1);
        });
      }
      return outline;
    },
    toFill() {
      if (!fill) {
        const overflowWidth = bbox[2] - bbox[0] + 1;
        const overflowHeight = bbox[3] - bbox[1] + 1;

        const outline = new SparseBitmask(
          overflowWidth * overflowHeight,
          false
        );
        adjacentPixels.forEach((_, pixel) => {
          outline.set(pixel, 1);
        });

        const beforeCut = new SparseBitmask(
          overflowWidth * overflowHeight,
          true
        );

        let runState = 0;
        let nextRowStart = overflowWidth;
        for (const pixel of outline.getIndices()) {
          if (pixel >= nextRowStart) {
            if (runState !== 0) {
              beforeCut.flip(nextRowStart);
            }
            runState = 0;
            while (pixel >= nextRowStart) {
              nextRowStart += overflowWidth;
            }
          }

          const junction = adjacentPixels.get(pixel) ?? 0;
          let nextState = runState;
          nextState ^= (junction & 16 ? 2 : 0) + (junction & 128 ? 1 : 0);
          nextState ^= (junction & 1 ? 2 : 0) + (junction & 4 ? 1 : 0);
          nextState ^= (junction & 32 ? 2 : 0) + (junction & 64 ? 1 : 0);

          if (runState === 0) {
            beforeCut.flip(pixel);
          }
          if (nextState === 0 && pixel + 1 < overflowWidth * overflowHeight) {
            beforeCut.flip(pixel + 1);
          }
          runState = nextState;
        }
        fill =
          overflowWidth > width || overflowHeight > height
            ? cutBitmask(
                beforeCut,
                overflowWidth,
                overflowHeight,
                -bbox[0],
                -bbox[1],
                width,
                height
              )
            : beforeCut;
      }
      return fill;
    },
  };
}

export function cutAndPasteBitmask(
  from: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  cutX: number,
  cutY: number,
  cutWidth: number,
  cutHeight: number,
  pasteX: number,
  pasteY: number,
  toWidth: number,
  toHeight: number,
  to = new SparseBitmask(toWidth * toHeight, from.isRunEnds)
): SparseBitmask {
  return cutAndPasteBitmask3d(
    from,
    fromWidth,
    fromHeight,
    1,
    cutX,
    cutY,
    0,
    cutWidth,
    cutHeight,
    1,
    pasteX,
    pasteY,
    0,
    toWidth,
    toHeight,
    1,
    to
  );
}

export function cutBitmask(
  from: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  x: number,
  y: number,
  toWidth: number,
  toHeight: number
): SparseBitmask {
  if (x === 0 && y === 0 && fromWidth === toWidth && fromHeight === toHeight) {
    return from;
  }
  return cutAndPasteBitmask3d(
    from,
    fromWidth,
    fromHeight,
    1,
    x,
    y,
    0,
    toWidth,
    toHeight,
    1,
    0,
    0,
    0,
    toWidth,
    toHeight,
    1
  );
}

export function pasteBitmask(
  from: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  x: number,
  y: number,
  toWidth: number,
  toHeight: number,
  to = new SparseBitmask(toWidth * toHeight, from.isRunEnds)
): SparseBitmask {
  return cutAndPasteBitmask3d(
    from,
    fromWidth,
    fromHeight,
    1,
    0,
    0,
    0,
    fromWidth,
    fromHeight,
    1,
    x,
    y,
    0,
    toWidth,
    toHeight,
    1,
    to
  );
}

export function offsetBitmask(
  mask: SparseBitmask,
  offsetX: number,
  offsetY: number,
  width: number,
  height: number
): SparseBitmask {
  return cutAndPasteBitmask3d(
    mask,
    width,
    height,
    1,
    0,
    0,
    0,
    width,
    height,
    1,
    offsetX,
    offsetY,
    0,
    width,
    height,
    1
  );
}

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

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

export function getWeight(
  mask: SparseBitmask,
  width: number,
  height: number,
  depth = 1
): number {
  if (mask.length !== width * height * depth) {
    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 * depth - lastIndex;
  }
  return weight;
}

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

export function getCentroid(
  mask: SparseBitmask,
  width: number,
  height: number
): [number, number] {
  const centroid = getCentroid3d(mask, width, height, 1);
  return [centroid[0], centroid[1]];
}

export function getWeightedCentroid(
  masks: SparseBitmask[],
  width: number,
  height: number
): [number, number] {
  if (masks.length === 0) return [width / 2, height / 2];
  let sumX = 0;
  let sumY = 0;
  let weight = 0;
  for (const mask of masks) {
    const [x, y] = getCentroid(mask, width, height);
    const w = getWeight(mask, width, height);
    weight += w;
    sumX += x * w;
    sumY += y * w;
  }
  return [sumX / weight, sumY / weight];
}

export function getBoundingBox(
  mask: SparseBitmask,
  width: number,
  height: number
): [number, number, number, number] {
  const bbox = getBoundingBox3d(mask, width, height, 1);
  return [bbox[0], bbox[1], bbox[3], bbox[4]];
}

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
  );
}

export interface PixelIsland {
  id: number;
  type: 1 | 0;
  mask: SparseBitmask;
  weight: number;
  parent: number;
}

export interface AugmentedPixelIsland extends PixelIsland {
  children: Set<number>;
  nestedWeight: number;
}

/**
 * Return the set of pixel islands from a mask
 * ReturnType:
 * - id: the id of the island
 * - type: 0 for hole, 1 for island
 * - mask: the island or hole bitmask as a single contiguous block
 *   (may contain holes or other islands within)
 * - weight: the weight of the island (in pixel count and excluding children)
 * - parent: the id of the island's parent (0 for background)
 * For more sophisticated downstream operations call augmentIslands
 */
export function getIslands(
  mask: SparseBitmask,
  width: number,
  height: number
): PixelIsland[] {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }

  if (mask.getIndicesCount() === 0) {
    const island: PixelIsland = {
      id: 0,
      type: 0,
      mask: new SparseBitmask(mask.length, true).setIndices([0], true),
      weight: mask.length,
      parent: 0,
    };
    return [island];
  }

  const runLengths = [...getWindowedRunLengths3d(mask, width, height)];
  const assignments: number[] = [];
  const reassigned = new Map<number, number>();
  const parents = new Map<number, number>();

  let minA = -1;
  let maxA = 1;

  // ensures zero fills connected to top edge are assigned 0
  let prevRowOffsets: number[] = [width];
  let prevRowAssignments: number[] = [0];
  let currRowOffsets: number[] = [];
  let currRowAssignments: number[] = [];
  let prevPointer = 0;
  let currOffset = 0;
  let colMode = false;

  // adding an additional full width run length
  // ensures zero fills connected to bottom edge are assigned 0
  runLengths.push(width, 1);

  runLengths.forEach(r => {
    if (currOffset >= width) {
      // reset everything once finish processing a row
      prevRowOffsets = currRowOffsets;
      prevRowAssignments = currRowAssignments;
      currRowOffsets = [];
      currRowAssignments = [];
      prevPointer = 0;
      currOffset = 0;
    }

    const connected = new Set<number>();
    let currA: number;
    if (r === width) {
      colMode = true;
      currA = 0;
    } else if (r < 0) {
      const run = colMode ? -width : r;
      let parent = 0;
      if (prevRowOffsets[prevPointer] > currOffset) {
        // prev run is connected, add to connected if is same sign
        const prevA = prevRowAssignments[prevPointer];
        if (prevA < 0) connected.add(prevA);
        else parent = prevA;
      }

      while (prevRowOffsets[prevPointer] < currOffset - run) {
        // check next run, add to connected if is same sign
        prevPointer += 1;
        const prevA = prevRowAssignments[prevPointer];
        if (prevA < 0) connected.add(prevA);
        else parent = prevA;
      }

      currA = minA;
      if (connected.size > 0) {
        // take smallest assignment (absolute value) among connected runs (from prev row)
        // and assign it to the curr run (in curr row)
        connected.forEach(prevA => {
          if (prevA > currA) currA = prevA;
        });
      } else {
        // otherwise create a new assignment by incrementing counter
        minA -= 1;
        parents.set(currA, parent);
      }
      currOffset -= run;
      colMode = false;
    } else {
      const run = colMode ? width : r;
      let parent = 0;
      if (prevRowOffsets[prevPointer] > currOffset) {
        const prevA = prevRowAssignments[prevPointer];
        if (prevA >= 0) connected.add(prevA);
        else parent = prevA;
      }

      while (prevRowOffsets[prevPointer] < currOffset + run) {
        prevPointer += 1;
        const prevA = prevRowAssignments[prevPointer];
        if (prevA >= 0) connected.add(prevA);
        else parent = prevA;
      }

      currA = maxA;
      if (currOffset <= 0 || currOffset + run >= width) {
        // ensures zero fills connected to side edges are assigned 0d
        connected.add(0);
      }

      if (connected.size > 0) {
        connected.forEach(prevA => {
          if (prevA < currA) currA = prevA;
        });
      } else {
        maxA += 1;
        parents.set(currA, parent);
      }
      currOffset += run;
      colMode = false;
    }

    // reassign connected runs (from prev row) to curr run's assignment (in curr row)
    connected.forEach(prevA => {
      if (prevA !== currA) {
        reassigned.set(prevA, currA);
      }
    });
    currRowOffsets.push(currOffset);
    currRowAssignments.push(currA);
    assignments.push(currA);
  });

  // remove the extra run length
  runLengths.pop();
  runLengths.pop();
  assignments.pop();
  assignments.pop();

  // finalize assignment from smallest to largest (absolute value)
  for (const k of range(maxA)) {
    const curr = reassigned.get(k);
    if (curr != null) {
      const next = reassigned.get(curr);
      if (next != null) {
        reassigned.set(k, next);
      }
    }
  }
  for (const k of range(-1, minA, -1)) {
    const curr = reassigned.get(k);
    if (curr != null) {
      const next = reassigned.get(curr);
      if (next != null) {
        reassigned.set(k, next);
      }
    }
  }

  const finalAssignments = assignments.map(
    assignment => reassigned.get(assignment) ?? assignment
  );
  const islandSet = new Set(finalAssignments);
  const islandMap = new Map<number, SparseBitmask>();
  islandSet.add(0);
  islandSet.forEach(i => {
    islandMap.set(i, new SparseBitmask(mask.length, true));
  });

  let index = 0;
  let k = 1;
  runLengths.forEach((r, i) => {
    if (r === width) {
      k = width;
    } else {
      const currMask = islandMap.get(finalAssignments[i])!;
      currMask.flip(index);
      if (r < 0) index -= r * k;
      else index += r * k;
      currMask.flip(index);
      k = 1;
    }
  });

  const islands: PixelIsland[] = [];
  islandMap.forEach((mask, id) => {
    const weight = getWeight(mask, width, height);
    if (id === 0 || weight > 0) {
      let parentId = parents.get(id) ?? 0;
      parentId = reassigned.get(parentId) ?? parentId;
      const island: PixelIsland = {
        id,
        type: id < 0 ? 1 : 0,
        mask,
        weight,
        parent: parentId,
      };
      islands.push(island);
    }
  });
  return islands;
}

/**
 * Augment the islands with children and nested weight
 * and sort them largest to smallest by nested weight
 */
export function augmentIslands(islands: PixelIsland[]): AugmentedPixelIsland[] {
  const nestedWeight = computeIslandsNestedWeight(islands);
  const children = new Map<number, Set<number>>();
  islands.forEach(island => {
    children.set(island.id, new Set());
  });
  islands.forEach(island => {
    const parentId = island.parent;
    if (island.id !== parentId) {
      children.get(parentId)!.add(island.id);
    }
  });
  return islands
    .map(island => ({
      ...island,
      children: children.get(island.id)!,
      nestedWeight: nestedWeight.get(island.id)!,
    }))
    .sort((a, b) => b.nestedWeight - a.nestedWeight);
}

export function computeIslandsNestedWeight(
  islands: PixelIsland[]
): Map<number, number> {
  const nestedWeight = new Map<number, number>();
  const relations = new Map<
    number,
    { parent: number; children: Set<number> }
  >();

  islands.forEach(island => {
    relations.set(island.id, { parent: island.parent, children: new Set() });
    nestedWeight.set(island.id, island.weight);
  });
  islands.forEach(island => {
    const parentId = island.parent;
    if (island.id !== parentId) {
      relations.get(parentId)!.children.add(island.id);
    }
  });
  while (relations.size > 1) {
    relations.forEach(({ children, parent }, self) => {
      if (children.size === 0) {
        nestedWeight.set(
          parent,
          nestedWeight.get(parent)! + nestedWeight.get(self)!
        );
        relations.get(parent)!.children.delete(self);
        relations.delete(self);
      }
    });
  }
  return nestedWeight;
}

export function resizeBitmask(
  mask: SparseBitmask,
  fromWidth: number,
  fromHeight: number,
  toWidth: number,
  toHeight: number
): SparseBitmask {
  return resizeBitmask3d(mask, fromWidth, fromHeight, 1, toWidth, toHeight, 1);
}

export function flipAxes(
  mask: SparseBitmask,
  width: number,
  height: number
): SparseBitmask {
  return switchPrimaryAxis(mask, width, height, 1);
}

interface RGBA {
  r: number;
  g: number;
  b: number;
  a: number;
}

let cachedCanvas: OffscreenCanvas;

export async function bitmaskToImage(
  mask: SparseBitmask,
  width: number,
  height: number,
  fill: RGBA,
  outline: RGBA = { r: 0, g: 0, b: 0, a: 0 }
): Promise<string> {
  if (mask.length !== width * height) {
    throw new Error("mismatch parameters");
  }
  const imageData = new ImageData(width, height);
  const { data } = imageData;
  if (fill.a > 0) {
    const { r, g, b, a } = fill;
    for (const index of mask.getIndices(false)) {
      data[index * 4] = r;
      data[index * 4 + 1] = g;
      data[index * 4 + 2] = b;
      data[index * 4 + 3] = a;
    }
  }
  if (outline.a > 0) {
    const { r, g, b, a } = outline;
    const outlineMask = getOutlineFromFill(mask, width, height);
    for (const index of outlineMask.getIndices(false)) {
      data[index * 4] = r;
      data[index * 4 + 1] = g;
      data[index * 4 + 2] = b;
      data[index * 4 + 3] = a;
    }
  }
  if (!cachedCanvas) {
    cachedCanvas = new OffscreenCanvas(width, height);
  }
  cachedCanvas.width = width;
  cachedCanvas.height = height;
  const ctx = cachedCanvas.getContext("2d")!;
  ctx.putImageData(imageData, 0, 0);
  const blob = await cachedCanvas.convertToBlob();
  return URL.createObjectURL(blob);
}

export function optimizeBitmaskToImage(
  maxShorterSide: number
): (
  ...args: Parameters<typeof bitmaskToImage>
) => Promise<[string, number, number, number, number]> {
  return (
    mask: SparseBitmask,
    width: number,
    height: number,
    fill: RGBA,
    outline: RGBA = { r: 0, g: 0, b: 0, a: 0 }
  ) => {
    const bbox = getBoundingBox(mask, width, height);
    const cutWidth = bbox[2] - bbox[0];
    const cutHeight = bbox[3] - bbox[1];
    const cut = cutBitmask(
      mask,
      width,
      height,
      bbox[0],
      bbox[1],
      cutWidth,
      cutHeight
    );
    const shorterSide = Math.min(cutWidth, cutHeight);
    const targetScale =
      shorterSide <= maxShorterSide ? 1 : maxShorterSide / shorterSide;
    const resizedWidth = Math.ceil(cutWidth * targetScale);
    const resizedHeight = Math.ceil(cutHeight * targetScale);

    const resizedMask = resizeBitmask3d(
      cut,
      cutWidth,
      cutHeight,
      1,
      resizedWidth,
      resizedHeight,
      1
    );

    return bitmaskToImage(
      resizedMask,
      resizedWidth,
      resizedHeight,
      fill,
      outline
    ).then(
      url =>
        [url, bbox[0], bbox[1], bbox[2] - bbox[0], bbox[3] - bbox[1]] as [
          string,
          number,
          number,
          number,
          number
        ]
    );
  };
}

export function bitmaskFromWeightedRuns(
  runWeights: OrderedMap<number, number>,
  maskSize: number,
  threshold = 1
): SparseBitmask {
  const indices: number[] = [];
  let accumulatedWeight = 0;
  let curr = 0;
  for (const [index, weight] of runWeights) {
    if (index >= maskSize) break;
    accumulatedWeight += weight;
    if (
      (curr && accumulatedWeight < threshold) ||
      (!curr && accumulatedWeight >= threshold)
    ) {
      indices.push(index);
      curr = 1 - curr;
    }
  }
  return new SparseBitmask(maskSize, true).setIndices(indices, true);
}