Skip to content

Virtual whiteboard for sketching hand-drawn like diagrams

67.3 KB
Raw Blame
import { pointsOnBezierCurves, simplify } from "points-on-curve";
import { curveToBezier } from "points-on-curve/lib/curve-to-bezier";

import {
  distanceToLineSegment,
  lineSegment,
  lineSegmentIntersectionPoints,
  pointDistance,
  pointFrom,
  pointRotateRads,
  polygonArea,
  polygonIncludesPoint,
  polygonIncludesPointNonZero,
  polygonSignedArea,
} from "@excalidraw/math";

import { isOpaqueColor, isTransparent } from "@excalidraw/common";

import type { Bounds } from "@excalidraw/common";
import type {
  GlobalPoint,
  LineSegment,
  LocalPoint,
  Polygon,
} from "@excalidraw/math";

import {
  doBoundsIntersect,
  elementCenterPoint,
  getBoundsFromPoints,
  getElementBounds,
  getElementLineSegments,
} from "./bounds";
import { intersectElementWithLineSegment, isPointInElement } from "./collision";
import { hasBackground } from "./comparisons";
import { distanceToElement } from "./distance";
import { getFreedrawStrokeCenterPoints } from "./shape";
import {
  isFreeDrawElement,
  isLinearElement,
  isLineElement,
  isValidPolygon,
} from "./typeChecks";
import { isPathALoop } from "./utils";

import type { Point } from "points-on-curve";

import type {
  ElementsMap,
  ExcalidrawElement,
  ExcalidrawFreeDrawElement,
  ExcalidrawLineElement,
  NonDeletedExcalidrawElement,
} from "./types";

/**
 * Pure geometry helpers for the bucket fill tool.
 *
 * Given a click point and the scene elements, this computes the closed polygon
 * (in scene/global coordinates) that fills the enclosed region under the
 * pointer. The Excalidraw app layer converts the returned `scenePoints` into a
 * local `line` polygon and inserts it.
 *
 * All fills go through a single path: a planar segment arrangement is built
 * (segments split at intersections) and the smallest bounded face containing
 * the click is selected.
 *
 * The OWNER is the topmost closed, visible element containing the click
 * point — a shape, a closed (`polygon`) line, or a looped freedraw. It is
 * not the fill's boundary per se; it anchors the fast common case: only
 * elements near the owner's bounds feed the arrangement, and the app layer
 * inherits the fill's frame/group membership from it. When no owner exists
 * (regions formed by open lines, including against other elements' outside
 * walls), candidates come from an expanding search box around the click
 * instead — the owner-less fallback. Fill-compatible paint (see
 * `isBucketFillCompatible`) never becomes an owner: clicking it restyles
 * the existing paint (app layer) or re-derives the region from the actual
 * strokes around it.
 *
 * Islands (disconnected outlines fully inside the selected region) become
 * holes: their contours are spliced into the returned ring as zero-width
 * "keyhole" bridges, so the result stays a single closed polygon that
 * renders with unpainted hole interiors. Looped-line fills are painted with
 * the even-odd rule (roughjs uses it for solid polygon/curve fills and the
 * SVG export sets `fill-rule="evenodd"` explicitly; pattern fills use
 * scanline parity, which behaves the same) — the doubled bridge edges
 * cancel under it. Holes are nonetheless spliced with opposite winding, so
 * the path stays correct under the nonzero rule too.
 */

/**
 * How big a visual gap between strokes still counts as closed, in scene px.
 *
 * This is a BRIDGING radius, not a snapping radius: gaps are closed by
 * adding short connector edges between loose stroke ends (see the bridging
 * pass in `buildFaces`), never by relocating vertices — so a generous value
 * here does not distort the filled shape.
 */
const BUCKET_FILL_GAP_TOLERANCE = 6;

/**
 * How far apart, in scene px, two fill outlines' bounds may lie and still
 * count as the same region (see `findRestylableBucketFill`). Covers the
 * pipeline's own jitter — polygon simplification (~0.75px) and node
 * canonicalization (`snapEpsilon`) — while staying under typical stroke
 * widths, so "the same region" matches what the user sees.
 */
const BUCKET_FILL_REGION_MATCH_TOLERANCE = 2;

/**
 * How deep inside a coverer, in scene px, a stroke must lie before it counts
 * as hidden (see `clipSegmentToVisible`). A fill's polygon runs along the
 * CENTERLINE of the strokes that bound it, so without a margin the fill —
 * itself a coverer — would clip its own boundary strokes on the next click
 * and adjacent regions would merge. A stroke on a coverer's edge still
 * renders its outer half; only strokes buried deeper than this stay clipped.
 * Sized like `BUCKET_FILL_REGION_MATCH_TOLERANCE`: above the pipeline's own
 * jitter (~0.75px simplification + `snapEpsilon`), below typical visible
 * stroke overlaps.
 */
const BUCKET_FILL_COVER_MARGIN = 2;

/**
 * Max deviation, in scene px, of a curved (`roundness`) line's sampled
 * boundary from its true rendered curve (see `lineElementIdealSegments`).
 * The fidelity knob for fills along curved lines: lower hugs the curve
 * tighter but feeds more segments into the arrangement — cost grows roughly
 * linearly with segment count.
 *
 * Note the final polygon is independently simplified at ~0.75px
 * (`finalizePolygon`), so values much below that add segments without
 * adding visible fidelity.
 */
const BUCKET_FILL_CURVE_MAX_DEVIATION = 0.5;

export type BucketFillOptions = {
  /**
   * geometric fidelity: vertices closer than this collapse to the same graph
   * node, and a node this close to a stroke splits it (T-junction). Keep
   * SMALL — every merge can relocate a vertex by up to this distance, so
   * this value is the upper bound on how far the filled shape may deviate
   * from the actual strokes.
   */
  snapEpsilon: number;
  /**
   * connectivity: loose stroke ends within this distance of another stroke
   * are bridged with a connector edge so the region reads as closed. Also
   * used as broad-phase padding around the owner bounds. Unlike
   * `snapEpsilon` this does not affect the shape's fidelity (bridges add
   * edges; they never move existing vertices).
   */
  gapTolerance: number;
  /** discard faces / polygons smaller than this absolute area */
  minArea: number;
  /** bail out with `too_complex` above this many input segments */
  maxBoundarySegments: number;
  /** cap on the number of generated polygon points */
  maxGeneratedPoints: number;
  /**
   * initial half-extent of the owner-less search box around the click
   * (doubles up to 3 times while the found face touches the box frontier)
   */
  fallbackSearchRadius: number;
};

export const DEFAULT_BUCKET_FILL_OPTIONS: BucketFillOptions = {
  snapEpsilon: 0.5,
  gapTolerance: BUCKET_FILL_GAP_TOLERANCE,
  minArea: 4,
  maxBoundarySegments: 2560,
  maxGeneratedPoints: 1536,
  fallbackSearchRadius: 512,
};

export type BucketFillFailureReason =
  | "no_owner"
  | "open_region"
  | "too_complex"
  | "too_small"
  | "invalid_polygon";

/**
 * Where the generated fill element belongs in the scene order, expressed
 * relative to an existing element so the caller can resolve it against
 * whatever (e.g. deleted-inclusive) array it inserts into.
 */
export type BucketFillInsertion = {
  placement: "above" | "below";
  elementId: ExcalidrawElement["id"];
};

export type BucketFillGeometryResult =
  | {
      ok: true;
      /**
       * the closed element under the click, or null for fills resolved by
       * the owner-less fallback (regions formed by open lines)
       */
      ownerId: ExcalidrawElement["id"] | null;
      boundaryElementIds: ExcalidrawElement["id"][];
      /**
       * closed polygon ring in scene coordinates. When the region contains
       * islands, this is a keyhole path: the hole contours are spliced in
       * via zero-width bridges, so it still renders as one polygon with
       * unpainted hole interiors
       */
      scenePoints: GlobalPoint[];
      insertion: BucketFillInsertion;
    }
  | {
      ok: false;
      reason: BucketFillFailureReason;
    };

// -----------------------------------------------------------------------------
// small geometry helpers
// -----------------------------------------------------------------------------

const expandBounds = ([x1, y1, x2, y2]: Bounds, pad: number): Bounds => [
  x1 - pad,
  y1 - pad,
  x2 + pad,
  y2 + pad,
];

const segmentLength = (s: LineSegment<GlobalPoint>): number =>
  pointDistance(s[0], s[1]);

/** Parametric position of `q` projected onto the line through a-b. */
const projectParam = (
  a: GlobalPoint,
  b: GlobalPoint,
  q: GlobalPoint,
): number => {
  const dx = b[0] - a[0];
  const dy = b[1] - a[1];
  const len2 = dx * dx + dy * dy;
  if (len2 === 0) {
    return 0;
  }
  return ((q[0] - a[0]) * dx + (q[1] - a[1]) * dy) / len2;
};

/**
 * Visit every grid cell (of `cellSize`) that intersects the `inflate`-expanded
 * segment a-b, walking column by column so a long diagonal segment visits the
 * cells it passes near rather than its full bounding box.
 */
const forEachCellAlongSegment = (
  a: GlobalPoint,
  b: GlobalPoint,
  inflate: number,
  cellSize: number,
  visit: (cx: number, cy: number) => void,
): void => {
  const minX = Math.min(a[0], b[0]);
  const maxX = Math.max(a[0], b[0]);
  const dx = b[0] - a[0];
  const dy = b[1] - a[1];
  const fromCx = Math.floor((minX - inflate) / cellSize);
  const toCx = Math.floor((maxX + inflate) / cellSize);
  for (let cx = fromCx; cx <= toCx; cx++) {
    // y-extent of the segment over this column's (inflated) x-interval
    let y0 = a[1];
    let y1 = b[1];
    if (dx !== 0) {
      const t0 = (Math.max(minX, cx * cellSize - inflate) - a[0]) / dx;
      const t1 = (Math.min(maxX, (cx + 1) * cellSize + inflate) - a[0]) / dx;
      y0 = a[1] + t0 * dy;
      y1 = a[1] + t1 * dy;
    }
    const fromCy = Math.floor((Math.min(y0, y1) - inflate) / cellSize);
    const toCy = Math.floor((Math.max(y0, y1) + inflate) / cellSize);
    for (let cy = fromCy; cy <= toCy; cy++) {
      visit(cx, cy);
    }
  }
};

const perpendicularDistance = (
  p: GlobalPoint,
  a: GlobalPoint,
  b: GlobalPoint,
): number => {
  const dx = b[0] - a[0];
  const dy = b[1] - a[1];
  const len = Math.hypot(dx, dy);
  if (len === 0) {
    return pointDistance(p, a);
  }
  return Math.abs((p[0] - a[0]) * dy - (p[1] - a[1]) * dx) / len;
};

const pointAtParam = (a: GlobalPoint, b: GlobalPoint, t: number): GlobalPoint =>
  pointFrom<GlobalPoint>(a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t);

/** Remove the `cuts` parameter intervals from the `base` parameter intervals. */
const subtractIntervals = (
  base: [number, number][],
  cuts: [number, number][],
): [number, number][] => {
  let result = base;
  for (const [c0, c1] of cuts) {
    const next: [number, number][] = [];
    for (const [b0, b1] of result) {
      if (c1 <= b0 || c0 >= b1) {
        next.push([b0, b1]);
        continue;
      }
      if (c0 > b0) {
        next.push([b0, c0]);
      }
      if (c1 < b1) {
        next.push([c1, b1]);
      }
    }
    result = next;
  }
  return result;
};

/**
 * Boundary segments for a line element from its LOGICAL path (the element's
 * points), not its rough rendering.
 *
 * Rough rendering draws lines as two jittery passes; using those as
 * boundaries makes the fill hug the inner pass and leaves an unfilled
 * sliver between the passes. The logical path runs down the stroke's
 * centerline, so the fill straddles the sketchy stroke — exactly how
 * Excalidraw draws shape backgrounds (fill from the ideal path, rough
 * stroke on top). It also makes line endpoints genuine degree-1 graph
 * nodes, which is what the bridging pass keys on.
 *
 * Curved (`roundness`) lines deviate slightly at bends since the points are
 * the pre-smoothing polyline; the stroke width hides it.
 */
const lineElementIdealSegments = (
  element: ExcalidrawLineElement,
  elementsMap: ElementsMap,
): LineSegment<GlobalPoint>[] => {
  const center = elementCenterPoint(element, elementsMap);
  // curved (`roundness`) lines render a smooth curve fitted through the
  // points — sample that same fit (curveToBezier is what roughjs' curve op
  // uses) so the boundary follows what's actually on screen instead of
  // cutting corners along the raw polyline
  const localPoints =
    element.roundness && element.points.length > 2
      ? (pointsOnBezierCurves(
          curveToBezier(element.points as unknown as Point[]),
          // near-exact adaptive subdivision (the lib default); the sample
          // count is then bounded by the RDP pass below, which is the
          // actual fidelity knob
          0.15,
          BUCKET_FILL_CURVE_MAX_DEVIATION,
        ) as unknown as readonly LocalPoint[])
      : element.points;
  const points = localPoints.map((point) =>
    pointRotateRads(
      pointFrom<GlobalPoint>(element.x + point[0], element.y + point[1]),
      center,
      element.angle,
    ),
  );
  const segments: LineSegment<GlobalPoint>[] = [];
  for (let i = 0; i < points.length - 1; i++) {
    segments.push(lineSegment(points[i], points[i + 1]));
  }
  return segments;
};

/**
 * Boundary segments for a freedraw element from its RENDERED centerline
 * (perfect-freehand's streamline-smoothed stroke points), not its raw
 * input points.
 *
 * Raw freedraw points can sit 20px+ apart and the renderer smooths the
 * path between them, so raw chords visibly deviate from the stroke on
 * screen: fills poke out at raw vertices, slivers open along sagging
 * chords, and closures that only exist in the smoothed path (the stroke
 * crossing itself near its start) are missed entirely.
 */
const freedrawIdealSegments = (
  element: ExcalidrawFreeDrawElement,
  elementsMap: ElementsMap,
): LineSegment<GlobalPoint>[] => {
  const center = elementCenterPoint(element, elementsMap);
  const points = getFreedrawStrokeCenterPoints(element).map((point) =>
    pointRotateRads(
      pointFrom<GlobalPoint>(element.x + point[0], element.y + point[1]),
      center,
      element.angle,
    ),
  );
  const segments: LineSegment<GlobalPoint>[] = [];
  for (let i = 0; i < points.length - 1; i++) {
    segments.push(lineSegment(points[i], points[i + 1]));
  }
  return segments;
};

/**
 * Clip a segment to only its visible parts: the portions covered by an opaque
 * (non-transparent background) element above the segment's source are hidden
 * and removed. Returns the visible sub-segments (possibly empty).
 *
 * A portion only counts as covered when it lies inside the coverer by at
 * least `margin` — a stroke whose centerline sits ON a coverer's edge (the
 * shape a fill bounded by that stroke takes) still renders its outer half,
 * so it must keep bounding; see `BUCKET_FILL_COVER_MARGIN`.
 */
const clipSegmentToVisible = (
  a: GlobalPoint,
  b: GlobalPoint,
  coverers: readonly ExcalidrawElement[],
  elementsMap: ElementsMap,
  eps: number,
  margin: number,
): [GlobalPoint, GlobalPoint][] => {
  let intervals: [number, number][] = [[0, 1]];
  for (const coverer of coverers) {
    if (intervals.length === 0) {
      break;
    }
    const hits = intersectElementWithLineSegment(
      coverer,
      elementsMap,
      lineSegment(a, b),
    );
    const breaks = [
      0,
      ...hits
        .map((p) => projectParam(a, b, p))
        .filter((t) => t > 0 && t < 1)
        .sort((x, y) => x - y),
      1,
    ];
    const covered: [number, number][] = [];
    for (let k = 0; k < breaks.length - 1; k++) {
      const t0 = breaks[k];
      const t1 = breaks[k + 1];
      if (t1 - t0 < 1e-9) {
        continue;
      }
      const mid = pointAtParam(a, b, (t0 + t1) / 2);
      if (
        isPointInElement(mid, coverer, elementsMap) &&
        distanceToElement(coverer, elementsMap, mid) > margin
      ) {
        covered.push([t0, t1]);
      }
    }
    if (covered.length) {
      intervals = subtractIntervals(intervals, covered);
    }
  }
  return intervals
    .filter(
      ([t0, t1]) =>
        pointDistance(pointAtParam(a, b, t0), pointAtParam(a, b, t1)) >= eps,
    )
    .map(([t0, t1]) => [pointAtParam(a, b, t0), pointAtParam(a, b, t1)]);
};

/**
 * Spatial-hash node store that merges points within `eps` into one node so the
 * planar graph is free of near-duplicate vertices.
 */
class NodeStore {
  nodes: GlobalPoint[] = [];

  private cells = new Map<string, number[]>();

  private cellSize: number;

  constructor(private eps: number) {
    this.cellSize = Math.max(eps, 1);
  }

  private cellKey(cx: number, cy: number): string {
    return `${cx}:${cy}`;
  }

  getOrCreate(p: GlobalPoint): number {
    const cx = Math.floor(p[0] / this.cellSize);
    const cy = Math.floor(p[1] / this.cellSize);
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const bucket = this.cells.get(this.cellKey(cx + dx, cy + dy));
        if (bucket) {
          for (const idx of bucket) {
            if (pointDistance(this.nodes[idx], p) <= this.eps) {
              return idx;
            }
          }
        }
      }
    }
    const idx = this.nodes.length;
    this.nodes.push(p);
    const key = this.cellKey(cx, cy);
    const bucket = this.cells.get(key);
    if (bucket) {
      bucket.push(idx);
    } else {
      this.cells.set(key, [idx]);
    }
    return idx;
  }

  /**
   * Visit the indices of all nodes within `radius` of `p`. Superset by cell
   * granularity — nodes slightly beyond `radius` may be visited too, so
   * callers must check distances themselves.
   */
  forEachInRadius(
    p: GlobalPoint,
    radius: number,
    visit: (index: number) => void,
  ): void {
    const fromCx = Math.floor((p[0] - radius) / this.cellSize);
    const toCx = Math.floor((p[0] + radius) / this.cellSize);
    const fromCy = Math.floor((p[1] - radius) / this.cellSize);
    const toCy = Math.floor((p[1] + radius) / this.cellSize);
    for (let cx = fromCx; cx <= toCx; cx++) {
      for (let cy = fromCy; cy <= toCy; cy++) {
        const bucket = this.cells.get(this.cellKey(cx, cy));
        if (bucket) {
          for (const index of bucket) {
            visit(index);
          }
        }
      }
    }
  }
}

// -----------------------------------------------------------------------------
// owner & boundary selection
// -----------------------------------------------------------------------------

/**
 * Whether the element visually paints an opaque background fill — i.e. can
 * actually hide outlines beneath it. Element types that never render their
 * `backgroundColor` (text, image, frames), see-through fill styles
 * (hachure/cross-hatch), partial element opacity, and colors with an alpha
 * channel below 1 (`#RRGGBBAA`, `rgba(…)`) all don't count — anything under
 * them shows through.
 *
 * Shared with the app layer's z-order pass so "covers" means the same thing
 * in boundary clipping and in fill insertion.
 */
export const rendersOpaqueFill = (element: ExcalidrawElement): boolean => {
  if (
    !hasBackground(element.type) ||
    element.fillStyle !== "solid" ||
    element.opacity < 100 ||
    !isOpaqueColor(element.backgroundColor)
  ) {
    return false;
  }
  // open strokes never paint their background
  if (
    (isLineElement(element) || isFreeDrawElement(element)) &&
    !isPathALoop(element.points)
  ) {
    return false;
  }
  return true;
};

/**
 * Element types whose outlines can participate in a fill — as the owner
 * (when closed) and as boundaries. Text, image, embeddable, iframe and
 * arrows are excluded in v1.
 */
const FILL_BOUNDARY_TYPES = new Set<ExcalidrawElement["type"]>([
  "rectangle",
  "diamond",
  "ellipse",
  "frame",
  "magicframe",
  "line",
  "freedraw",
]);

/** fully invisible elements never participate in a fill */
const isInvisible = (element: ExcalidrawElement): boolean =>
  element.opacity <= 0;

/**
 * Whether the element renders any pixels at all: a visible stroke (doubles
 * as the text color for text elements), a background its type actually
 * paints, or image content.
 */
const rendersAnyMark = (element: ExcalidrawElement): boolean =>
  !isInvisible(element) &&
  (element.type === "image" ||
    !isTransparent(element.strokeColor) ||
    (hasBackground(element.type) && !isTransparent(element.backgroundColor)));

/**
 * Whether the element renders as pure paint the bucket tool could have
 * produced: a closed, visible line polygon with a background and no visible
 * stroke. Recognition is by SHAPE, not by a metadata marker — any marker
 * would go stale the moment the user restyles a fill, and a hand-drawn
 * strokeless background polygon is indistinguishable from a generated fill
 * anyway. Such paint never becomes an owner and is what the app layer
 * restyles in place on re-click (see `isRestylableFill`).
 */
export const isBucketFillCompatible = (
  element: ExcalidrawElement,
): element is ExcalidrawLineElement =>
  isLineElement(element) &&
  element.polygon &&
  isValidPolygon(element.points) &&
  !isInvisible(element) &&
  !isTransparent(element.backgroundColor) &&
  isTransparent(element.strokeColor);

const isClosedOwnerCandidate = (element: ExcalidrawElement): boolean => {
  if (!FILL_BOUNDARY_TYPES.has(element.type)) {
    return false;
  }
  if (isLineElement(element)) {
    return element.polygon && isValidPolygon(element.points);
  }
  if (isFreeDrawElement(element)) {
    return isPathALoop(element.points);
  }
  return true;
};

// Boundary and coverer roles are decided by VISIBILITY, not provenance:
// generated fills participate like any other element. In practice their
// default transparent stroke keeps them out of the boundary set — but once
// the user gives a fill a visible stroke, that outline genuinely bounds
// regions on screen and must bound new fills too.
const isEligibleBoundary = (element: ExcalidrawElement): boolean =>
  !isInvisible(element) &&
  FILL_BOUNDARY_TYPES.has(element.type) &&
  // skip outlines that don't render a visible stroke
  !isTransparent(element.strokeColor);

const findOwner = (
  point: GlobalPoint,
  elements: readonly NonDeletedExcalidrawElement[],
  elementsMap: ElementsMap,
): NonDeletedExcalidrawElement | null => {
  for (let i = elements.length - 1; i >= 0; i--) {
    const element = elements[i];
    // fill-compatible paint is deliberately never an OWNER (unlike its
    // boundary / coverer roles): re-clicking a filled region should either
    // restyle the paint (app layer) or re-derive the region from the
    // actual strokes, not from the previous fill's ring — and keyhole
    // rings (zero-width bridges) make degenerate owner outlines.
    // Elements that render no pixels can't own either — an invisible
    // (transparent stroke + transparent background) shape would otherwise
    // let a click on seemingly empty canvas conjure a fill out of nowhere.
    if (!rendersAnyMark(element) || isBucketFillCompatible(element)) {
      continue;
    }
    if (!isClosedOwnerCandidate(element)) {
      continue;
    }
    if (isPointInElement(point, element, elementsMap)) {
      return element;
    }
  }
  return null;
};

// -----------------------------------------------------------------------------
// planar arrangement + face extraction
// -----------------------------------------------------------------------------

type WorkingSegment = {
  a: number;
  b: number;
  pa: GlobalPoint;
  pb: GlobalPoint;
  box: Bounds;
  elementId: string;
  splits: { node: number; t: number }[];
};

/** A segment paired with the element it was extracted from. */
type SourceSegment = {
  segment: LineSegment<GlobalPoint>;
  elementId: string;
};

/** An extracted face ring plus the ids of the elements whose outlines bound it. */
type Face = {
  ring: GlobalPoint[];
  contributors: Set<string>;
  /**
   * connected component of the arrangement graph this face belongs to —
   * faces of OTHER components lying inside a selected face are islands
   * (holes), while faces of the same component are just its subdivisions
   */
  componentId: number;
};

/**
 * Build the planar straight-line graph from the input segments (split at
 * intersections and T-junctions) and extract its face rings. Each face records
 * which source elements contributed an edge to its boundary.
 *
 * Returns `[]` when there are no usable edges (no enclosed region), or `null`
 * when the arrangement is too complex to process.
 *
 * Collinear/overlapping segments need no dedicated pass: a 1D overlap always
 * puts at least one segment's endpoint (a node) on the other segment, so the
 * T-junction pass splits them and `addEdge`'s node-pair dedupe collapses the
 * coincident pieces into one edge.
 */
const buildFaces = (
  rawSegments: SourceSegment[],
  options: BucketFillOptions,
): Face[] | null => {
  const eps = options.snapEpsilon;
  // Two distinct radii, deliberately decoupled:
  // - `eps` (snapEpsilon) governs node merging and T-junction snapping. It
  //   must stay small: merging RELOCATES vertices to the first-seen position
  //   and T-junctions route edges THROUGH off-stroke nodes, so this radius
  //   is the upper bound on how far the filled shape can deviate from the
  //   actual strokes.
  // - `gapTolerance` governs the bridging pass further down, which closes
  //   visual gaps by ADDING short connector edges at loose stroke ends. It
  //   can be generous (see BUCKET_FILL_GAP_TOLERANCE) without distorting
  //   the shape, because bridging never moves existing vertices.
  const store = new NodeStore(eps);
  const segments: WorkingSegment[] = [];
  // first element that produced each node — used to attribute bridge edges
  const nodeElement = new Map<number, string>();

  for (const { segment, elementId } of rawSegments) {
    // NOTE: sub-epsilon segments are NOT dropped here — their endpoints merge
    // into the same node (a === b below) which collapses them while keeping
    // the outline chain connected. Dropping them instead would disconnect
    // densely subdivided curves (e.g. the tiny corner arcs a diamond has even
    // with roundness: null) and leave the region open.
    const a = store.getOrCreate(segment[0]);
    const b = store.getOrCreate(segment[1]);
    if (!nodeElement.has(a)) {
      nodeElement.set(a, elementId);
    }
    if (!nodeElement.has(b)) {
      nodeElement.set(b, elementId);
    }
    if (a === b) {
      continue;
    }
    const pa = store.nodes[a];
    const pb = store.nodes[b];
    segments.push({
      a,
      b,
      pa,
      pb,
      elementId,
      box: [
        Math.min(pa[0], pb[0]),
        Math.min(pa[1], pb[1]),
        Math.max(pa[0], pb[0]),
        Math.max(pa[1], pb[1]),
      ],
      splits: [
        { node: a, t: 0 },
        { node: b, t: 1 },
      ],
    });
  }

  const segLines = segments.map((s) => lineSegment(s.pa, s.pb));

  // transversal intersections. Broad phase: sort by bbox minX and sweep, so
  // every candidate pair is tested at most once. A segment grid is a poor fit
  // here: dense overlapping segments share many consecutive cells, and even
  // deduping the geometry test still re-enumerates every pair in every cell.
  const byMinX = segments
    .map((_, index) => index)
    .sort((a, b) => segments[a].box[0] - segments[b].box[0]);
  for (let oi = 0; oi < byMinX.length; oi++) {
    const i = byMinX[oi];
    const si = segments[i];
    const sweepMaxX = si.box[2] + eps;
    for (let oj = oi + 1; oj < byMinX.length; oj++) {
      const j = byMinX[oj];
      const sj = segments[j];
      if (sj.box[0] > sweepMaxX) {
        break;
      }
      if (!doBoundsIntersect(expandBounds(si.box, eps), sj.box)) {
        continue;
      }
      const intersection = lineSegmentIntersectionPoints(
        segLines[i],
        segLines[j],
        eps,
      );
      if (!intersection) {
        continue;
      }
      const node = store.getOrCreate(intersection);
      // intersection nodes need a source too — one may end up a loose end
      // (after visibility clipping) and get bridged, and bridge attribution
      // reads `nodeElement`
      if (!nodeElement.has(node)) {
        nodeElement.set(node, si.elementId);
      }
      si.splits.push({
        node,
        t: projectParam(si.pa, si.pb, store.nodes[node]),
      });
      sj.splits.push({
        node,
        t: projectParam(sj.pa, sj.pb, store.nodes[node]),
      });
    }
  }

  // safety: intersection splitting can inflate the node count quadratically
  // in pathological scenes; bail before the downstream passes (T-junctions,
  // edge emission, face extraction) turn a click into a multi-second freeze
  if (store.nodes.length > options.maxBoundarySegments * 4) {
    return null;
  }

  // Broad phase for the T-junction pass: insert each segment into the cells
  // along its path inflated by `eps`. Cell size scales with the scene extent
  // so even a scene-spanning segment walks a bounded number of cells.
  let sceneMinX = Infinity;
  let sceneMinY = Infinity;
  let sceneMaxX = -Infinity;
  let sceneMaxY = -Infinity;
  for (const s of segments) {
    sceneMinX = Math.min(sceneMinX, s.box[0]);
    sceneMinY = Math.min(sceneMinY, s.box[1]);
    sceneMaxX = Math.max(sceneMaxX, s.box[2]);
    sceneMaxY = Math.max(sceneMaxY, s.box[3]);
  }
  const sceneSpan = Math.max(sceneMaxX - sceneMinX, sceneMaxY - sceneMinY, 0);
  const segCellSize = Math.max(eps * 2, sceneSpan / 128);
  const segGrid = new Map<string, number[]>();
  segments.forEach((s, index) => {
    forEachCellAlongSegment(s.pa, s.pb, eps, segCellSize, (cx, cy) => {
      const key = `${cx}:${cy}`;
      const bucket = segGrid.get(key);
      if (bucket) {
        bucket.push(index);
      } else {
        segGrid.set(key, [index]);
      }
    });
  });

  // T-junctions: split any segment that passes through (within `eps` of) an
  // existing node. Deliberately tight — routing an edge through a node that
  // sits further off the stroke would visibly bend the filled shape; wider
  // gaps are closed by the bridging pass below instead.
  // Broad phase: each node tests only the segments sharing its grid cell —
  // the eps-inflated insertion guarantees any segment within `eps` of the
  // node is in the node's own cell. (The node set is stable during this
  // pass — no nodes are created here, so the grid stays complete.)
  for (let n = 0; n < store.nodes.length; n++) {
    const q = store.nodes[n];
    const bucket = segGrid.get(
      `${Math.floor(q[0] / segCellSize)}:${Math.floor(q[1] / segCellSize)}`,
    );
    if (!bucket) {
      continue;
    }
    for (const index of bucket) {
      const segment = segments[index];
      if (n === segment.a || n === segment.b) {
        continue;
      }
      const t = projectParam(segment.pa, segment.pb, q);
      if (t <= 0 || t >= 1) {
        continue;
      }
      if (distanceToLineSegment(q, segLines[index]) <= eps) {
        segment.splits.push({ node: n, t });
      }
    }
  }

  // emit atomic edges
  const edgeSet = new Set<string>();
  const adjacency = new Map<number, number[]>();
  // atomic edge -> ids of the elements whose segments produced it
  const edgeToElements = new Map<string, Set<string>>();
  const edgeKey = (u: number, v: number) => (u < v ? `${u}-${v}` : `${v}-${u}`);
  const link = (u: number, v: number) => {
    const list = adjacency.get(u);
    if (list) {
      list.push(v);
    } else {
      adjacency.set(u, [v]);
    }
  };
  const addEdge = (u: number, v: number, elementId: string) => {
    if (u === v) {
      return;
    }
    if (pointDistance(store.nodes[u], store.nodes[v]) < eps) {
      return;
    }
    const key = edgeKey(u, v);
    const owners = edgeToElements.get(key);
    if (owners) {
      owners.add(elementId);
    } else {
      edgeToElements.set(key, new Set([elementId]));
    }
    if (edgeSet.has(key)) {
      return;
    }
    edgeSet.add(key);
    link(u, v);
    link(v, u);
  };

  for (const segment of segments) {
    const byNode = new Map<number, number>();
    for (const split of segment.splits) {
      if (!byNode.has(split.node)) {
        byNode.set(split.node, split.t);
      }
    }
    const ordered = [...byNode.entries()]
      .map(([node, t]) => ({ node, t }))
      .sort((a, b) => a.t - b.t);
    for (let k = 0; k < ordered.length - 1; k++) {
      addEdge(ordered[k].node, ordered[k + 1].node, segment.elementId);
    }
  }

  if (edgeSet.size === 0) {
    // nothing usable — not an error, just no enclosed region
    return [];
  }

  // ---------------------------------------------------------------------------
  // bridging pass — close visual gaps up to `gapTolerance` so sketchy joints
  // (a stroke stopping a few px short of another) still enclose a region.
  //
  // Additive by design: each dangling stroke end gets a short connector EDGE
  // to its nearest reachable geometry — either an existing node, or a point
  // ON a nearby edge (the edge is split at the projection, which lies
  // exactly on the stroke). Existing vertices are never relocated, so unlike
  // snapping, a generous radius here cannot distort the filled shape — the
  // worst artifact is a tiny connector edge spanning the visual gap,
  // typically hidden under the stroke width.
  //
  // A dangling end is simply a degree-1 node. This relies on boundaries
  // being single-pass paths: line elements use their logical points (see
  // `lineElementIdealSegments`), freedraw its smoothed centerline (see
  // `freedrawIdealSegments`), and closed shapes their ideal outlines —
  // none of them produce the rough renderer's double-pass geometry, whose
  // ends would be degree-2.
  // ---------------------------------------------------------------------------
  const bridgeRadius = Math.max(eps, options.gapTolerance);
  const isDanglingEnd = (node: number): boolean =>
    new Set(adjacency.get(node) ?? []).size === 1;
  const looseEnds: number[] = [];
  for (const node of adjacency.keys()) {
    if (isDanglingEnd(node)) {
      looseEnds.push(node);
    }
  }
  if (looseEnds.length > 0) {
    // spatial hash of live edges, updated as bridging splits edges / adds
    // connectors. Cells are at least `bridgeRadius` wide so any edge within
    // the radius of a query point lies in the point's 3×3 cell
    // neighbourhood. Entries are never removed — edges deleted by `unlink`
    // are filtered out on lookup via `edgeSet`
    // Keep the arrangement's longest axis to roughly 128 cells. The cell size
    // remains at least `bridgeRadius`, so every edge within that radius is
    // still guaranteed to lie in the query point's 3×3 neighbourhood.
    const edgeCellSize = Math.max(bridgeRadius, sceneSpan / 128, 1);
    const edgeGrid = new Map<string, { u: number; v: number }[]>();
    const insertLiveEdge = (u: number, v: number) => {
      const edge = { u, v };
      forEachCellAlongSegment(
        store.nodes[u],
        store.nodes[v],
        0,
        edgeCellSize,
        (cx, cy) => {
          const key = `${cx}:${cy}`;
          const bucket = edgeGrid.get(key);
          if (bucket) {
            bucket.push(edge);
          } else {
            edgeGrid.set(key, [edge]);
          }
        },
      );
    };
    for (const key of edgeSet) {
      const [u, v] = key.split("-").map(Number);
      insertLiveEdge(u, v);
    }
    const unlink = (u: number, v: number) => {
      const key = edgeKey(u, v);
      edgeSet.delete(key);
      const owners = edgeToElements.get(key);
      edgeToElements.delete(key);
      const listU = adjacency.get(u);
      const listV = adjacency.get(v);
      listU?.splice(listU.indexOf(v), 1);
      listV?.splice(listV.indexOf(u), 1);
      return owners;
    };

    for (const loose of looseEnds) {
      // skip ends already closed by an earlier bridge
      if (!isDanglingEnd(loose)) {
        continue;
      }
      const p = store.nodes[loose];
      const neighbours = adjacency.get(loose) ?? [];

      // nearest non-adjacent node within the bridge radius. Candidates
      // closer than the snap epsilon are skipped — they're effectively the
      // same point and `addEdge` refuses such degenerate edges anyway
      let bestNode = -1;
      let bestNodeDistance = Infinity;
      store.forEachInRadius(p, bridgeRadius, (n) => {
        if (n === loose || neighbours.includes(n)) {
          return;
        }
        const distance = pointDistance(p, store.nodes[n]);
        if (
          distance >= eps &&
          distance <= bridgeRadius &&
          distance < bestNodeDistance
        ) {
          bestNodeDistance = distance;
          bestNode = n;
        }
      });

      // nearest edge (not incident to the loose end) whose interior the
      // loose end projects onto, within the bridge radius
      let bestEdge: { u: number; v: number } | null = null;
      let bestEdgeDistance = Infinity;
      let bestEdgeT = 0;
      const looseCx = Math.floor(p[0] / edgeCellSize);
      const looseCy = Math.floor(p[1] / edgeCellSize);
      // an edge spans multiple cells, so it can show up in several of the 9
      // inspected buckets
      const seenEdges = new Set<string>();
      for (let dcx = -1; dcx <= 1; dcx++) {
        for (let dcy = -1; dcy <= 1; dcy++) {
          const bucket = edgeGrid.get(`${looseCx + dcx}:${looseCy + dcy}`);
          if (!bucket) {
            continue;
          }
          for (const edge of bucket) {
            const key = edgeKey(edge.u, edge.v);
            if (seenEdges.has(key)) {
              continue;
            }
            seenEdges.add(key);
            if (!edgeSet.has(key) || edge.u === loose || edge.v === loose) {
              continue;
            }
            const eu = store.nodes[edge.u];
            const ev = store.nodes[edge.v];
            const t = projectParam(eu, ev, p);
            if (t <= 0 || t >= 1) {
              continue;
            }
            const distance = distanceToLineSegment(p, lineSegment(eu, ev));
            if (distance <= bridgeRadius && distance < bestEdgeDistance) {
              bestEdgeDistance = distance;
              bestEdge = edge;
              bestEdgeT = t;
            }
          }
        }
      }

      const bridgeElement =
        // every node gets a source at creation; the fallback is defensive
        nodeElement.get(loose) ?? segments[0].elementId;
      if (bestEdge && bestEdgeDistance < bestNodeDistance) {
        // split the edge at the projection (a point ON the stroke) and
        // connect the loose end to it
        const eu = store.nodes[bestEdge.u];
        const ev = store.nodes[bestEdge.v];
        const projection = store.getOrCreate(pointAtParam(eu, ev, bestEdgeT));
        if (projection === bestEdge.u || projection === bestEdge.v) {
          // projection merged into an endpoint — plain node bridge
          addEdge(loose, projection, bridgeElement);
          insertLiveEdge(loose, projection);
        } else {
          if (!nodeElement.has(projection)) {
            nodeElement.set(
              projection,
              edgeToElements
                .get(edgeKey(bestEdge.u, bestEdge.v))
                ?.values()
                .next().value ?? bridgeElement,
            );
          }
          const owners =
            unlink(bestEdge.u, bestEdge.v) ?? new Set([bridgeElement]);
          for (const owner of owners) {
            addEdge(bestEdge.u, projection, owner);
            addEdge(projection, bestEdge.v, owner);
          }
          insertLiveEdge(bestEdge.u, projection);
          insertLiveEdge(projection, bestEdge.v);
          addEdge(loose, projection, bridgeElement);
          insertLiveEdge(loose, projection);
        }
      } else if (bestNode >= 0) {
        addEdge(loose, bestNode, bridgeElement);
        insertLiveEdge(loose, bestNode);
      }
    }
  }

  // connected components of the final graph (bridges included, so a bridged
  // island shares a component with what it bridged to and can't become a
  // hole) — used to tell true islands from same-component subdivisions
  const componentOf = new Map<number, number>();
  let componentCount = 0;
  for (const start of adjacency.keys()) {
    if (componentOf.has(start)) {
      continue;
    }
    const queue = [start];
    componentOf.set(start, componentCount);
    while (queue.length) {
      const node = queue.pop()!;
      for (const neighbour of adjacency.get(node) ?? []) {
        if (!componentOf.has(neighbour)) {
          componentOf.set(neighbour, componentCount);
          queue.push(neighbour);
        }
      }
    }
    componentCount++;
  }

  // sort outgoing half-edges by angle around each node
  const angleOf = (from: number, to: number): number =>
    Math.atan2(
      store.nodes[to][1] - store.nodes[from][1],
      store.nodes[to][0] - store.nodes[from][0],
    );
  const sortedOut = new Map<number, number[]>();
  const positionOf = new Map<number, Map<number, number>>();
  for (const [node, neighbours] of adjacency) {
    const unique = Array.from(new Set(neighbours));
    unique.sort((p, q) => angleOf(node, p) - angleOf(node, q));
    sortedOut.set(node, unique);
    const positions = new Map<number, number>();
    unique.forEach((neighbour, index) => positions.set(neighbour, index));
    positionOf.set(node, positions);
  }

  // walk half-edges into face rings
  const visited = new Set<string>();
  const faces: Face[] = [];
  const maxSteps = edgeSet.size * 2 + 4;
  for (const [node, neighbours] of adjacency) {
    for (const first of neighbours) {
      if (visited.has(`${node}->${first}`)) {
        continue;
      }
      const ring: number[] = [];
      let from = node;
      let to = first;
      let steps = 0;
      while (steps++ <= maxSteps) {
        visited.add(`${from}->${to}`);
        ring.push(from);
        const outs = sortedOut.get(to)!;
        const twinPosition = positionOf.get(to)!.get(from)!;
        // the next edge in the face is the one immediately clockwise from the
        // reverse (twin) direction
        const nextPosition = (twinPosition - 1 + outs.length) % outs.length;
        const next = outs[nextPosition];
        from = to;
        to = next;
        if (from === node && to === first) {
          break;
        }
      }
      if (ring.length >= 3) {
        const contributors = new Set<string>();
        for (let k = 0; k < ring.length; k++) {
          const owners = edgeToElements.get(
            edgeKey(ring[k], ring[(k + 1) % ring.length]),
          );
          if (owners) {
            for (const id of owners) {
              contributors.add(id);
            }
          }
        }
        faces.push({
          ring: ring.map((index) => store.nodes[index]),
          contributors,
          componentId: componentOf.get(node) ?? -1,
        });
      }
    }
  }

  return faces;
};

type FaceSelection = {
  face: Face;
  /** island contours to punch out of the face — see `selectFaceFromArrangement` */
  holes: Face[];
};

/**
 * Select the smallest bounded face that contains the click point. The single
 * unbounded face has the largest absolute area; faces sharing its orientation
 * are skipped, which leaves only true (bounded) cells.
 *
 * Also collects the face's holes: each disconnected component has exactly one
 * outer-orientation ring (its outside contour), and when that contour lies
 * inside the selected face the component is an island the flood fill must
 * flow around. Only outermost islands count — an island nested inside
 * another island already sits inside a hole.
 */
const selectFaceFromArrangement = (
  faces: Face[],
  point: GlobalPoint,
  options: BucketFillOptions,
): FaceSelection | null => {
  if (faces.length === 0) {
    return null;
  }

  // The half-edge walk ("next = the neighbour immediately clockwise of the
  // twin", in screen coordinates with y pointing down) traces every BOUNDED
  // face with negative shoelace area and every component's outside contour
  // with positive area — a structural invariant of the walk rule. Bounded vs
  // unbounded must be decided by this sign alone, NOT by comparing areas:
  // the outermost outline's interior face and outside contour trace the same
  // polygon with equal |area|, so any size-based heuristic degenerates into
  // an enumeration-order coin flip (which made hole detection depend on
  // element order/position — see the overlapping-islands regression tests).
  const outerSign = 1;
  const areaOf = new Map<Face, number>();
  for (const face of faces) {
    // negated: polygonSignedArea is CCW-positive, while the invariant above
    // is stated in the opposite (bounded-faces-negative) convention
    areaOf.set(face, -polygonSignedArea(face.ring, 0));
  }

  let best: Face | null = null;
  let bestArea = Infinity;
  for (const face of faces) {
    const area = areaOf.get(face)!;
    if (Math.sign(area) === outerSign) {
      continue;
    }
    const absArea = Math.abs(area);
    if (absArea < options.minArea) {
      continue;
    }
    if (!polygonIncludesPointNonZero(point, face.ring)) {
      continue;
    }
    if (absArea < bestArea) {
      bestArea = absArea;
      best = face;
    }
  }

  if (!best) {
    return null;
  }
  const selected = best;

  const islandCandidates = faces.filter(
    (face) =>
      face.componentId !== selected.componentId &&
      // a component's outside contour shares the unbounded face's orientation
      Math.sign(areaOf.get(face)!) === outerSign &&
      Math.abs(areaOf.get(face)!) >= options.minArea &&
      // the click face never sits inside one of its own holes (defensive —
      // the smallest-containing-face selection above already guarantees it)
      !polygonIncludesPointNonZero(point, face.ring) &&
      // components never intersect (crossings would have merged them), so a
      // single-vertex test decides containment
      polygonIncludesPointNonZero(face.ring[0], selected.ring),
  );
  const holes = islandCandidates.filter(
    (hole) =>
      !islandCandidates.some(
        (other) =>
          other !== hole &&
          polygonIncludesPointNonZero(hole.ring[0], other.ring),
      ),
  );

  return { face: selected, holes };
};

// -----------------------------------------------------------------------------
// simplification
// -----------------------------------------------------------------------------

const dedupeConsecutive = (pts: GlobalPoint[], eps: number): GlobalPoint[] => {
  const out: GlobalPoint[] = [];
  for (const p of pts) {
    if (out.length === 0 || pointDistance(out[out.length - 1], p) >= eps) {
      out.push(p);
    }
  }
  while (out.length > 1 && pointDistance(out[0], out[out.length - 1]) < eps) {
    out.pop();
  }
  return out;
};

const removeCollinear = (
  pts: GlobalPoint[],
  tolerance: number,
): GlobalPoint[] => {
  if (pts.length <= 3) {
    return pts;
  }
  const out: GlobalPoint[] = [];
  for (let i = 0; i < pts.length; i++) {
    const prev = out[out.length - 1] ?? pts[pts.length - 1];
    const next = pts[(i + 1) % pts.length];
    if (perpendicularDistance(pts[i], prev, next) >= tolerance) {
      out.push(pts[i]);
    }
  }
  return out.length >= 3 ? out : pts;
};

/**
 * Simplify an open ring under a point budget. Returns null when it collapses
 * below a triangle or cannot fit the budget.
 */
const simplifyRing = (
  ring: GlobalPoint[],
  options: BucketFillOptions,
  budget: number,
): GlobalPoint[] | null => {
  const pts = dedupeConsecutive(ring, options.snapEpsilon);
  if (pts.length < 3) {
    return null;
  }

  // Ramer–Douglas–Peucker via the same `simplify` the freedraw renderer
  // uses (identical default tolerance), escalating until under the point cap
  let tolerance = 0.75;
  let simplified = simplify(pts, tolerance) as GlobalPoint[];
  while (simplified.length > budget && tolerance < 1e6) {
    tolerance *= 2;
    simplified = simplify(pts, tolerance) as GlobalPoint[];
  }
  if (simplified.length > budget) {
    return null;
  }

  simplified = removeCollinear(simplified, 0.05);
  return simplified.length >= 3 ? simplified : null;
};

/**
 * Splice a hole contour into the ring as a zero-width "keyhole": walk the
 * ring to the attachment vertex, bridge to the hole, traverse the hole, and
 * bridge back along the same edge. The doubled bridge cancels under the
 * even-odd rule the renderer uses for looped-line fills (and under the
 * pattern fills' scanline parity), leaving the hole interior unpainted
 * while the result stays one closed polygon.
 */
const spliceHoleIntoRing = (
  ring: GlobalPoint[],
  hole: GlobalPoint[],
): GlobalPoint[] => {
  // opposite winding: even-odd doesn't care, but this keeps the path
  // correct under the nonzero rule as well (defense against renderer or
  // export changes)
  const oriented =
    Math.sign(polygonSignedArea(hole, 0)) ===
    Math.sign(polygonSignedArea(ring, 0))
      ? [...hole].reverse()
      : hole;

  // shortest bridge, so the (invisible) channel never spans the region
  let bestRingIndex = 0;
  let bestHoleIndex = 0;
  let bestDistance = Infinity;
  for (let i = 0; i < ring.length; i++) {
    for (let j = 0; j < oriented.length; j++) {
      const distance = pointDistance(ring[i], oriented[j]);
      if (distance < bestDistance) {
        bestDistance = distance;
        bestRingIndex = i;
        bestHoleIndex = j;
      }
    }
  }

  const out: GlobalPoint[] = ring.slice(0, bestRingIndex + 1);
  // full hole loop, ending back on its attachment vertex
  for (let k = 0; k <= oriented.length; k++) {
    out.push(oriented[(bestHoleIndex + k) % oriented.length]);
  }
  out.push(ring[bestRingIndex]);
  out.push(...ring.slice(bestRingIndex + 1));
  return out;
};

/**
 * Simplify the face ring and its hole contours (each independently, so the
 * keyhole bridges stay exactly zero-width), splice the holes in, and return
 * the result explicitly closed (first point repeated as last), along with
 * the indices of the holes that were actually spliced. Returns null when
 * the outer ring cannot form a valid polygon; holes that cannot fit the
 * remaining point budget are dropped (the island then just gets painted
 * over, the pre-hole-support behavior).
 */
const finalizePolygon = (
  outerRing: GlobalPoint[],
  holeRings: GlobalPoint[][],
  options: BucketFillOptions,
): { scenePoints: GlobalPoint[]; splicedHoleIndices: number[] } | null => {
  let ring = simplifyRing(outerRing, options, options.maxGeneratedPoints);
  if (!ring) {
    return null;
  }

  // largest first, so a tight point budget drops the least visible islands
  const byAreaDesc = holeRings
    .map((holeRing, index) => ({ holeRing, index }))
    .sort((a, b) => polygonArea(b.holeRing, 0) - polygonArea(a.holeRing, 0));
  const splicedHoleIndices: number[] = [];
  for (const { holeRing, index } of byAreaDesc) {
    // a spliced hole costs its own points + 2 bridge duplicates
    const budget = options.maxGeneratedPoints - ring.length - 2;
    if (budget < 3) {
      break;
    }
    const hole = simplifyRing(holeRing, options, budget);
    if (!hole) {
      continue;
    }
    ring = spliceHoleIntoRing(ring, hole);
    splicedHoleIndices.push(index);
  }

  // close the polygon exactly once
  return { scenePoints: [...ring, ring[0]], splicedHoleIndices };
};

// -----------------------------------------------------------------------------
// public API
// -----------------------------------------------------------------------------

export const computeBucketFillPolygon = (args: {
  point: GlobalPoint;
  elements: readonly NonDeletedExcalidrawElement[];
  elementsMap: ElementsMap;
  options?: Partial<BucketFillOptions>;
}): BucketFillGeometryResult => {
  const options = { ...DEFAULT_BUCKET_FILL_OPTIONS, ...args.options };
  const { point, elements, elementsMap } = args;

  // 1. owner under the pointer — the fast common case (click inside a closed
  // element). When there is none (regions formed by open lines, or
  // self-intersecting outlines whose hit-test fails), the owner-less
  // fallback below builds the arrangement from everything near the click.
  const owner = findOwner(point, elements, elementsMap);

  const indexOf = new Map<string, number>();
  elements.forEach((element, i) => indexOf.set(element.id, i));

  // 2+3. collect boundary segments within `candidateBounds`, tagged with
  // their source element and clipped to their visible parts (portions hidden
  // behind an opaque element above are not boundaries — only what the user
  // actually sees can stop fill). Returns null when over the segment cap.
  const collectSegments = (
    candidateBounds: Bounds,
    primary: NonDeletedExcalidrawElement | null,
  ): SourceSegment[] | null => {
    const inRange = (element: ExcalidrawElement) =>
      doBoundsIntersect(
        candidateBounds,
        getElementBounds(element, elementsMap),
      );
    const boundaries = elements.filter(
      (element) =>
        element.id !== primary?.id &&
        isEligibleBoundary(element) &&
        inRange(element),
    );
    // the opaque elements that hide outlines beneath them — including
    // existing bucket fills: an outline buried under an opaque fill is
    // invisible, so it must not stop a new fill either
    const coverers = elements.filter(
      (element) => rendersOpaqueFill(element) && inRange(element),
    );

    const rawSegments: SourceSegment[] = [];
    const collect = (element: ExcalidrawElement) => {
      const elementIndex = indexOf.get(element.id) ?? 0;
      const coverersAbove = coverers.filter(
        (coverer) =>
          coverer.id !== element.id &&
          (indexOf.get(coverer.id) ?? 0) > elementIndex,
      );
      // half this element's stroke still renders when its centerline lies on
      // a coverer's edge — never treat that band as hidden
      const clipMargin = Math.max(
        options.snapEpsilon,
        element.strokeWidth / 2,
        BUCKET_FILL_COVER_MARGIN,
      );
      const segments = isLineElement(element)
        ? lineElementIdealSegments(element, elementsMap)
        : isFreeDrawElement(element)
        ? freedrawIdealSegments(element, elementsMap)
        : getElementLineSegments(element, elementsMap);
      // freedraw and non-polygon line loops render as closed once their
      // endpoints are within LINE_CONFIRM_THRESHOLD (isPathALoop), but their
      // segment chain leaves that closure gap open — bridge it explicitly so
      // the region reads as closed here too. Deliberately isPathALoop (the
      // renderer's own closure rule), NOT gapTolerance: whether an element
      // paints its background must match whether fill treats it as closed.
      if (
        (element.type === "freedraw" ||
          (isLineElement(element) && !element.polygon)) &&
        isPathALoop(element.points) &&
        segments.length > 0
      ) {
        const first = segments[0][0];
        const last = segments[segments.length - 1][1];
        if (pointDistance(first, last) >= options.snapEpsilon) {
          segments.push(lineSegment(last, first));
        }
      }
      for (const segment of segments) {
        // enforce the segment budget WHILE collecting: without this, a huge
        // scene does all the expensive visibility clipping before the cap
        // is ever consulted
        if (rawSegments.length > options.maxBoundarySegments) {
          return;
        }
        // keep sub-epsilon segments: buildFaces collapses them via node
        // merging without breaking the chain (see note there); only true
        // zero-length degenerates are noise
        if (segmentLength(segment) === 0) {
          continue;
        }
        if (coverersAbove.length === 0) {
          rawSegments.push({ segment, elementId: element.id });
          continue;
        }
        for (const [a, b] of clipSegmentToVisible(
          segment[0],
          segment[1],
          coverersAbove,
          elementsMap,
          options.snapEpsilon,
          clipMargin,
        )) {
          rawSegments.push({
            segment: lineSegment(a, b),
            elementId: element.id,
          });
        }
      }
    };
    for (const element of primary ? [primary, ...boundaries] : boundaries) {
      if (rawSegments.length > options.maxBoundarySegments) {
        break;
      }
      collect(element);
    }
    return rawSegments.length > options.maxBoundarySegments
      ? null
      : rawSegments;
  };

  const buildAndSelect = (
    rawSegments: SourceSegment[],
  ): FaceSelection | null | "too_complex" => {
    const faces = buildFaces(rawSegments, options);
    if (!faces) {
      return "too_complex";
    }
    return selectFaceFromArrangement(faces, point, options);
  };

  // 4. resolve the face under the click
  let selection: FaceSelection | null = null;
  if (owner) {
    const pad = options.gapTolerance + 2 + Math.max(owner.strokeWidth ?? 1, 1);
    const searchBounds = expandBounds(
      getElementBounds(owner, elementsMap),
      pad,
    );
    const rawSegments = collectSegments(searchBounds, owner);
    if (!rawSegments) {
      return { ok: false, reason: "too_complex" };
    }
    const selected = buildAndSelect(rawSegments);
    if (selected === "too_complex") {
      return { ok: false, reason: "too_complex" };
    }
    if (!selected) {
      return { ok: false, reason: "open_region" };
    }
    selection = selected;
  } else {
    // owner-less fallback: search an expanding box around the click. A face
    // is final once its ring stays clear of the box frontier — any element
    // that could still subdivide it would intersect the box and is already
    // included; a ring touching the frontier may be missing far-away
    // boundaries, so grow and retry.
    const totalEligible = elements.reduce(
      (count, element) => count + (isEligibleBoundary(element) ? 1 : 0),
      0,
    );
    if (totalEligible === 0) {
      return { ok: false, reason: "no_owner" };
    }
    let radius = options.fallbackSearchRadius;
    for (let attempt = 0; attempt < 4 && !selection; attempt++, radius *= 2) {
      const box: Bounds = [
        point[0] - radius,
        point[1] - radius,
        point[0] + radius,
        point[1] + radius,
      ];
      const inRange = elements.reduce(
        (count, element) =>
          count +
          (isEligibleBoundary(element) &&
          doBoundsIntersect(box, getElementBounds(element, elementsMap))
            ? 1
            : 0),
        0,
      );
      // every eligible element is in range: whatever this box yields is
      // FINAL — a bigger box would rebuild the identical arrangement, and
      // the frontier heuristic below only exists to approximate exactly
      // this condition
      const isFinalAttempt = attempt === 3 || inRange === totalEligible;
      if (inRange === 0) {
        // empty at this radius — the region may still lie farther out, so
        // keep growing (a distant enclosure, e.g. a huge line square whose
        // strokes are all beyond the first box)
        continue;
      }
      const rawSegments = collectSegments(box, null);
      // the fallback is speculative — never toast on its failures. Over the
      // segment cap counts as a failure, not a "too complex" complaint.
      if (!rawSegments) {
        return { ok: false, reason: "no_owner" };
      }
      const selected = buildAndSelect(rawSegments);
      if (selected === "too_complex") {
        return { ok: false, reason: "no_owner" };
      }
      if (
        selected &&
        (isFinalAttempt ||
          selected.face.ring.every(
            (p) =>
              p[0] > box[0] + options.gapTolerance &&
              p[1] > box[1] + options.gapTolerance &&
              p[0] < box[2] - options.gapTolerance &&
              p[1] < box[3] - options.gapTolerance,
          ))
      ) {
        selection = selected;
      }
      if (!selection && isFinalAttempt) {
        // nothing more can enter range — no point burning further builds
        break;
      }
    }
    if (!selection) {
      // no enclosed region under the pointer — stay silent like `no_owner`;
      // clicking open canvas shouldn't nag
      return { ok: false, reason: "no_owner" };
    }
  }
  const { face, holes } = selection;

  // 5. simplify and validate. Note the returned ring may be a keyhole path
  // (holes spliced in via zero-width bridges); its signed area is then the
  // NET filled area, which is exactly what the size check should measure.
  const finalized = finalizePolygon(
    face.ring,
    holes.map((hole) => hole.ring),
    options,
  );
  if (!finalized) {
    return { ok: false, reason: "invalid_polygon" };
  }
  const { scenePoints, splicedHoleIndices } = finalized;
  if (polygonArea(scenePoints, 0) < options.minArea) {
    return { ok: false, reason: "too_small" };
  }

  // spliced islands genuinely bound the visible fill, so they join the
  // boundary metadata (and, via the app layer, group inheritance)
  const contributors = new Set<string>(face.contributors);
  for (const index of splicedHoleIndices) {
    for (const id of holes[index].contributors) {
      contributors.add(id);
    }
  }

  // 6. z-order. Two constraints, applied over ALL scene elements (not just
  // the region's participants):
  //
  // - the fill goes ABOVE the topmost opaque element whose paint overlaps
  //   the region ANYWHERE (same "covers" predicate boundary clipping uses).
  //   After a fill the region should read uniformly filled — the raster
  //   flood-fill outcome — so older opaque paint must not poke through it;
  //   the paint containing the click point is just the special case where
  //   the fill would otherwise be hidden at the very point clicked;
  // - otherwise it goes BELOW the lowest element that must stay visible:
  //   every participant (their outlines border the fill; deliberately
  //   including islands whose hole was dropped for the point budget — the
  //   fill paints straight through those, so staying below them is what
  //   keeps them visible at all), plus any visible NON-participant whose
  //   mark lies inside the region (a floating line, a label, an icon — an
  //   opaque fill would bury them). A visible stroke merely CROSSING the
  //   region would have subdivided the face and be a participant already,
  //   so sampling the element center + path points is enough to catch the
  //   wholly-inside marks that remain. The even-odd containment matches
  //   the render rule, so elements inside a keyhole hole are correctly NOT
  //   constrained (the fill doesn't paint there).
  //
  // When the two constraints conflict (an overlapping coverer sits above
  // some in-region mark in z), above-the-coverer wins: a mark buried under
  // opaque paint was largely hidden already, while paint poking through a
  // fresh fill always reads as the fill having failed.
  const participantIds = new Set<string>(
    owner ? [owner.id, ...contributors] : contributors,
  );
  for (const hole of holes) {
    for (const id of hole.contributors) {
      participantIds.add(id);
    }
  }

  const fillRegion = scenePoints as unknown as Polygon<GlobalPoint>;
  const [regionMinX, regionMinY, regionMaxX, regionMaxY] =
    getBoundsFromPoints(scenePoints);
  const markInsideRegion = (element: ExcalidrawElement): boolean => {
    const [minX, minY, maxX, maxY] = getElementBounds(element, elementsMap);
    if (
      maxX < regionMinX ||
      minX > regionMaxX ||
      maxY < regionMinY ||
      minY > regionMaxY
    ) {
      return false;
    }
    const samples: GlobalPoint[] = [
      pointFrom<GlobalPoint>((minX + maxX) / 2, (minY + maxY) / 2),
    ];
    if (isLinearElement(element) || isFreeDrawElement(element)) {
      const center = elementCenterPoint(element, elementsMap);
      const step = Math.max(1, Math.floor(element.points.length / 8));
      for (let i = 0; i < element.points.length; i += step) {
        samples.push(
          pointRotateRads(
            pointFrom<GlobalPoint>(
              element.x + element.points[i][0],
              element.y + element.points[i][1],
            ),
            center,
            element.angle,
          ),
        );
      }
    }
    return samples.some((sample) => polygonIncludesPoint(sample, fillRegion));
  };

  /**
   * Whether the element's paint overlaps the fill region anywhere. Sampled
   * in both directions (element outline inside the region, region ring
   * inside the element — covering partial overlap and containment either
   * way), plus the click point itself; exactness doesn't matter for a
   * z-order decision.
   */
  const paintOverlapsRegion = (element: ExcalidrawElement): boolean => {
    const [minX, minY, maxX, maxY] = getElementBounds(element, elementsMap);
    if (
      maxX < regionMinX ||
      minX > regionMaxX ||
      maxY < regionMinY ||
      minY > regionMaxY
    ) {
      return false;
    }
    if (isPointInElement(point, element, elementsMap)) {
      return true;
    }
    const outline = getElementLineSegments(element, elementsMap);
    const outlineStep = Math.max(1, Math.floor(outline.length / 16));
    for (let i = 0; i < outline.length; i += outlineStep) {
      if (polygonIncludesPoint(outline[i][0], fillRegion)) {
        return true;
      }
    }
    const ringStep = Math.max(1, Math.floor(scenePoints.length / 16));
    for (let i = 0; i < scenePoints.length; i += ringStep) {
      if (isPointInElement(scenePoints[i], element, elementsMap)) {
        return true;
      }
    }
    return false;
  };

  let lowestAbove: ExcalidrawElement | null = null;
  let covering: ExcalidrawElement | null = null;
  for (const element of elements) {
    // the coverer constraint is evaluated for EVERY element, not just the
    // `mustStayAbove` ones: an opaque element overlapping the region away
    // from the click (or straddling its edge, center outside) is neither a
    // participant nor a sampled in-region mark — missing it would insert
    // the fill beneath it, and its paint would poke through the fill
    if (rendersOpaqueFill(element) && paintOverlapsRegion(element)) {
      covering = element;
    }
    const mustStayAbove =
      participantIds.has(element.id) ||
      (rendersAnyMark(element) && markInsideRegion(element));
    if (mustStayAbove) {
      lowestAbove = lowestAbove ?? element;
    }
  }
  // a face always has contributors from `elements`, so a participant exists;
  // the last-element fallback is defensive only
  const insertion: BucketFillInsertion = covering
    ? { placement: "above", elementId: covering.id }
    : {
        placement: "below",
        elementId: (lowestAbove ?? elements[elements.length - 1]).id,
      };

  return {
    ok: true,
    ownerId: owner?.id ?? null,
    // elements (other than the owner) whose outlines actually bound the fill
    boundaryElementIds: [...contributors].filter((id) => id !== owner?.id),
    scenePoints,
    insertion,
  };
};

/**
 * Whether the element the click landed on is a fill the bucket tool should
 * restyle in place (instead of stacking an identical fill on top), given
 * the computed region.
 *
 * Fill-compatibility is decided by shape (`isBucketFillCompatible`): a fill
 * the user gave a stroke to has been repurposed into an outline and
 * participates as a boundary instead of being restyled.
 *
 * One guard on top: the computed region's net area and bounds must match
 * the element's. Without it, a click inside a shape drawn ON TOP of a
 * filled region would recolor the underlying fill instead of filling that
 * shape; a click on a since-subdivided part of an old fill likewise
 * creates a new (smaller) fill rather than restyling the old one.
 */
export const isRestylableFill = (args: {
  hitElement: ExcalidrawElement;
  scenePoints: readonly GlobalPoint[];
  elementsMap: ElementsMap;
}): boolean => {
  const { hitElement, scenePoints, elementsMap } = args;
  if (!isBucketFillCompatible(hitElement)) {
    return false;
  }

  const center = elementCenterPoint(hitElement, elementsMap);
  const ring = hitElement.points.map((p) =>
    pointRotateRads(
      pointFrom<GlobalPoint>(hitElement.x + p[0], hitElement.y + p[1]),
      center,
      hitElement.angle,
    ),
  );
  // same region? net areas (keyhole bridges cancel) and bounds must agree
  const fillArea = polygonArea(ring, 0);
  const regionArea = polygonArea(scenePoints, 0);
  const sameArea =
    Math.abs(fillArea - regionArea) <= 0.05 * Math.max(fillArea, regionArea);
  const [aMinX, aMinY, aMaxX, aMaxY] = getBoundsFromPoints(ring);
  const [bMinX, bMinY, bMaxX, bMaxY] = getBoundsFromPoints(scenePoints);
  const tolerance = BUCKET_FILL_REGION_MATCH_TOLERANCE;
  const sameBounds =
    Math.abs(aMinX - bMinX) <= tolerance &&
    Math.abs(aMinY - bMinY) <= tolerance &&
    Math.abs(aMaxX - bMaxX) <= tolerance &&
    Math.abs(aMaxY - bMaxY) <= tolerance;

  return sameArea && sameBounds;
};