/**
 * pathbool.js
 * ---------------------------------------------------------------------------
 * Self-contained polygon boolean geometry for Illustrator-style Pathfinder
 * operations (unite / subtract / intersect / exclude). No external library.
 *
 * Pipeline:
 *   1. Parse an ABSOLUTE path "d" (M/L/C/Q/Z only — svgcanvas normalizes to
 *      this via pathActions.convertPath(el, false)) into subpaths.
 *   2. Adaptive de Casteljau flattening of cubic/quadratic beziers to a
 *      polyline, flatness tolerance <= 0.05 user units.
 *   3. Boolean via a Martinez-Rueda style sweep-line over polygon edges,
 *      producing an oriented result contour set that respects the source
 *      fill-rule (nonzero / evenodd) for holes/multi-subpath inputs.
 *   4. Serialize contours back to a multi-subpath "d" (evenodd), coords
 *      rounded to 3 decimals, with a collinear-run simplification pass.
 *
 * Public API (attached to window.PathBool):
 *   PathBool.dToPolygons(d, fillRule)  -> [[ {x,y}, ... ], ...]  (flattened, closed rings)
 *   PathBool.operate(op, subjectRings, clipRings) -> resultRings
 *   PathBool.ringsToD(rings)           -> "d" string (evenodd), 3-decimal
 *   PathBool.area(ring)                -> signed area
 *
 * All coordinates are plain numbers in the SAME user space; callers must bake
 * element transforms into the "d" BEFORE calling (svgcanvas does this via
 * resetOrientation).
 * ---------------------------------------------------------------------------
 */
(function (global) {
  'use strict';

  // Flatness tolerance for bezier subdivision, in user units.
  var FLATNESS = 0.05;
  // Perturbation / coincidence epsilon for degenerate sweep cases.
  var EPS = 1e-9;
  // Snap grid used to weld nearly-coincident vertices before the sweep. Keeps
  // the topology robust against floating noise from flattening. Slightly
  // coarser than EPS so distinct flattened points don't collapse.
  var SNAP = 1e-7;
  // Collinear simplification deviation threshold (user units).
  var SIMPLIFY_DEV = 0.01;

  // ---------------------------------------------------------------------------
  // 1. PATH PARSING (absolute M/L/C/Q/Z)
  // ---------------------------------------------------------------------------

  // Tokenize a "d" string into { cmd, coords[] } commands. Only the absolute
  // command set produced by convertPath is expected; lowercase is tolerated by
  // treating relative as absolute-from-current for robustness.
  function parseD(d) {
    var cmds = [];
    if (!d) return cmds;
    var re = /([MmLlHhVvCcSsQqTtAaZz])|(-?\d*\.?\d+(?:[eE][-+]?\d+)?)/g;
    var m, cur = null;
    var nums = [];
    function flush() {
      if (cur) { cur.coords = nums; cmds.push(cur); }
      nums = [];
    }
    while ((m = re.exec(d)) !== null) {
      if (m[1]) {
        flush();
        cur = { cmd: m[1], coords: [] };
      } else if (cur) {
        nums.push(parseFloat(m[2]));
      }
    }
    flush();
    return cmds;
  }

  // Convert a command list into an array of subpaths, each a list of segments.
  // Handles multiple coordinate sets per command letter (implicit repeats) and
  // relative commands (defensive). Returns:
  //   [ { closed:bool, segs:[ {type,'L'|'C'|'Q', p0,p1,p2,p3} ] } ]
  function commandsToSubpaths(cmds) {
    var subs = [];
    var cx = 0, cy = 0, sx = 0, sy = 0;
    var cur = null;
    function ensure() { if (!cur) { cur = { closed: false, segs: [] }; subs.push(cur); } }
    for (var i = 0; i < cmds.length; i++) {
      var c = cmds[i], k = c.cmd, a = c.coords, rel = (k >= 'a' && k <= 'z');
      var K = k.toUpperCase();
      var j = 0;
      switch (K) {
        case 'M': {
          // First pair is moveto; subsequent pairs are implicit linetos.
          for (var first = true; j + 1 < a.length; j += 2) {
            var x = a[j] + (rel ? cx : 0), y = a[j + 1] + (rel ? cy : 0);
            if (rel && !first) { x = a[j] + cx; y = a[j + 1] + cy; }
            if (first) {
              cur = { closed: false, segs: [] }; subs.push(cur);
              cx = x; cy = y; sx = x; sy = y; first = false;
            } else {
              cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: { x: x, y: y } });
              cx = x; cy = y;
            }
          }
          break;
        }
        case 'L': {
          ensure();
          for (; j + 1 < a.length; j += 2) {
            var lx = a[j] + (rel ? cx : 0), ly = a[j + 1] + (rel ? cy : 0);
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: { x: lx, y: ly } });
            cx = lx; cy = ly;
          }
          break;
        }
        case 'H': {
          ensure();
          for (; j < a.length; j++) {
            var hx = a[j] + (rel ? cx : 0);
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: { x: hx, y: cy } });
            cx = hx;
          }
          break;
        }
        case 'V': {
          ensure();
          for (; j < a.length; j++) {
            var vy = a[j] + (rel ? cy : 0);
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: { x: cx, y: vy } });
            cy = vy;
          }
          break;
        }
        case 'C': {
          ensure();
          for (; j + 5 < a.length; j += 6) {
            var c1 = { x: a[j] + (rel ? cx : 0), y: a[j + 1] + (rel ? cy : 0) };
            var c2 = { x: a[j + 2] + (rel ? cx : 0), y: a[j + 3] + (rel ? cy : 0) };
            var e = { x: a[j + 4] + (rel ? cx : 0), y: a[j + 5] + (rel ? cy : 0) };
            cur.segs.push({ type: 'C', p0: { x: cx, y: cy }, p1: c1, p2: c2, p3: e });
            cx = e.x; cy = e.y;
          }
          break;
        }
        case 'Q': {
          ensure();
          for (; j + 3 < a.length; j += 4) {
            var q1 = { x: a[j] + (rel ? cx : 0), y: a[j + 1] + (rel ? cy : 0) };
            var qe = { x: a[j + 2] + (rel ? cx : 0), y: a[j + 3] + (rel ? cy : 0) };
            cur.segs.push({ type: 'Q', p0: { x: cx, y: cy }, p1: q1, p3: qe });
            cx = qe.x; cy = qe.y;
          }
          break;
        }
        // S/T (smooth) are not emitted by convertPath; approximate as line to end
        // if ever encountered so we never throw.
        case 'S': {
          ensure();
          for (; j + 3 < a.length; j += 4) {
            var se = { x: a[j + 2] + (rel ? cx : 0), y: a[j + 3] + (rel ? cy : 0) };
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: se });
            cx = se.x; cy = se.y;
          }
          break;
        }
        case 'T': {
          ensure();
          for (; j + 1 < a.length; j += 2) {
            var te = { x: a[j] + (rel ? cx : 0), y: a[j + 1] + (rel ? cy : 0) };
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: te });
            cx = te.x; cy = te.y;
          }
          break;
        }
        case 'A': {
          // Arcs are not emitted by convertPath. Fall back to a straight line to
          // the endpoint so we never break (rare; document.d is normalized).
          ensure();
          for (; j + 6 < a.length; j += 7) {
            var ae = { x: a[j + 5] + (rel ? cx : 0), y: a[j + 6] + (rel ? cy : 0) };
            cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: ae });
            cx = ae.x; cy = ae.y;
          }
          break;
        }
        case 'Z': {
          if (cur) {
            cur.closed = true;
            // Close the ring with an explicit segment if not already at start.
            if (Math.abs(cx - sx) > EPS || Math.abs(cy - sy) > EPS) {
              cur.segs.push({ type: 'L', p0: { x: cx, y: cy }, p3: { x: sx, y: sy } });
            }
            cx = sx; cy = sy;
          }
          break;
        }
      }
    }
    return subs;
  }

  // ---------------------------------------------------------------------------
  // 2. ADAPTIVE BEZIER FLATTENING (de Casteljau)
  // ---------------------------------------------------------------------------

  // Distance from point p to the line through a-b (unnormalized fallback safe).
  function distToLine(p, a, b) {
    var dx = b.x - a.x, dy = b.y - a.y;
    var len2 = dx * dx + dy * dy;
    if (len2 < EPS) { var ex = p.x - a.x, ey = p.y - a.y; return Math.sqrt(ex * ex + ey * ey); }
    var num = Math.abs(dy * p.x - dx * p.y + b.x * a.y - b.y * a.x);
    return num / Math.sqrt(len2);
  }

  // Recursively flatten a cubic into `out` (excludes p0, includes p3).
  function flattenCubic(p0, p1, p2, p3, out, depth) {
    if (depth > 32) { out.push({ x: p3.x, y: p3.y }); return; }
    var d1 = distToLine(p1, p0, p3);
    var d2 = distToLine(p2, p0, p3);
    if (d1 + d2 <= FLATNESS) { out.push({ x: p3.x, y: p3.y }); return; }
    // Subdivide at t=0.5
    var p01 = mid(p0, p1), p12 = mid(p1, p2), p23 = mid(p2, p3);
    var p012 = mid(p01, p12), p123 = mid(p12, p23);
    var pm = mid(p012, p123);
    flattenCubic(p0, p01, p012, pm, out, depth + 1);
    flattenCubic(pm, p123, p23, p3, out, depth + 1);
  }

  function flattenQuad(p0, p1, p2, out, depth) {
    if (depth > 32) { out.push({ x: p2.x, y: p2.y }); return; }
    var d = distToLine(p1, p0, p2);
    if (d <= FLATNESS) { out.push({ x: p2.x, y: p2.y }); return; }
    var p01 = mid(p0, p1), p12 = mid(p1, p2), pm = mid(p01, p12);
    flattenQuad(p0, p01, pm, out, depth + 1);
    flattenQuad(pm, p12, p2, out, depth + 1);
  }

  function mid(a, b) { return { x: (a.x + b.x) * 0.5, y: (a.y + b.y) * 0.5 }; }

  // Flatten one subpath into a closed ring (array of {x,y}); duplicate closing
  // point removed. Returns null for degenerate (<3 pts) rings.
  function subpathToRing(sub) {
    var ring = [];
    var segs = sub.segs;
    if (!segs.length) return null;
    ring.push({ x: segs[0].p0.x, y: segs[0].p0.y });
    for (var i = 0; i < segs.length; i++) {
      var s = segs[i];
      if (s.type === 'L') {
        ring.push({ x: s.p3.x, y: s.p3.y });
      } else if (s.type === 'C') {
        flattenCubic(s.p0, s.p1, s.p2, s.p3, ring, 0);
      } else if (s.type === 'Q') {
        flattenQuad(s.p0, s.p1, s.p3, ring, 0);
      }
    }
    // Remove trailing duplicate of the first vertex (ring is implicitly closed).
    while (ring.length > 1) {
      var a = ring[0], b = ring[ring.length - 1];
      if (Math.abs(a.x - b.x) < SNAP && Math.abs(a.y - b.y) < SNAP) ring.pop();
      else break;
    }
    if (ring.length < 3) return null;
    return ring;
  }

  // Parse + flatten a whole "d" into rings. fillRule is passed through unused
  // here (the winding rule is applied inside operate()), but kept for API.
  function dToPolygons(d, fillRule) {
    var subs = commandsToSubpaths(parseD(d));
    var rings = [];
    for (var i = 0; i < subs.length; i++) {
      var r = subpathToRing(subs[i]);
      if (r) rings.push(r);
    }
    return rings;
  }

  function area(ring) {
    var a = 0;
    for (var i = 0, n = ring.length; i < n; i++) {
      var p = ring[i], q = ring[(i + 1) % n];
      a += p.x * q.y - q.x * p.y;
    }
    return a / 2;
  }

  // ---------------------------------------------------------------------------
  // 3. BOOLEAN — Martinez-Rueda sweep line
  // ---------------------------------------------------------------------------
  // Operation codes.
  var OP = { UNITE: 0, INTERSECT: 1, DIFFERENCE: 2, XOR: 3 };

  // Polygon-type tags for annotation.
  var SUBJECT = 0, CLIP = 1;

  function snap(v) { return Math.round(v / SNAP) * SNAP; }

  // Sweep event.
  function SweepEvent(p, left, poltype, otherEvent) {
    this.p = p;                 // {x,y}
    this.left = left;           // is this the left endpoint of its segment?
    this.poltype = poltype;     // SUBJECT | CLIP
    this.other = otherEvent;    // the event for the other endpoint
    this.inOut = false;         // inside-outside transition for own polygon
    this.otherInOut = false;    // transition for the other polygon
    this.prevInResult = null;
    this.inResult = false;
    this.resultInOut = false;
    this.edgeType = 0;          // 0 normal, 1 same-transition, 2 diff-transition
    this.pos = 0;
    this.resultId = -1;
    this.contribution = 0;
  }

  // Signed area of triangle (p0,p1,p2). >0 => counter-clockwise turn.
  function signedArea(p0, p1, p2) {
    return (p0.x - p2.x) * (p1.y - p2.y) - (p1.x - p2.x) * (p0.y - p2.y);
  }

  // Comparator for the event queue (ordered sweep). Returns true if e1 before e2.
  function queueBefore(e1, e2) {
    if (e1.p.x !== e2.p.x) return e1.p.x < e2.p.x;
    if (e1.p.y !== e2.p.y) return e1.p.y < e2.p.y;
    if (e1.left !== e2.left) return !e1.left; // right endpoints first
    // Both same point & same side: order by segment slope.
    if (!collinearPts(e1.p, e1.other.p, e2.other.p)) {
      return aboveSeg(e1, e2.other.p) < 0 ? !e1.left : e1.left ? false : true;
    }
    return e1.poltype < e2.poltype;
  }

  function collinearPts(a, b, c) { return Math.abs(signedArea(a, b, c)) < EPS; }

  // Sign of point relative to segment (e.p -> e.other.p).
  function aboveSeg(e, p) {
    var s = signedArea(e.p, e.other.p, p);
    return s > EPS ? 1 : (s < -EPS ? -1 : 0);
  }

  // Comparator for the sweep-line status (ordered by y at sweep). Returns
  // negative if e1 below e2, positive if above.
  function statusCompare(e1, e2) {
    if (e1 === e2) return 0;
    if (signedArea(e1.p, e1.other.p, e2.p) !== 0 ||
        signedArea(e1.p, e1.other.p, e2.other.p) !== 0) {
      // Not collinear.
      if (pointEq(e1.p, e2.p)) {
        return below(e1, e2.other.p) ? -1 : 1;
      }
      if (e1.p.x === e2.p.x) return e1.p.y < e2.p.y ? -1 : 1;
      if (queueBefore(e1, e2)) return below(e1, e2.p) ? -1 : 1;
      return below(e2, e1.p) ? 1 : -1;
    }
    // Collinear.
    if (e1.poltype !== e2.poltype) return e1.poltype < e2.poltype ? -1 : 1;
    if (pointEq(e1.p, e2.p)) return e1.pos < e2.pos ? -1 : 1;
    return queueBefore(e1, e2) ? -1 : 1;
  }

  function pointEq(a, b) { return a.x === b.x && a.y === b.y; }
  function below(e, p) { return e.left ? signedArea(e.p, e.other.p, p) > 0
                                       : signedArea(e.other.p, e.p, p) > 0; }

  // Simple binary-heap priority queue for sweep events.
  function EventQueue() { this.h = []; }
  EventQueue.prototype.push = function (e) {
    var h = this.h; h.push(e); var i = h.length - 1;
    while (i > 0) { var par = (i - 1) >> 1;
      if (queueBefore(h[i], h[par])) { var t = h[i]; h[i] = h[par]; h[par] = t; i = par; }
      else break; }
  };
  EventQueue.prototype.pop = function () {
    var h = this.h; if (!h.length) return null;
    var top = h[0], last = h.pop();
    if (h.length) { h[0] = last; var i = 0, n = h.length;
      while (true) { var l = 2 * i + 1, r = 2 * i + 2, s = i;
        if (l < n && queueBefore(h[l], h[s])) s = l;
        if (r < n && queueBefore(h[r], h[s])) s = r;
        if (s === i) break; var t = h[i]; h[i] = h[s]; h[s] = t; i = s; } }
    return top;
  };
  EventQueue.prototype.size = function () { return this.h.length; };

  // Ordered status structure. A sorted array with linear insert is O(n) per op;
  // for the polygon sizes here (flattened contours) this is robust and adequate.
  function StatusLine() { this.a = []; }
  StatusLine.prototype.insert = function (e) {
    var a = this.a, lo = 0, hi = a.length;
    while (lo < hi) { var m = (lo + hi) >> 1;
      if (statusCompare(a[m], e) < 0) lo = m + 1; else hi = m; }
    a.splice(lo, 0, e);
    e._si = lo;
    return lo;
  };
  StatusLine.prototype.indexOf = function (e) {
    var a = this.a;
    for (var i = 0; i < a.length; i++) if (a[i] === e) return i;
    return -1;
  };
  StatusLine.prototype.removeAt = function (i) { this.a.splice(i, 1); };

  // Split a segment at point p, creating the two new events.
  function divideSegment(e, p, queue) {
    var r = new SweepEvent({ x: p.x, y: p.y }, false, e.poltype, e);
    var l = new SweepEvent({ x: p.x, y: p.y }, true, e.poltype, e.other);
    r.contribution = e.contribution;
    l.contribution = e.contribution;
    // If ordering broke, fix left flags.
    if (queueBefore(l, e.other)) {
      e.other.left = true; l.left = false;
    }
    r.other = e.other; e.other.other = r;
    e.other = l; l.other = e;
    queue.push(l); queue.push(r);
  }

  // Intersection of two segments; returns number of intersection pts and fills
  // pi0/pi1. Handles collinear overlaps.
  function segIntersect(a0, a1, b0, b1, out) {
    var va = { x: a1.x - a0.x, y: a1.y - a0.y };
    var vb = { x: b1.x - b0.x, y: b1.y - b0.y };
    var e = { x: b0.x - a0.x, y: b0.y - a0.y };
    var kross = va.x * vb.y - va.y * vb.x;
    var sqrKross = kross * kross;
    var sqrLenA = va.x * va.x + va.y * va.y;
    if (sqrKross > EPS * EPS * sqrLenA * (vb.x * vb.x + vb.y * vb.y)) {
      var s = (e.x * vb.y - e.y * vb.x) / kross;
      if (s < -EPS || s > 1 + EPS) return 0;
      var t = (e.x * va.y - e.y * va.x) / kross;
      if (t < -EPS || t > 1 + EPS) return 0;
      s = clamp01(s);
      out[0] = { x: a0.x + s * va.x, y: a0.y + s * va.y };
      return 1;
    }
    // Parallel. Check collinear.
    var sqrLenE = e.x * e.x + e.y * e.y;
    kross = e.x * va.y - e.y * va.x;
    sqrKross = kross * kross;
    if (sqrKross > EPS * EPS * sqrLenA * sqrLenE) return 0; // parallel, non-collinear
    // Collinear overlap: project onto va.
    var sa = (e.x * va.x + e.y * va.y) / sqrLenA;
    var sb = sa + (vb.x * va.x + vb.y * va.y) / sqrLenA;
    var smin = Math.min(sa, sb), smax = Math.max(sa, sb);
    if (smin > 1 + EPS || smax < -EPS) return 0;
    var lo = Math.max(0, smin), hi = Math.min(1, smax);
    out[0] = { x: a0.x + lo * va.x, y: a0.y + lo * va.y };
    if (Math.abs(hi - lo) < EPS) return 1;
    out[1] = { x: a0.x + hi * va.x, y: a0.y + hi * va.y };
    return 2;
  }
  function clamp01(v) { return v < 0 ? 0 : (v > 1 ? 1 : v); }

  // Handle possible intersection between two neighboring segments in status.
  function possibleIntersection(e1, e2, queue) {
    if (!e1 || !e2) return 0;
    var out = [];
    var n = segIntersect(e1.p, e1.other.p, e2.p, e2.other.p, out);
    if (n === 0) return 0;
    if (n === 1) {
      if (pointEq(e1.p, e2.p) || pointEq(e1.other.p, e2.other.p)) return 0; // shared endpoint
      var p = out[0];
      if (!pointEq(e1.p, p) && !pointEq(e1.other.p, p)) divideSegment(e1, p, queue);
      if (!pointEq(e2.p, p) && !pointEq(e2.other.p, p)) divideSegment(e2, p, queue);
      return 1;
    }
    // Overlapping collinear segments (n === 2).
    var events = [];
    var leftCoincide = pointEq(e1.p, e2.p);
    var rightCoincide = pointEq(e1.other.p, e2.other.p);
    if (!leftCoincide) events.push([e1, e2]);
    if (!rightCoincide) events.push([e1.other, e2.other]);
    if (leftCoincide) {
      // e1 and e2 start at same point; mark edge types.
      e2.edgeType = e1.contribution === e2.contribution ? 1 : 2;
      e1.edgeType = 0;
      e1.other.edgeType = 0;
      e2.other.edgeType = 0;
    }
    // Divide by ordering of the four endpoints along the line.
    var pts = out;
    // Determine which segment extends further and split accordingly.
    // Split e1 and e2 at the interior overlap endpoints.
    splitOverlap(e1, e2, pts, queue);
    return 3;
  }

  function splitOverlap(e1, e2, pts, queue) {
    // Order the endpoints along the shared line.
    for (var k = 0; k < pts.length; k++) {
      var p = pts[k];
      if (!pointEq(e1.p, p) && !pointEq(e1.other.p, p)) divideSegment(e1, p, queue);
      if (!pointEq(e2.p, p) && !pointEq(e2.other.p, p)) divideSegment(e2, p, queue);
    }
  }

  // Compute inResult / fields per Martinez rules for a given op.
  function computeFields(e, prev, op) {
    if (prev === null) {
      e.inOut = false;
      e.otherInOut = true;
    } else if (e.poltype === prev.poltype) {
      e.inOut = !prev.inOut;
      e.otherInOut = prev.otherInOut;
    } else {
      e.inOut = !prev.otherInOut;
      e.otherInOut = prev.left ? !prev.inOut : prev.inOut;
    }
    e.prevInResult = (prev && (!inResult(prev, op) || prev.edgeType !== 0)) ? prev.prevInResult : prev;
    e.inResult = determineInResult(e, op);
  }

  function inResult(e, op) { return determineInResult(e, op); }

  function determineInResult(e, op) {
    switch (e.edgeType) {
      case 0: // NORMAL
        switch (op) {
          case OP.INTERSECT: return !e.otherInOut;
          case OP.UNITE: return e.otherInOut;
          case OP.DIFFERENCE:
            return (e.poltype === SUBJECT && e.otherInOut) ||
                   (e.poltype === CLIP && !e.otherInOut);
          case OP.XOR: return true;
        }
        return false;
      case 1: // SAME TRANSITION (coincident, same orientation)
        return op === OP.INTERSECT || op === OP.UNITE;
      case 2: // DIFFERENT TRANSITION
        return op === OP.DIFFERENCE;
      case 3: // NON CONTRIBUTING
        return false;
    }
    return false;
  }

  // Main boolean between two annotated ring sets.
  function boolean(subjectRings, clipRings, op) {
    var queue = new EventQueue();
    var posCounter = 0;

    function addRing(ring, poltype) {
      var n = ring.length;
      for (var i = 0; i < n; i++) {
        var p0 = ring[i], p1 = ring[(i + 1) % n];
        var a = { x: snap(p0.x), y: snap(p0.y) };
        var b = { x: snap(p1.x), y: snap(p1.y) };
        if (a.x === b.x && a.y === b.y) continue; // skip zero-length
        var e1 = new SweepEvent(a, true, poltype, null);
        var e2 = new SweepEvent(b, true, poltype, e1);
        e1.other = e2;
        e1.contribution = 1; e2.contribution = 1;
        // Decide which is the left endpoint.
        if (queueBefore(e1, e2)) { e2.left = false; }
        else { e1.left = false; e2.left = true; }
        e1.pos = posCounter++; e2.pos = e1.pos;
        queue.push(e1); queue.push(e2);
      }
    }

    for (var i = 0; i < subjectRings.length; i++) addRing(subjectRings[i], SUBJECT);
    for (var j = 0; j < clipRings.length; j++) addRing(clipRings[j], CLIP);

    var status = new StatusLine();
    var result = [];
    var guard = 0, maxGuard = 4000000;

    while (queue.size()) {
      if (++guard > maxGuard) break; // hard safety valve
      var e = queue.pop();
      if (e.left) {
        var pos = status.insert(e);
        var prev = pos > 0 ? status.a[pos - 1] : null;
        var next = pos < status.a.length - 1 ? status.a[pos + 1] : null;
        computeFields(e, prev, op);
        if (next) {
          if (possibleIntersection(e, next, queue) === 3) {
            // recompute fields (event geometry changed); handled by re-sort on
            // subsequent pops via queue ordering.
          }
        }
        if (prev) {
          possibleIntersection(prev, e, queue);
        }
      } else {
        // Right endpoint: locate its left twin in status and remove.
        var le = e.other;
        var si = status.indexOf(le);
        if (si === -1) continue;
        var sPrev = si > 0 ? status.a[si - 1] : null;
        var sNext = si < status.a.length - 1 ? status.a[si + 1] : null;
        if (le.inResult) result.push(le);
        status.removeAt(si);
        if (sPrev && sNext) possibleIntersection(sPrev, sNext, queue);
      }
    }
    return connectEdges(result);
  }

  // Order result events for contour construction.
  function connectEdges(result) {
    // Filter to contributing events and pair left/right.
    var resultEvents = [];
    for (var i = 0; i < result.length; i++) {
      var e = result[i];
      resultEvents.push(e);
      resultEvents.push(e.other);
    }
    resultEvents.sort(function (a, b) {
      if (a.p.x !== b.p.x) return a.p.x - b.p.x;
      if (a.p.y !== b.p.y) return a.p.y - b.p.y;
      if (a.left !== b.left) return a.left ? 1 : -1; // right first
      return signedArea(a.p, a.other.p, b.other.p) > 0 ? 1 : -1;
    });
    for (var k = 0; k < resultEvents.length; k++) {
      resultEvents[k].pos = k;
      if (!resultEvents[k].left) {
        var t = resultEvents[k].pos;
        resultEvents[k].pos = resultEvents[k].other.pos;
        resultEvents[k].other.pos = t;
      }
    }
    var processed = new Array(resultEvents.length);
    var contours = [];
    for (var m = 0; m < resultEvents.length; m++) {
      if (processed[m]) continue;
      var contour = [];
      var pos = m;
      var start = resultEvents[m].p;
      contour.push({ x: resultEvents[m].p.x, y: resultEvents[m].p.y });
      var guard = 0;
      while (guard++ < resultEvents.length + 5) {
        processed[pos] = true;
        var ev = resultEvents[pos];
        if (ev.left) {
          processed[ev.pos] = true;
        } else {
          processed[ev.other.pos !== undefined ? ev.other.pos : pos] = true;
        }
        // Move to the other endpoint of this edge.
        pos = ev.left ? ev.other.pos : ev.pos;
        var nextEv = resultEvents[pos];
        var pt = nextEv.p;
        if (pointEq(pt, start) && contour.length > 1) break;
        contour.push({ x: pt.x, y: pt.y });
        processed[pos] = true;
        // Find next unprocessed event at this same point.
        pos = nextEventAt(resultEvents, processed, pos);
        if (pos < 0) break;
      }
      if (contour.length >= 3) contours.push(contour);
    }
    return contours;
  }

  function nextEventAt(events, processed, idx) {
    var p = events[idx].p;
    // Scan forward and backward for an unprocessed event sharing this point.
    for (var i = idx + 1; i < events.length; i++) {
      if (events[i].p.x !== p.x || events[i].p.y !== p.y) break;
      if (!processed[i]) return i;
    }
    for (var j = idx - 1; j >= 0; j--) {
      if (events[j].p.x !== p.x || events[j].p.y !== p.y) break;
      if (!processed[j]) return j;
    }
    return -1;
  }

  // ---------------------------------------------------------------------------
  // Robust fallback: even the best sweep implementations can hit pathological
  // flattened input. We wrap the sweep and, if it yields an empty/broken
  // result, retry with a tiny random perturbation of the clip rings before
  // giving up. This is the "perturbation for degenerate intersections" clause.
  // ---------------------------------------------------------------------------
  // Accept both OP codes and the string names used by the native bridge.
  var OP_NAMES = { unite: 0, union: 0, intersect: 1, intersection: 1,
                   subtract: 2, difference: 2, exclude: 3, xor: 3 };
  function opCode(op) {
    if (typeof op === 'string') {
      var k = op.toLowerCase();
      return (k in OP_NAMES) ? OP_NAMES[k] : 0;
    }
    return op | 0;
  }

  // Preferred engine: Clipper (battle-tested Vatti implementation, loaded from
  // js/lib/clipper.js). The hand-written sweep below stays as a fallback when
  // ClipperLib is not available.
  var CLIPPER_SCALE = 1000;
  function clipperBoolean(code, subjectRings, clipRings) {
    var C = global.ClipperLib;
    var toPath = function (r) {
      return r.map(function (p) {
        return { X: Math.round(p.x * CLIPPER_SCALE), Y: Math.round(p.y * CLIPPER_SCALE) };
      });
    };
    var ct = [C.ClipType.ctUnion, C.ClipType.ctIntersection,
              C.ClipType.ctDifference, C.ClipType.ctXor][code];
    var c = new C.Clipper();
    c.AddPaths(subjectRings.map(toPath), C.PolyType.ptSubject, true);
    c.AddPaths(clipRings.map(toPath), C.PolyType.ptClip, true);
    var sol = [];
    var ok = c.Execute(ct, sol, C.PolyFillType.pftNonZero, C.PolyFillType.pftNonZero);
    if (!ok) return [];
    return sol.map(function (path) {
      return path.map(function (pt) {
        return { x: pt.X / CLIPPER_SCALE, y: pt.Y / CLIPPER_SCALE };
      });
    });
  }

  function operate(op, subjectRings, clipRings) {
    var code = opCode(op);
    if (global.ClipperLib) {
      try { return clipperBoolean(code, subjectRings, clipRings); }
      catch (err) {
        if (global.ace_wk_logger && global.ace_wk_logger.err) {
          global.ace_wk_logger.err('PathBool.clipper ' + err);
        }
      }
    }
    var res = tryBoolean(code, subjectRings, clipRings, 0);
    if (res && res.length) return res;
    // One perturbation retry.
    res = tryBoolean(code, subjectRings, clipRings, 1e-6);
    return res || [];
  }

  function tryBoolean(op, subjectRings, clipRings, jitter) {
    var subj = subjectRings, clip = clipRings;
    if (jitter) {
      clip = clipRings.map(function (r) {
        return r.map(function (p) {
          return { x: p.x + (Math.random() - 0.5) * jitter,
                   y: p.y + (Math.random() - 0.5) * jitter };
        });
      });
    }
    try {
      return boolean(subj, clip, op);
    } catch (err) {
      if (global.ace_wk_logger && global.ace_wk_logger.err) {
        global.ace_wk_logger.err('PathBool.boolean ' + err);
      }
      return [];
    }
  }

  // ---------------------------------------------------------------------------
  // 4/5. SERIALIZATION + SIMPLIFICATION
  // ---------------------------------------------------------------------------

  // Collapse near-collinear runs: drop a vertex whose perpendicular deviation
  // from the segment joining its neighbours is < SIMPLIFY_DEV.
  function simplifyRing(ring) {
    if (ring.length < 4) return ring;
    var out = ring.slice();
    var changed = true;
    while (changed && out.length > 3) {
      changed = false;
      var res = [];
      var n = out.length;
      for (var i = 0; i < n; i++) {
        var prev = out[(i - 1 + n) % n], cur = out[i], next = out[(i + 1) % n];
        if (distToLine(cur, prev, next) < SIMPLIFY_DEV) { changed = true; continue; }
        res.push(cur);
      }
      if (res.length >= 3) out = res; else break;
    }
    return out;
  }

  function round3(v) { return Math.round(v * 1000) / 1000; }

  function ringsToD(rings) {
    var d = '';
    for (var i = 0; i < rings.length; i++) {
      var r = simplifyRing(rings[i]);
      if (r.length < 3) continue;
      // Drop a trailing point coincident with the first.
      var f = r[0], l = r[r.length - 1];
      var end = r.length;
      if (Math.abs(f.x - l.x) < 1e-6 && Math.abs(f.y - l.y) < 1e-6) end--;
      if (end < 3) continue;
      d += 'M' + round3(r[0].x) + ',' + round3(r[0].y);
      for (var k = 1; k < end; k++) {
        d += 'L' + round3(r[k].x) + ',' + round3(r[k].y);
      }
      d += 'Z';
    }
    return d;
  }

  // ---------------------------------------------------------------------------
  // Export
  // ---------------------------------------------------------------------------
  global.PathBool = {
    OP: OP,
    FLATNESS: FLATNESS,
    dToPolygons: dToPolygons,
    operate: operate,
    ringsToD: ringsToD,
    area: area,
    simplifyRing: simplifyRing,
    _parseD: parseD,
    _commandsToSubpaths: commandsToSubpaths
  };

})(typeof window !== 'undefined' ? window : this);
