import { arrayToMap, ROUNDNESS } from "@excalidraw/common";
import {
  distanceToLineSegment,
  lineSegment,
  pointFrom,
  polygonIncludesPoint,
} from "@excalidraw/math";

import { API } from "@excalidraw/excalidraw/tests/helpers/api";

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

import { computeBucketFillPolygon, isRestylableFill } from "../src/bucketFill";
import { getFreedrawStrokeCenterPoints } from "../src/shape";

import type { ElementsMap, NonDeletedExcalidrawElement } from "../src/types";

const setup = (elements: NonDeletedExcalidrawElement[]) => ({
  elements,
  elementsMap: arrayToMap(elements) as ElementsMap,
});

const polygonArea = (pts: GlobalPoint[]): number => {
  let area = 0;
  for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) {
    area += (pts[j][0] + pts[i][0]) * (pts[j][1] - pts[i][1]);
  }
  return Math.abs(area / 2);
};

/**
 * Turn a computed fill polygon into the line element the app would create
 * for it, so a follow-up `computeBucketFillPolygon` sees the prior fill.
 */
const materializeFill = (scenePoints: readonly GlobalPoint[]) => {
  const minX = Math.min(...scenePoints.map((p) => p[0]));
  const minY = Math.min(...scenePoints.map((p) => p[1]));
  const maxX = Math.max(...scenePoints.map((p) => p[0]));
  const maxY = Math.max(...scenePoints.map((p) => p[1]));
  return API.createElement({
    type: "line",
    x: minX,
    y: minY,
    width: maxX - minX,
    height: maxY - minY,
    points: scenePoints.map((p) =>
      pointFrom<LocalPoint>(p[0] - minX, p[1] - minY),
    ),
    polygon: true,
    backgroundColor: "#ffc9c9",
    fillStyle: "solid",
    strokeColor: "transparent",
  });
};

const isClosed = (pts: GlobalPoint[]): boolean =>
  pts.length > 3 &&
  pts[0][0] === pts[pts.length - 1][0] &&
  pts[0][1] === pts[pts.length - 1][1];

describe("computeBucketFillPolygon", () => {
  it("fills a simple rectangle and returns a closed polygon", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const { elements, elementsMap } = setup([rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(rect.id);
    expect(result.boundaryElementIds).toEqual([]);
    // transparent owner => the fill goes below it
    expect(result.insertion).toEqual({
      placement: "below",
      elementId: rect.id,
    });
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -1);
  });

  it("fills a rotated rectangle", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      angle: Math.PI / 5,
      roundness: null,
    });
    const { elements, elementsMap } = setup([rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -1);
  });

  it("fills an ellipse with a bounded point count", () => {
    const ellipse = API.createElement({
      type: "ellipse",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
    });
    const { elements, elementsMap } = setup([ellipse]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    // circle of r=50 ~ 7854; simplified polygon is slightly smaller
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(7000);
    expect(polygonArea(result.scenePoints)).toBeLessThan(7900);
    expect(result.scenePoints.length).toBeLessThanOrEqual(64);
    expect(result.scenePoints.length).toBeGreaterThan(6);
  });

  it("fills a curved line polygon along its smoothed path", () => {
    // curved (`roundness`) lines render a curve fitted through the points;
    // the fill boundary must sample that curve, not cut corners along the
    // raw polyline
    const points = [
      pointFrom<LocalPoint>(0, 50),
      pointFrom<LocalPoint>(35, 0),
      pointFrom<LocalPoint>(100, 20),
      pointFrom<LocalPoint>(90, 80),
      pointFrom<LocalPoint>(30, 100),
      pointFrom<LocalPoint>(0, 50),
    ];
    const blob = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points,
      polygon: true,
      roundness: { type: ROUNDNESS.PROPORTIONAL_RADIUS },
    });
    const { elements, elementsMap } = setup([blob]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // the smoothed curve bulges away from the polyline between sparse
    // points — some fill vertex must deviate from every polyline chord by
    // clearly more than the snap epsilon (a polyline-based boundary would
    // keep all vertices within ~1px of the chords)
    const chords = points
      .slice(0, -1)
      .map((p, i) => lineSegment(p as any, points[i + 1] as any));
    const maxDeviation = Math.max(
      ...result.scenePoints.map((vertex) =>
        Math.min(
          ...chords.map((chord) => distanceToLineSegment(vertex, chord as any)),
        ),
      ),
    );
    expect(maxDeviation).toBeGreaterThan(2);
  });

  it("fills a diamond", () => {
    // regression: a roundness:null diamond still has tiny (~2px chord) corner
    // arcs whose densely-subdivided segments used to be dropped by the
    // sub-epsilon length filter, disconnecting the outline at the corners
    const diamond = API.createElement({
      type: "diamond",
      x: 0,
      y: 0,
      width: 200,
      height: 150,
      roundness: null,
    });
    const { elements, elementsMap } = setup([diamond]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(100, 75),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    // diamond area = w*h/2 = 15000
    expect(polygonArea(result.scenePoints)).toBeCloseTo(15000, -3);
  });

  it("fills a freedraw loop with a hand-drawn closure gap", () => {
    // regression: isPathALoop accepts closure gaps up to LINE_CONFIRM_THRESHOLD
    // (8px), so the segment chain must be bridged explicitly or the region
    // reads as open even though it renders (and hit-tests) as closed.
    // Realistically dense points (~10px spacing, like actual drawing input) —
    // the boundary follows the streamline-smoothed centerline, which only
    // tracks the input at drawing-like densities
    const points: LocalPoint[] = [];
    const corners = [
      [0, 0],
      [100, 0],
      [100, 100],
      [0, 100],
      [0, 5],
    ];
    for (let c = 0; c < corners.length - 1; c++) {
      const [ax, ay] = corners[c];
      const [bx, by] = corners[c + 1];
      const steps = Math.ceil(Math.hypot(bx - ax, by - ay) / 10);
      for (let s = 0; s < steps; s++) {
        points.push(
          pointFrom<LocalPoint>(
            ax + ((bx - ax) * s) / steps,
            ay + ((by - ay) * s) / steps,
          ),
        );
      }
    }
    points.push(pointFrom<LocalPoint>(0, 5));
    const freedraw = API.createElement({
      type: "freedraw",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points,
    });
    const { elements, elementsMap } = setup([freedraw]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -3);
  });

  it("fills an exactly-closed freedraw loop", () => {
    // the sibling of the gapped-closure test: last point === first point,
    // so no synthetic closing segment is needed at all
    const points: LocalPoint[] = [];
    const corners = [
      [0, 0],
      [100, 0],
      [100, 100],
      [0, 100],
      [0, 0],
    ];
    for (let c = 0; c < corners.length - 1; c++) {
      const [ax, ay] = corners[c];
      const [bx, by] = corners[c + 1];
      const steps = Math.ceil(Math.hypot(bx - ax, by - ay) / 10);
      for (let s = 0; s < steps; s++) {
        points.push(
          pointFrom<LocalPoint>(
            ax + ((bx - ax) * s) / steps,
            ay + ((by - ay) * s) / steps,
          ),
        );
      }
    }
    points.push(pointFrom<LocalPoint>(0, 0));
    const freedraw = API.createElement({
      type: "freedraw",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points,
    });
    const { elements, elementsMap } = setup([freedraw]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -3);
  });

  it("fills a line polygon", () => {
    const triangle = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(50, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
      ],
      polygon: true,
    });
    const { elements, elementsMap } = setup([triangle]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 70),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(5000, -3);
  });

  it("fills the overlap region split by a rectangle below the owner", () => {
    const below = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      roundness: null,
    });
    // `owner` is drawn last => topmost => chosen as owner; `below` is lower
    // z-order but must still participate in the boundary graph.
    const { elements, elementsMap } = setup([below, owner]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(75, 75),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(owner.id);
    expect(result.boundaryElementIds).toContain(below.id);
    // both participants are transparent => below the lowest one
    expect(result.insertion).toEqual({
      placement: "below",
      elementId: below.id,
    });
    // overlap region is the 50x50 square (50,50)-(100,100) => area 2500,
    // much smaller than either full 100x100 rectangle
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(2300);
    expect(polygonArea(result.scenePoints)).toBeLessThan(2700);
  });

  it("fills the owner-minus-overlap region when clicking outside the overlap", () => {
    const below = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      roundness: null,
    });
    const { elements, elementsMap } = setup([below, owner]);

    // (130,130) is inside `owner` but outside `below`
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(130, 130),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // owner (10000) minus overlap (2500) => 7500
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(7200);
    expect(polygonArea(result.scenePoints)).toBeLessThan(7800);
  });

  it("ignores outline portions hidden behind an opaque element on top", () => {
    // `hidden` sits below `owner`; the part of its outline inside `owner` is
    // covered by owner's opaque fill, so it must not act as a boundary
    const hidden = API.createElement({
      type: "rectangle",
      x: 40,
      y: 40,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "#ffd43b",
    });
    // owner drawn last => on top, with an opaque fill
    const { elements, elementsMap } = setup([hidden, owner]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(20, 20),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(owner.id);
    // the whole visible owner fills (~10000); the hidden outline does NOT carve
    // out the ~6400 L-shape it would if it were visible
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(9000);
  });

  it("respects outlines visible through a transparent element on top", () => {
    // same geometry, but `owner` is transparent, so the lower rectangle's
    // outline shows through and splits the region
    const lower = API.createElement({
      type: "rectangle",
      x: 40,
      y: 40,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([lower, owner]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(20, 20),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // the visible outline carves out the overlap corner => ~6400 L-shape
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(6000);
    expect(polygonArea(result.scenePoints)).toBeLessThan(7000);
  });

  it("ignores a text element's never-rendered backgroundColor", () => {
    // text elements inherit currentItemBackgroundColor on creation but never
    // paint it — such a text box overlapping the owner outline must neither
    // cover (clip) the outline nor act as a boundary
    const owner = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const text = API.createElement({
      type: "text",
      x: 80,
      y: 40,
      width: 60,
      height: 25,
      backgroundColor: "#ffec99",
    });
    const { elements, elementsMap } = setup([owner, text]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -1);
  });

  it("does not treat a hachure-filled element as covering", () => {
    // hachure fill is see-through: the lower outline stays visible through it
    // and must still act as a boundary
    const lower = API.createElement({
      type: "rectangle",
      x: 40,
      y: 40,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "#ffd43b",
      fillStyle: "hachure",
    });
    const { elements, elementsMap } = setup([lower, owner]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(20, 20),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // the outline visible through the hachure carves out the overlap corner
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(6000);
    expect(polygonArea(result.scenePoints)).toBeLessThan(7000);
  });

  it("does not treat a semi-transparent element as covering", () => {
    const lower = API.createElement({
      type: "rectangle",
      x: 40,
      y: 40,
      width: 100,
      height: 100,
      roundness: null,
    });
    const owner = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "#ffd43b",
      opacity: 50,
    });
    const { elements, elementsMap } = setup([lower, owner]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(20, 20),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // the outline blended through the 50% fill still bounds the region
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(6000);
    expect(polygonArea(result.scenePoints)).toBeLessThan(7000);
  });

  it.each([
    ["#RRGGBBAA hex", "#ffd43b80"],
    ["rgba()", "rgba(255, 212, 59, 0.5)"],
  ])(
    "does not treat a partial-alpha (%s) background as covering",
    (_label, backgroundColor) => {
      // same scene as the semi-transparent test, but the translucency comes
      // from the COLOR's alpha channel at full element opacity — the outline
      // blended through it is just as visible and must still bound the region
      const lower = API.createElement({
        type: "rectangle",
        x: 40,
        y: 40,
        width: 100,
        height: 100,
        roundness: null,
      });
      const owner = API.createElement({
        type: "rectangle",
        x: 0,
        y: 0,
        width: 100,
        height: 100,
        roundness: null,
        backgroundColor,
      });
      const { elements, elementsMap } = setup([lower, owner]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(20, 20),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(polygonArea(result.scenePoints)).toBeGreaterThan(6000);
      expect(polygonArea(result.scenePoints)).toBeLessThan(7000);
    },
  );

  it("fills the whole top element when clicking an opaque overlap", () => {
    // clicking the overlap of two OPAQUE shapes fills the whole top shape, not
    // the small overlap: the lower outline is hidden behind the top shape's
    // opaque fill, so it does not subdivide the visible region
    const lower = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "#ffd43b",
    });
    const top = API.createElement({
      type: "rectangle",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "#ffd43b",
    });
    const { elements, elementsMap } = setup([lower, top]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(75, 75), // inside the 50x50 overlap
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(top.id);
    // the whole top rectangle (~10000), NOT the 50x50 overlap (~2500)
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(9000);
    // the opaque owner would hide a fill beneath it => above it
    expect(result.insertion).toEqual({
      placement: "above",
      elementId: top.id,
    });
  });

  it("fills a rounded owner partially covered by a thin opaque overlap", () => {
    // regression: a thin opaque coverer crossing the owner's ROUNDED corners
    // left sub-pixel gaps in the clipped outline, opening the region. The
    // gapTolerance-based node merging in the arrangement bridges them.
    const rounded = { type: ROUNDNESS.ADAPTIVE_RADIUS } as const;
    const owner = API.createElement({
      type: "rectangle",
      x: 180,
      y: 650,
      width: 240,
      height: 195,
      roundness: rounded,
      backgroundColor: "#ffd43b",
    });
    const sideways = API.createElement({
      type: "rectangle",
      x: 5,
      y: 690,
      width: 230,
      height: 160,
      roundness: rounded,
      backgroundColor: "#ffd43b",
    });
    // thin opaque cover: its bottom edge overlaps the owner's top by ~5px,
    // crossing the owner's rounded top corners
    const cover = API.createElement({
      type: "rectangle",
      x: 110,
      y: 510,
      width: 245,
      height: 145,
      roundness: rounded,
      backgroundColor: "#a5d8ff",
    });
    const { elements, elementsMap } = setup([sideways, owner, cover]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(300, 740),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(owner.id);
  });

  it("fills a region enclosed only by open lines (owner-less)", () => {
    // 4 open lines forming a diamond; no closed element anywhere
    const mkLine = (pts: [number, number][]) =>
      API.createElement({
        type: "line",
        x: 0,
        y: 0,
        width: 100,
        height: 100,
        points: pts.map(([x, y]) => pointFrom<LocalPoint>(x, y)),
      });
    const l1 = mkLine([
      [50, 0],
      [100, 50],
    ]);
    const l2 = mkLine([
      [100, 50],
      [50, 100],
    ]);
    const l3 = mkLine([
      [50, 100],
      [0, 50],
    ]);
    const l4 = mkLine([
      [0, 50],
      [50, 0],
    ]);
    const { elements, elementsMap } = setup([l1, l2, l3, l4]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBeNull();
    expect(result.boundaryElementIds.sort()).toEqual(
      [l1.id, l2.id, l3.id, l4.id].sort(),
    );
    expect(isClosed(result.scenePoints)).toBe(true);
    // diamond with diagonals 100 => area 5000
    expect(polygonArea(result.scenePoints)).toBeCloseTo(5000, -3);
  });

  it("fills a loop formed by a single self-crossing open polyline", () => {
    // open polyline that crosses itself, enclosing a triangle
    const line = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(100, 0),
      ],
    });
    const { elements, elementsMap } = setup([line]);

    // click inside the enclosed lower triangle (50,50)-(0,100)-(100,100)...
    // actually the loop is the triangle between the two crossing diagonals
    // and the bottom edge; its centroid is around (50, 83)
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 80),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBeNull();
    expect(result.boundaryElementIds).toEqual([line.id]);
    // triangle (50,50)-(0,100)-(100,100) => area 2500
    expect(polygonArea(result.scenePoints)).toBeCloseTo(2500, -3);
  });

  it("fills a region closed by an open line against a shape's outside wall", () => {
    // an open V-line whose two ends touch the rectangle's right edge,
    // enclosing a region OUTSIDE the rectangle
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const line = API.createElement({
      type: "line",
      x: 100,
      y: 20,
      width: 60,
      height: 60,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(60, 30),
        pointFrom<LocalPoint>(0, 60),
      ],
    });
    const { elements, elementsMap } = setup([rect, line]);

    // inside the triangle right of the rectangle's wall
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(115, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBeNull();
    expect(result.boundaryElementIds.sort()).toEqual([line.id, rect.id].sort());
    // triangle (100,20)-(160,50)-(100,80) => area 1800
    expect(polygonArea(result.scenePoints)).toBeCloseTo(1800, -3);
  });

  it("fills only the clicked lobe of a self-intersecting (figure-eight) polygon", () => {
    const line = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(100, 0),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(0, 0),
      ],
      polygon: true,
    });
    const { elements, elementsMap } = setup([line]);

    // left lobe: triangle (0,0)-(50,50)-(0,100), centroid ~(17, 50)
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(17, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // one lobe (area 2500), not the whole figure-eight
    expect(polygonArea(result.scenePoints)).toBeCloseTo(2500, -3);
  });

  it("handles a line retracing part of the owner's edge (collinear overlap)", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    // line running exactly along the rect's top edge, extending past it
    const retrace = API.createElement({
      type: "line",
      x: -50,
      y: 0,
      width: 200,
      height: 0,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(200, 0)],
    });
    const { elements, elementsMap } = setup([rect, retrace]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.ownerId).toBe(rect.id);
    expect(isClosed(result.scenePoints)).toBe(true);
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -3);
  });

  it("bridges endpoint gaps up to gapTolerance without distorting the shape", () => {
    // triangle of open lines whose corners have ~5px gaps: bridged by the
    // default tolerance (8), unfillable with a stricter one
    const mkLine = (pts: [number, number][]) =>
      API.createElement({
        type: "line",
        x: 0,
        y: 0,
        width: 100,
        height: 100,
        points: pts.map(([x, y]) => pointFrom<LocalPoint>(x, y)),
      });
    const l1 = mkLine([
      [4, 0],
      [96, 0],
    ]);
    const l2 = mkLine([
      [100, 4],
      [52, 96],
    ]);
    const l3 = mkLine([
      [48, 96],
      [0, 4],
    ]);
    const { elements, elementsMap } = setup([l1, l2, l3]);
    const point = pointFrom<GlobalPoint>(50, 30);

    const result = computeBucketFillPolygon({ point, elements, elementsMap });
    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // fidelity: gaps are closed by ADDING connector edges, never by moving
    // vertices — every polygon vertex must lie (near-)on one of the strokes,
    // not be dragged toward a merged corner position
    const strokes = [
      lineSegment(pointFrom<GlobalPoint>(4, 0), pointFrom<GlobalPoint>(96, 0)),
      lineSegment(
        pointFrom<GlobalPoint>(100, 4),
        pointFrom<GlobalPoint>(52, 96),
      ),
      lineSegment(pointFrom<GlobalPoint>(48, 96), pointFrom<GlobalPoint>(0, 4)),
    ];
    for (const vertex of result.scenePoints) {
      const distance = Math.min(
        ...strokes.map((stroke) => distanceToLineSegment(vertex, stroke)),
      );
      expect(distance).toBeLessThanOrEqual(2);
    }

    const strict = computeBucketFillPolygon({
      point,
      elements,
      elementsMap,
      options: { gapTolerance: 2 },
    });
    expect(strict.ok).toBe(false);
  });

  it("bridges a stroke ending short of a long edge at the projection point", () => {
    // chord stopping 6px short of both rectangle walls: the nearest NODES on
    // those walls are the far-away corners, so bridging must split the wall
    // edge at the chord end's projection instead of snapping to a corner
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const chord = API.createElement({
      type: "line",
      x: 6,
      y: 50,
      width: 88,
      height: 0,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(88, 0)],
    });
    const { elements, elementsMap } = setup([rect, chord]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 25),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // upper half of the rectangle, not the whole thing
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(4500);
    expect(polygonArea(result.scenePoints)).toBeLessThan(5500);
  });

  it("bounds bridge-grid indexing for scene-spanning edges", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    // The chord needs the bridge grid to reach both rectangle walls.
    const chord = API.createElement({
      type: "line",
      x: 6,
      y: 50,
      width: 88,
      height: 0,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(88, 0)],
    });
    // This open line's bounds touch the owner's local search area, so its full
    // million-pixel span joins the arrangement even though it does not bound
    // the clicked face.
    const sceneSpanning = API.createElement({
      type: "line",
      x: -500_000,
      y: 105,
      width: 1_000_000,
      height: 0,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(1_000_000, 0),
      ],
    });
    const { elements, elementsMap } = setup([rect, chord, sceneSpanning]);

    const originalSet = Map.prototype.set;
    let spatialBucketSets = 0;
    const setSpy = vi
      .spyOn(Map.prototype, "set")
      .mockImplementation(function (this: Map<unknown, unknown>, key, value) {
        if (typeof key === "string" && /^-?\d+:-?\d+$/.test(key)) {
          spatialBucketSets++;
          if (spatialBucketSets > 512) {
            throw new Error("spatial grid exceeded its bucket budget");
          }
        }
        return originalSet.call(this, key, value);
      });

    const result = (() => {
      try {
        return computeBucketFillPolygon({
          point: pointFrom<GlobalPoint>(50, 25),
          elements,
          elementsMap,
        });
      } finally {
        setSpy.mockRestore();
      }
    })();

    expect(result.ok).toBe(true);
    expect(spatialBucketSets).toBeLessThanOrEqual(512);
    if (result.ok) {
      expect(polygonArea(result.scenePoints)).toBeGreaterThan(4500);
      expect(polygonArea(result.scenePoints)).toBeLessThan(5500);
    }
  });

  const lineSquare = (half: number) => {
    const mkLine = (x: number, y: number, dx: number, dy: number) =>
      API.createElement({
        type: "line",
        x,
        y,
        points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(dx, dy)],
      });
    return [
      mkLine(-half, -half, 2 * half, 0),
      mkLine(half, -half, 0, 2 * half),
      mkLine(half, half, -2 * half, 0),
      mkLine(-half, half, 0, -2 * half),
    ] as NonDeletedExcalidrawElement[];
  };

  it("the owner-less fallback keeps expanding past an empty first radius", () => {
    // regression: an empty candidate set at the first radius used to return
    // no_owner immediately — a 2,000px square of open lines around the
    // click has all its strokes beyond the initial 512px box
    const { elements, elementsMap } = setup(lineSquare(1000));

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(0, 0),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(polygonArea(result.scenePoints)).toBeCloseTo(4_000_000, -5);
  });

  it("the owner-less fallback accepts a complete face touching the frontier", () => {
    // regression: all four lines fit the first 512px box, but the ring's
    // vertices at ±508 graze the frontier — with every eligible element
    // already in range the face is complete and must be accepted, not
    // rejected as possibly-unfinished
    const { elements, elementsMap } = setup(lineSquare(508));

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(0, 0),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(polygonArea(result.scenePoints)).toBeCloseTo(1016 * 1016, -4);
  });

  it("a fully invisible closed element cannot own a fill", () => {
    // regression: a rect with transparent stroke AND transparent background
    // renders no pixels — clicking the seemingly empty canvas used to
    // conjure a fill out of it
    const ghost = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      strokeColor: "transparent",
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([ghost]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result).toEqual({ ok: false, reason: "no_owner" });
  });

  it("returns no_owner for open canvas", () => {
    const { elements, elementsMap } = setup([]);
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(10, 10),
      elements,
      elementsMap,
    });
    expect(result).toEqual({ ok: false, reason: "no_owner" });
  });

  it("returns no_owner when clicking outside every closed shape", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 50,
      height: 50,
      roundness: null,
    });
    const { elements, elementsMap } = setup([rect]);
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(500, 500),
      elements,
      elementsMap,
    });
    expect(result.ok).toBe(false);
  });

  it("returns too_complex when the segment cap is exceeded", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    const { elements, elementsMap } = setup([rect]);
    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
      options: { maxBoundarySegments: 2 },
    });
    expect(result).toEqual({ ok: false, reason: "too_complex" });
  });

  it("does not re-enumerate dense segment pairs in every spatial cell", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    // Every divider occupies roughly 100 grid cells. Enumerating all pairs
    // independently in every shared cell turns these 1,000 segments into
    // ~50 million pair visits despite there being only ~500,000 pairs.
    const dividers = Array.from({ length: 1000 }, () =>
      API.createElement({
        type: "line",
        x: -10,
        y: 50,
        width: 120,
        height: 0,
        points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(120, 0)],
      }),
    );
    const { elements, elementsMap } = setup([rect, ...dividers]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 25),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(polygonArea(result.scenePoints)).toBeCloseTo(5000, -1);
  }, 2000);

  it("fill-compatible paint never becomes the owner", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
    });
    // a strokeless bg polygon (what a generated fill is — no marker, fills
    // are recognized by shape) sitting ON TOP of the rect. Hachure, so it
    // exercises the ownership exclusion in isolation without also acting
    // as an opaque coverer that would clip the rect's coincident outline
    const priorFill = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(0, 0),
      ],
      polygon: true,
      backgroundColor: "#b2f2bb",
      fillStyle: "hachure",
      strokeColor: "transparent",
    });
    const { elements, elementsMap } = setup([rect, priorFill]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // owner is the rectangle, not the paint on top of it
    expect(result.ownerId).toBe(rect.id);
  });

  it("inserts below a visible non-contributor inside the region", () => {
    // a floating line inside the rect doesn't subdivide the region (its
    // dangling chain forms no face), so it isn't a contributor — but it's
    // visible, and an opaque fill above it would bury it
    const floating = API.createElement({
      type: "line",
      x: 30,
      y: 50,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(40, 0)],
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    // scene order: line lowest — the fill must slot in below it
    const { elements, elementsMap } = setup([floating, rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(10, 10),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.insertion).toEqual({
      placement: "below",
      elementId: floating.id,
    });
  });

  it("inserts below a text label inside the region", () => {
    const label = API.createElement({
      type: "text",
      x: 30,
      y: 40,
      text: "hi",
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([label, rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(10, 10),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.insertion).toEqual({
      placement: "below",
      elementId: label.id,
    });
  });

  it("inserts above a covering non-participant (sub-region refill)", () => {
    // whole-rect fill exists; a line then subdivides the region and the top
    // half is filled anew — the new fill must go ABOVE the old opaque fill
    // (not below the participants, where the old fill would hide it)
    const oldFill = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(0, 0),
      ],
      polygon: true,
      backgroundColor: "#b2f2bb",
      fillStyle: "solid",
      strokeColor: "transparent",
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    const splitter = API.createElement({
      type: "line",
      x: -5,
      y: 50,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(110, 0)],
    });
    const { elements, elementsMap } = setup([oldFill, rect, splitter]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 25),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.insertion).toEqual({
      placement: "above",
      elementId: oldFill.id,
    });
  });

  it("inserts above a coverer straddling the region edge (center outside)", () => {
    // regression: the coverer constraint must be evaluated for EVERY
    // element — an opaque strokeless rect straddling the region edge
    // contains the click while being neither a participant nor (with its
    // center outside the region) a sampled in-region mark; gating the
    // coverer check on those buried the fill beneath it
    const line = API.createElement({
      type: "line",
      x: -20,
      y: 100,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(240, 0)],
      strokeColor: "#1e1e1e",
    });
    const coverer = API.createElement({
      type: "rectangle",
      x: 160,
      y: 20,
      width: 100,
      height: 60,
      roundness: null,
      backgroundColor: "#ffc9c9",
      fillStyle: "solid",
      strokeColor: "transparent",
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 200,
      height: 200,
      roundness: null,
      backgroundColor: "transparent",
    });
    // z-order: line (lowest), coverer, rect — the rect on top keeps the
    // coverer from clipping any face boundary
    const { elements, elementsMap } = setup([line, coverer, rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(170, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.insertion).toEqual({
      placement: "above",
      elementId: coverer.id,
    });
  });

  it("inserts above an opaque coverer overlapping the region away from the click", () => {
    // same trio as above, but the click lands OUTSIDE the coverer: after a
    // fill the region must read uniformly filled (the raster flood-fill
    // outcome), so opaque paint overlapping the region anywhere — not just
    // under the click — must not poke through the new fill
    const line = API.createElement({
      type: "line",
      x: -20,
      y: 100,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(240, 0)],
      strokeColor: "#1e1e1e",
    });
    const coverer = API.createElement({
      type: "rectangle",
      x: 150,
      y: 20,
      width: 110,
      height: 60,
      roundness: null,
      backgroundColor: "#a5d8ff",
      fillStyle: "solid",
      strokeColor: "transparent",
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 200,
      height: 200,
      roundness: null,
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([line, coverer, rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(60, 50),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(result.insertion).toEqual({
      placement: "above",
      elementId: coverer.id,
    });
  });

  it("an opaque prior fill hides strokes beneath it from new fills", () => {
    // the line crossing the rect would normally split it in two — but it
    // lies UNDER an opaque fill, so the user can't see it and it must not
    // stop the new fill either
    const buried = API.createElement({
      type: "line",
      x: -5,
      y: 50,
      points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(110, 0)],
    });
    const priorFill = API.createElement({
      type: "line",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(0, 0),
      ],
      polygon: true,
      backgroundColor: "#b2f2bb",
      fillStyle: "solid",
      strokeColor: "transparent",
    });
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    // realistic fill stacking: buried line lowest, fill above it, owner on top
    const { elements, elementsMap } = setup([buried, priorFill, rect]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(50, 25),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    // the whole rect, not the top half the buried line would carve out
    expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -2);
    expect(result.boundaryElementIds).not.toContain(buried.id);
  });

  // a fill's polygon runs along the CENTERLINE of the strokes that bound it,
  // so once the fill counts as a coverer, a clip test without a boundary
  // margin eats those strokes on the next click and adjacent regions merge
  // (or the region falls open). Rounded corners are what trigger it: the
  // sampled arc midpoints land inside the fill ring within simplification
  // jitter. See final-review-04.md §11.
  it("a fill does not clip the strokes that bound it (fill-then-fill, transparent container on top)", () => {
    const upper = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: { type: ROUNDNESS.ADAPTIVE_RADIUS },
      backgroundColor: "#ffd43b",
      fillStyle: "solid",
    });
    const lower = API.createElement({
      type: "rectangle",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      roundness: { type: ROUNDNESS.ADAPTIVE_RADIUS },
      backgroundColor: "transparent",
    });

    // step 1: click the overlap — the lens between the two containers
    const first = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(75, 75),
      ...setup([upper, lower]),
    });
    expect(first.ok).toBe(true);
    if (!first.ok) {
      return;
    }
    expect(polygonArea(first.scenePoints)).toBeGreaterThan(2000);
    expect(polygonArea(first.scenePoints)).toBeLessThan(2600);
    expect(first.insertion).toEqual({
      placement: "above",
      elementId: upper.id,
    });

    // step 2: materialize the lens fill at its computed insertion and click
    // the lower container's remaining region
    const second = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(120, 120),
      ...setup([upper, materializeFill(first.scenePoints), lower]),
    });
    expect(second.ok).toBe(true);
    if (!second.ok) {
      return;
    }
    // the lower container MINUS the lens (~7270), not the whole container
    // (~9530 — the regression: the fill flooded through the lens)
    expect(polygonArea(second.scenePoints)).toBeGreaterThan(6900);
    expect(polygonArea(second.scenePoints)).toBeLessThan(7700);
  });

  it("a fill does not clip the strokes that bound it (fill-then-fill, opaque container on top)", () => {
    const lower = API.createElement({
      type: "rectangle",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      roundness: { type: ROUNDNESS.ADAPTIVE_RADIUS },
      backgroundColor: "transparent",
    });
    const upper = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: { type: ROUNDNESS.ADAPTIVE_RADIUS },
      backgroundColor: "#ffd43b",
      fillStyle: "solid",
    });

    // step 1: click the overlap — the opaque container is on top, so the
    // region is its whole footprint
    const first = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(75, 75),
      ...setup([lower, upper]),
    });
    expect(first.ok).toBe(true);
    if (!first.ok) {
      return;
    }
    expect(polygonArea(first.scenePoints)).toBeGreaterThan(9000);
    expect(polygonArea(first.scenePoints)).toBeLessThan(10000);
    expect(first.insertion).toEqual({
      placement: "above",
      elementId: upper.id,
    });

    // step 2: click the lower container's remaining region — before the
    // boundary-margin fix this failed outright (`open_region`)
    const second = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(120, 120),
      ...setup([lower, upper, materializeFill(first.scenePoints)]),
    });
    expect(second.ok).toBe(true);
    if (!second.ok) {
      return;
    }
    expect(polygonArea(second.scenePoints)).toBeGreaterThan(6900);
    expect(polygonArea(second.scenePoints)).toBeLessThan(7700);
  });

  it("isRestylableFill accepts strokeless bg polygons covering the region", () => {
    const rect = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 100,
      height: 100,
      roundness: null,
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([rect]);
    const click = pointFrom<GlobalPoint>(50, 50);
    const result = computeBucketFillPolygon({
      point: click,
      elements,
      elementsMap,
    });
    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    const scenePoints = result.scenePoints;

    // NOTE deliberately no `customData.bucketFill` — restylability is
    // shape-based (the marker goes stale once the user restyles a fill)
    const mkFill = (size: number, overrides: object = {}) =>
      API.createElement({
        type: "line",
        x: 0,
        y: 0,
        points: [
          pointFrom<LocalPoint>(0, 0),
          pointFrom<LocalPoint>(size, 0),
          pointFrom<LocalPoint>(size, size),
          pointFrom<LocalPoint>(0, size),
          pointFrom<LocalPoint>(0, 0),
        ],
        polygon: true,
        backgroundColor: "#b2f2bb",
        fillStyle: "solid",
        strokeColor: "transparent",
        ...overrides,
      });

    // fill-like polygon covering the clicked region -> restylable
    const fill = mkFill(100);
    expect(
      isRestylableFill({
        hitElement: fill,
        scenePoints,
        elementsMap: setup([fill, rect]).elementsMap,
      }),
    ).toBe(true);

    // a fill the user gave a visible stroke has been repurposed into an
    // outline (it participates as a boundary instead) -> not restylable
    const stroked = mkFill(100, { strokeColor: "#1e1e1e" });
    expect(
      isRestylableFill({
        hitElement: stroked,
        scenePoints,
        elementsMap: setup([stroked, rect]).elementsMap,
      }),
    ).toBe(false);

    // covers a smaller region than the computed one -> not restylable
    const subRegion = mkFill(20);
    expect(
      isRestylableFill({
        hitElement: subRegion,
        scenePoints,
        elementsMap: setup([subRegion, rect]).elementsMap,
      }),
    ).toBe(false);

    // a plain shape is never restylable
    expect(
      isRestylableFill({
        hitElement: rect,
        scenePoints,
        elementsMap,
      }),
    ).toBe(false);
  });

  it("a fill given a visible stroke afterwards acts as a boundary", () => {
    const strokedFill = API.createElement({
      type: "line",
      x: 50,
      y: 50,
      width: 100,
      height: 100,
      points: [
        pointFrom<LocalPoint>(0, 0),
        pointFrom<LocalPoint>(100, 0),
        pointFrom<LocalPoint>(100, 100),
        pointFrom<LocalPoint>(0, 100),
        pointFrom<LocalPoint>(0, 0),
      ],
      polygon: true,
      backgroundColor: "#b2f2bb",
      fillStyle: "solid",
      strokeColor: "#1e1e1e",
    });
    const outer = API.createElement({
      type: "rectangle",
      x: 0,
      y: 0,
      width: 200,
      height: 200,
      roundness: null,
      backgroundColor: "transparent",
    });
    const { elements, elementsMap } = setup([strokedFill, outer]);

    const annulus = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(25, 100),
      elements,
      elementsMap,
    });

    expect(annulus.ok).toBe(true);
    if (!annulus.ok) {
      return;
    }
    // the stroked fill is a visible outline now: it islands the region
    expect(polygonArea(annulus.scenePoints)).toBeCloseTo(30000, -2);
    expect(annulus.boundaryElementIds).toContain(strokedFill.id);

    // ...but a fill still never becomes an OWNER: clicking inside it falls
    // through to the rect while the fill's outline bounds the region
    const inside = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(100, 100),
      elements,
      elementsMap,
    });
    expect(inside.ok).toBe(true);
    if (!inside.ok) {
      return;
    }
    expect(inside.ownerId).toBe(outer.id);
    expect(polygonArea(inside.scenePoints)).toBeCloseTo(10000, -2);
  });

  it("fills a sparse freedraw along its rendered (smoothed) centerline", () => {
    // raw freedraw points can sit 20px+ apart; the renderer draws a
    // streamline-smoothed path between them, so the fill boundary must
    // sample that same path, not the raw chords (which visibly poke out)
    // prettier-ignore
    const CIRCLE_POINTS: [number, number][] = [[240,120],[238.18,140.84],[232.76,161.04],[223.92,180],[211.93,197.13],[197.13,211.93],[180,223.92],[161.04,232.76],[140.84,238.18],[120,240],[99.16,238.18],[78.96,232.76],[60,223.92],[42.87,211.93],[28.07,197.13],[16.08,180],[7.24,161.04],[1.82,140.84],[0,120],[1.82,99.16],[7.24,78.96],[16.08,60],[28.07,42.87],[42.87,28.07],[60,16.08],[78.96,7.24],[99.16,1.82],[120,0],[140.84,1.82],[161.04,7.24],[180,16.08],[197.13,28.07],[211.93,42.87],[223.92,60],[232.76,78.96],[238.18,99.16],[239.93,115.81]];
    const circle = API.createElement({
      type: "freedraw",
      x: 0,
      y: 0,
      width: 240,
      height: 240,
      points: CIRCLE_POINTS.map((p) => pointFrom<LocalPoint>(p[0], p[1])),
    });
    const { elements, elementsMap } = setup([
      circle as NonDeletedExcalidrawElement,
    ]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(120, 120),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    const distToPolyline = (p: GlobalPoint, poly: [number, number][]) => {
      let best = Infinity;
      for (let i = 0; i < poly.length - 1; i++) {
        const [ax, ay] = poly[i];
        const [bx, by] = poly[i + 1];
        const dx = bx - ax;
        const dy = by - ay;
        const l2 = dx * dx + dy * dy;
        const t = l2
          ? Math.max(0, Math.min(1, ((p[0] - ax) * dx + (p[1] - ay) * dy) / l2))
          : 0;
        best = Math.min(
          best,
          Math.hypot(p[0] - (ax + t * dx), p[1] - (ay + t * dy)),
        );
      }
      return best;
    };
    const rawPolyline = [...CIRCLE_POINTS, CIRCLE_POINTS[0]];
    const smoothedPolyline = [
      ...getFreedrawStrokeCenterPoints(circle),
      CIRCLE_POINTS[0],
    ] as [number, number][];
    // every fill vertex lies ON the smoothed centerline (RDP only removes
    // vertices, it never moves them)...
    const deviationFromSmoothed = Math.max(
      ...result.scenePoints.map((v) => distToPolyline(v, smoothedPolyline)),
    );
    expect(deviationFromSmoothed).toBeLessThan(0.5);
    // ...and measurably OFF the raw polyline, proving the boundary follows
    // the rendered path rather than the raw chords
    const deviationFromRaw = Math.max(
      ...result.scenePoints.map((v) => distToPolyline(v, rawPolyline)),
    );
    expect(deviationFromRaw).toBeGreaterThan(1.5);
  });

  it("fills a freedraw whose closure only exists in the smoothed stroke", () => {
    // real-world repro: the raw ends sit ~21px apart and ~14px from the
    // rest of the raw path — but the RENDERED (smoothed) stroke passes
    // within ~3px of its own tail, which reads as visually closed and must
    // be bridgeable
    // prettier-ignore
    const BLOB_POINTS: [number, number][] = [[0,0],[0,-0.3],[0,-0.6],[-0.6,-0.6],[-2.1,-0.6],[-4.7,-0.6],[-7.9,-0.6],[-11.2,0.3],[-18.2,3.8],[-26.2,7.9],[-33.8,13.2],[-42.3,20.0],[-50.9,27.6],[-56.7,34.7],[-62.0,43.5],[-63.2,50.3],[-63.8,54.7],[-60.0,60.3],[-51.7,65.3],[-38.2,69.1],[-21.5,72.3],[-3.5,73.8],[16.5,75.0],[36.7,75.0],[66.7,75.0],[74.4,75.8],[76.1,75.8],[76.1,76.1],[75.6,76.7],[71.1,77.9],[59.7,80.5],[46.2,85.0],[33.5,89.1],[21.2,95.0],[12.6,101.1],[6.8,106.7],[4.4,112.6],[4.4,116.4],[5.6,119.9],[10.3,124.1],[18.8,127.3],[32.0,129.6],[47.3,131.7],[62.6,131.7],[80.5,131.7],[97.3,129.1],[114.4,126.4],[139.0,123.5],[147.0,122.0],[150.2,122.0],[152.9,121.7],[154.6,120.2],[155.8,118.5],[157.9,114.1],[162.0,104.9],[167.0,93.2],[172.3,81.4],[177.3,69.7],[181.4,60.6],[184.6,52.0],[186.4,46.2],[187.3,42.3],[187.8,39.7],[187.8,37.6],[187.8,36.2],[185.5,34.4],[181.1,32.0],[172.9,29.4],[158.7,25.0],[144.3,21.8],[128.2,19.1],[100.0,14.4],[90.8,13.2],[86.7,12.1],[85.8,11.5],[85.5,11.5],[85.5,11.2],[86.1,10.9],[87.6,9.7],[88.8,7.9],[89.4,6.5],[89.4,5.6],[89.4,4.4],[86.7,2.9],[81.4,1.5],[74.1,0.3],[62.6,-0.6],[50.9,-1.2],[42.0,-1.2],[31.7,-1.2],[23.2,-0.6],[17.1,0.6],[12.1,1.5],[9.7,2.1],[8.5,2.1],[7.9,2.1],[7.6,2.1],[7.3,2.1],[6.5,1.5],[4.7,0],[1.8,-1.2],[-1.5,-2.4],[-5.6,-2.9],[-10.0,-3.8],[-14.7,-4.1],[-17.6,-4.4],[-21.5,-5.3],[-23.8,-5.6],[-25.6,-5.9],[-26.8,-6.2],[-27.0,-6.2],[-27.3,-6.2],[-27.3,-5.3],[-27.3,-4.4],[-26.8,-2.9],[-25.9,-1.5],[-24.7,-0.3],[-24.1,0.3],[-23.2,1.2],[-22.6,1.5],[-22.0,1.8],[-21.8,2.1],[-21.5,2.1],[-21.5,2.1]];
    const blob = API.createElement({
      type: "freedraw",
      x: 0,
      y: 0,
      width: 252,
      height: 138,
      points: BLOB_POINTS.map((p) => pointFrom<LocalPoint>(p[0], p[1])),
    });
    const { elements, elementsMap } = setup([
      blob as NonDeletedExcalidrawElement,
    ]);

    const result = computeBucketFillPolygon({
      point: pointFrom<GlobalPoint>(126, 69),
      elements,
      elementsMap,
    });

    expect(result.ok).toBe(true);
    if (!result.ok) {
      return;
    }
    expect(polygonArea(result.scenePoints)).toBeGreaterThan(15000);
  });

  describe("islands (holes)", () => {
    const rect = (x: number, y: number, size: number) =>
      API.createElement({
        type: "rectangle",
        x,
        y,
        width: size,
        height: size,
        roundness: null,
        backgroundColor: "transparent",
      });

    // NOTE: `polygonArea` (abs shoelace) doubles as the NET area for keyhole
    // rings — the zero-width bridges cancel and holes subtract

    /**
     * containment under the even-odd rule — the rule the renderer paints
     * looped-line fills with, so this asserts what actually shows on screen
     */
    const evenOddContains = (pts: GlobalPoint[], p: GlobalPoint): boolean =>
      polygonIncludesPoint(p, pts as unknown as Polygon<GlobalPoint>);

    it("punches a hole for an island inside the filled region", () => {
      const outer = rect(0, 0, 200);
      const inner = rect(50, 50, 100);
      const { elements, elementsMap } = setup([outer, inner]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 100), // in the annulus
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      // annulus, not the whole outer interior (which would be ~40000)
      expect(polygonArea(result.scenePoints)).toBeCloseTo(30000, -2);
      expect(isClosed(result.scenePoints)).toBe(true);
      // the island bounds the fill too
      expect(result.boundaryElementIds).toContain(inner.id);
      // and participates in z-order: below the lowest participant
      expect(result.insertion).toEqual({
        placement: "below",
        elementId: outer.id,
      });
    });

    it("clicking inside the island still fills just the island", () => {
      const outer = rect(0, 0, 200);
      const inner = rect(50, 50, 100);
      const { elements, elementsMap } = setup([outer, inner]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(100, 100),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(result.ownerId).toBe(inner.id);
      expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -2);
    });

    it("subtracts only outermost islands (island-in-island)", () => {
      const outer = rect(0, 0, 300);
      const middle = rect(50, 50, 200);
      const innermost = rect(100, 100, 100);
      const { elements, elementsMap } = setup([outer, middle, innermost]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 150), // outer annulus
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      // outer minus middle; the innermost sits inside the hole and is
      // irrelevant to the clicked region
      expect(polygonArea(result.scenePoints)).toBeCloseTo(90000 - 40000, -2);
    });

    it("subtracts a subdivided island by its outside contour", () => {
      const outer = rect(0, 0, 200);
      const inner = rect(50, 50, 100);
      // line splitting the island into two faces — the island's footprint
      // must still be subtracted as ONE contour
      const splitter = API.createElement({
        type: "line",
        x: 50,
        y: 100,
        points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(100, 0)],
      });
      const { elements, elementsMap } = setup([outer, inner, splitter]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 100),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(polygonArea(result.scenePoints)).toBeCloseTo(30000, -2);
    });

    it("an island connected to the boundary is not a hole", () => {
      const outer = rect(0, 0, 200);
      const inner = rect(50, 50, 100);
      // line connecting the island to the outer wall merges the components;
      // the click region becomes a C-shaped single face instead
      const connector = API.createElement({
        type: "line",
        x: 150,
        y: 100,
        points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(50, 0)],
      });
      const { elements, elementsMap } = setup([outer, inner, connector]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 100),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      // same net region as the annulus, reached without any hole splicing
      expect(polygonArea(result.scenePoints)).toBeCloseTo(30000, -2);
    });

    it("an open line island does not punch a hole", () => {
      const owner = rect(0, 0, 100);
      const floating = API.createElement({
        type: "line",
        x: 30,
        y: 50,
        points: [pointFrom<LocalPoint>(0, 0), pointFrom<LocalPoint>(40, 0)],
      });
      const { elements, elementsMap } = setup([owner, floating]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(10, 10),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(polygonArea(result.scenePoints)).toBeCloseTo(10000, -2);
    });

    it("punches multiple sibling islands", () => {
      const outer = rect(0, 0, 300);
      const a = rect(30, 30, 80);
      const b = rect(190, 190, 80);
      const { elements, elementsMap } = setup([outer, a, b]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(150, 20),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(polygonArea(result.scenePoints)).toBeCloseTo(90000 - 2 * 6400, -2);
      expect(
        evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(70, 70)),
      ).toBe(false);
      expect(
        evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(230, 230)),
      ).toBe(false);
      expect(
        evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(150, 150)),
      ).toBe(true);
    });

    it("overlapping islands punch their union regardless of element order", () => {
      // regression: bounded-vs-unbounded face orientation used to be
      // inferred from the largest |area| face, but the outermost outline's
      // interior and outside contour tie on |area|, making the outcome an
      // enumeration-order coin flip — overlapping islands then decomposed
      // into arbitrary sub-face "holes" (lenses filling, islands vanishing)
      const mkRect = (x: number, y: number) =>
        API.createElement({
          type: "rectangle",
          x,
          y,
          width: 120,
          height: 80,
          roundness: null,
          backgroundColor: "transparent",
        });
      const outer = rect(0, 0, 400);
      const a = mkRect(40, 100);
      const b = mkRect(140, 140);
      const c = mkRect(240, 100);

      for (const order of [
        [a, b, c, outer],
        [c, b, a, outer],
        [b, a, c, outer],
      ]) {
        const { elements, elementsMap } = setup(order);

        const result = computeBucketFillPolygon({
          point: pointFrom<GlobalPoint>(200, 30),
          elements,
          elementsMap,
        });

        expect(result.ok).toBe(true);
        if (!result.ok) {
          return;
        }
        // outer minus the union: 3×(120×80) − two 20×40 lenses
        expect(polygonArea(result.scenePoints)).toBeCloseTo(
          160000 - (3 * 9600 - 2 * 800),
          -2,
        );
        // what renders (even-odd): every part of the union is unpainted —
        // the lenses, the single-rect parts — and the outer region is painted
        expect(
          evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(150, 160)),
        ).toBe(false); // a∩b lens
        expect(
          evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(80, 140)),
        ).toBe(false); // a only
        expect(
          evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(200, 170)),
        ).toBe(false); // b only
        expect(
          evenOddContains(result.scenePoints, pointFrom<GlobalPoint>(200, 30)),
        ).toBe(true); // outer region
      }
    });

    it("inserts below the island when the island is lowest in z-order", () => {
      const inner = rect(50, 50, 100);
      const outer = rect(0, 0, 200);
      // island BELOW the outer shape in scene order: the fill must still go
      // below the island so its outline stays visible
      const { elements, elementsMap } = setup([inner, outer]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 100),
        elements,
        elementsMap,
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      expect(result.insertion).toEqual({
        placement: "below",
        elementId: inner.id,
      });
    });

    it("a hole dropped for the point budget leaves boundaries but keeps z-order", () => {
      const inner = rect(50, 50, 100);
      const outer = rect(0, 0, 200);
      const { elements, elementsMap } = setup([inner, outer]);

      const result = computeBucketFillPolygon({
        point: pointFrom<GlobalPoint>(25, 100),
        elements,
        elementsMap,
        // the outer ring fits the cap, the hole does not
        options: { maxGeneratedPoints: 6 },
      });

      expect(result.ok).toBe(true);
      if (!result.ok) {
        return;
      }
      // the fill paints through the dropped island...
      expect(polygonArea(result.scenePoints)).toBeCloseTo(40000, -2);
      // ...so it must NOT claim the island as a boundary...
      expect(result.boundaryElementIds).not.toContain(inner.id);
      // ...but still inserts below it, keeping the painted-over island
      // visible (deliberate: see the participant-set note in the source)
      expect(result.insertion).toEqual({
        placement: "below",
        elementId: inner.id,
      });
    });
  });
});