{"version":3,"sources":["../../src/geom-in.ts","../../src/constant.ts","../../src/compare.ts","../../src/orient.ts","../../src/snap.ts","../../src/identity.ts","../../src/precision.ts","../../src/bbox.ts","../../src/operation.ts","../../src/vector.ts","../../src/sweep-event.ts","../../src/geom-out.ts","../../src/sweep-line.ts","../../src/segment.ts","../../src/index.ts"],"sourcesContent":["import BigNumber from \"bignumber.js\";\nimport { Bbox } from \"./bbox.js\";\nimport { precision } from \"./precision.js\";\nimport Segment from \"./segment.js\";\nimport { Point } from \"./sweep-event.js\";\n\nexport type Ring = [number, number][]\nexport type Poly = Ring[]\nexport type MultiPoly = Poly[]\nexport type Geom = Poly | MultiPoly\n\nexport class RingIn {\n poly: PolyIn\n isExterior: boolean\n segments: Segment[]\n bbox: Bbox\n\n constructor(geomRing: Ring, poly: PolyIn, isExterior: boolean) {\n if (!Array.isArray(geomRing) || geomRing.length === 0) {\n throw new Error(\"Input geometry is not a valid Polygon or MultiPolygon\")\n }\n\n this.poly = poly\n this.isExterior = isExterior\n this.segments = []\n\n if (\n typeof geomRing[0][0] !== \"number\" ||\n typeof geomRing[0][1] !== \"number\"\n ) {\n throw new Error(\"Input geometry is not a valid Polygon or MultiPolygon\")\n }\n\n const firstPoint = precision.snap({ x: new BigNumber(geomRing[0][0]), y: new BigNumber(geomRing[0][1]) }) as Point\n this.bbox = {\n ll: { x: firstPoint.x, y: firstPoint.y },\n ur: { x: firstPoint.x, y: firstPoint.y },\n }\n\n let prevPoint = firstPoint\n for (let i = 1, iMax = geomRing.length; i < iMax; i++) {\n if (\n typeof geomRing[i][0] !== \"number\" ||\n typeof geomRing[i][1] !== \"number\"\n ) {\n throw new Error(\"Input geometry is not a valid Polygon or MultiPolygon\")\n }\n const point = precision.snap({ x: new BigNumber(geomRing[i][0]), y: new BigNumber(geomRing[i][1]) }) as Point\n // skip repeated points\n if (point.x.eq(prevPoint.x) && point.y.eq(prevPoint.y)) continue\n this.segments.push(Segment.fromRing(prevPoint, point, this))\n if (point.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = point.x\n if (point.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = point.y\n if (point.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = point.x\n if (point.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = point.y\n prevPoint = point\n }\n // add segment from last to first if last is not the same as first\n if (!firstPoint.x.eq(prevPoint.x) || !firstPoint.y.eq(prevPoint.y)) {\n this.segments.push(Segment.fromRing(prevPoint, firstPoint, this))\n }\n }\n\n getSweepEvents() {\n const sweepEvents = []\n for (let i = 0, iMax = this.segments.length; i < iMax; i++) {\n const segment = this.segments[i]\n sweepEvents.push(segment.leftSE)\n sweepEvents.push(segment.rightSE)\n }\n return sweepEvents\n }\n}\n\nexport class PolyIn {\n multiPoly: MultiPolyIn\n exteriorRing: RingIn\n interiorRings: RingIn[]\n bbox: Bbox\n\n constructor(geomPoly: Poly, multiPoly: MultiPolyIn) {\n if (!Array.isArray(geomPoly)) {\n throw new Error(\"Input geometry is not a valid Polygon or MultiPolygon\")\n }\n this.exteriorRing = new RingIn(geomPoly[0], this, true)\n // copy by value\n this.bbox = {\n ll: { x: this.exteriorRing.bbox.ll.x, y: this.exteriorRing.bbox.ll.y },\n ur: { x: this.exteriorRing.bbox.ur.x, y: this.exteriorRing.bbox.ur.y },\n }\n this.interiorRings = []\n for (let i = 1, iMax = geomPoly.length; i < iMax; i++) {\n const ring = new RingIn(geomPoly[i], this, false)\n if (ring.bbox.ll.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = ring.bbox.ll.x\n if (ring.bbox.ll.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = ring.bbox.ll.y\n if (ring.bbox.ur.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = ring.bbox.ur.x\n if (ring.bbox.ur.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = ring.bbox.ur.y\n this.interiorRings.push(ring)\n }\n this.multiPoly = multiPoly\n }\n\n getSweepEvents() {\n const sweepEvents = this.exteriorRing.getSweepEvents()\n for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) {\n const ringSweepEvents = this.interiorRings[i].getSweepEvents()\n for (let j = 0, jMax = ringSweepEvents.length; j < jMax; j++) {\n sweepEvents.push(ringSweepEvents[j])\n }\n }\n return sweepEvents\n }\n}\n\nexport class MultiPolyIn {\n isSubject: boolean\n polys: PolyIn[]\n bbox: Bbox\n\n constructor(geom: Geom, isSubject: boolean) {\n if (!Array.isArray(geom)) {\n throw new Error(\"Input geometry is not a valid Polygon or MultiPolygon\")\n }\n\n try {\n // if the input looks like a polygon, convert it to a multipolygon\n if (typeof geom[0][0][0] === \"number\") geom = [geom as Poly]\n } catch (ex) {\n // The input is either malformed or has empty arrays.\n // In either case, it will be handled later on.\n }\n\n this.polys = []\n this.bbox = {\n ll: { x: new BigNumber(Number.POSITIVE_INFINITY), y: new BigNumber(Number.POSITIVE_INFINITY) },\n ur: { x: new BigNumber(Number.NEGATIVE_INFINITY), y: new BigNumber(Number.NEGATIVE_INFINITY) },\n }\n for (let i = 0, iMax = geom.length; i < iMax; i++) {\n const poly = new PolyIn(geom[i] as Poly, this)\n if (poly.bbox.ll.x.isLessThan(this.bbox.ll.x)) this.bbox.ll.x = poly.bbox.ll.x\n if (poly.bbox.ll.y.isLessThan(this.bbox.ll.y)) this.bbox.ll.y = poly.bbox.ll.y\n if (poly.bbox.ur.x.isGreaterThan(this.bbox.ur.x)) this.bbox.ur.x = poly.bbox.ur.x\n if (poly.bbox.ur.y.isGreaterThan(this.bbox.ur.y)) this.bbox.ur.y = poly.bbox.ur.y\n this.polys.push(poly)\n }\n this.isSubject = isSubject\n }\n\n getSweepEvents() {\n const sweepEvents = []\n for (let i = 0, iMax = this.polys.length; i < iMax; i++) {\n const polySweepEvents = this.polys[i].getSweepEvents()\n for (let j = 0, jMax = polySweepEvents.length; j < jMax; j++) {\n sweepEvents.push(polySweepEvents[j])\n }\n }\n return sweepEvents\n }\n}\n","export default (x: T) => {\n return () => {\n return x\n }\n}","import BigNumber from \"bignumber.js\"\nimport constant from \"./constant.js\"\n\nexport default (eps?: number) => {\n const almostEqual = eps ? (a: BigNumber, b: BigNumber) =>\n b.minus(a).abs().isLessThanOrEqualTo(eps)\n : constant(false)\n\n return (a: BigNumber, b: BigNumber) => {\n if (almostEqual(a, b)) return 0\n\n return a.comparedTo(b)\n }\n}","import BigNumber from \"bignumber.js\";\nimport constant from \"./constant.js\";\nimport { Vector } from \"./vector.js\";\n\nexport default function (eps?: number) {\n const almostCollinear = eps ? (area2: BigNumber, ax: BigNumber, ay: BigNumber, cx: BigNumber, cy: BigNumber) =>\n area2.exponentiatedBy(2).isLessThanOrEqualTo(\n cx.minus(ax).exponentiatedBy(2).plus(cy.minus(ay).exponentiatedBy(2))\n .times(eps))\n : constant(false)\n\n return (a: Vector, b: Vector, c: Vector) => {\n const ax = a.x, ay = a.y, cx = c.x, cy = c.y\n\n const area2 = ay.minus(cy).times(b.x.minus(cx)).minus(ax.minus(cx).times(b.y.minus(cy)))\n\n if (almostCollinear(area2, ax, ay, cx, cy)) return 0\n\n return area2.comparedTo(0)\n }\n}","import BigNumber from \"bignumber.js\";\nimport { SplayTreeSet } from \"splaytree-ts\"\nimport compare from \"./compare.js\";\nimport identity from \"./identity.js\";\nimport { Vector } from \"./vector.js\";\n\nexport default (eps?: number) => {\n if (eps) {\n\n const xTree = new SplayTreeSet(compare(eps))\n const yTree = new SplayTreeSet(compare(eps))\n\n const snapCoord = (coord: BigNumber, tree: SplayTreeSet) => {\n return tree.addAndReturn(coord)\n }\n\n const snap = (v: Vector) => {\n return {\n x: snapCoord(v.x, xTree),\n y: snapCoord(v.y, yTree),\n } as Vector\n }\n\n snap({ x: new BigNumber(0), y: new BigNumber(0)})\n\n return snap\n }\n\n return identity\n}","export default (x: T) => {\n return x;\n}","import compare from \"./compare.js\";\nimport orient from \"./orient.js\";\nimport snap from \"./snap.js\";\n\nconst set = (eps?: number) => {\n return {\n set: (eps?: number) => { precision = set(eps) },\n reset: () => set(eps),\n compare: compare(eps),\n snap: snap(eps),\n orient: orient(eps)\n }\n}\n\nexport let precision: ReturnType = set()","import { Vector } from \"./vector.js\";\n\nexport interface Bbox {\n ll: Vector;\n ur: Vector;\n}\n\n/**\n * A bounding box has the format:\n *\n * { ll: { x: xmin, y: ymin }, ur: { x: xmax, y: ymax } }\n *\n */\n\nexport const isInBbox = (bbox: Bbox, point: Vector) => {\n return (\n bbox.ll.x.isLessThanOrEqualTo(point.x) &&\n point.x.isLessThanOrEqualTo(bbox.ur.x) &&\n bbox.ll.y.isLessThanOrEqualTo(point.y) &&\n point.y.isLessThanOrEqualTo(bbox.ur.y) \n )\n}\n\n/* Returns either null, or a bbox (aka an ordered pair of points)\n * If there is only one point of overlap, a bbox with identical points\n * will be returned */\nexport const getBboxOverlap = (b1: Bbox, b2: Bbox) => {\n // check if the bboxes overlap at all\n if (\n b2.ur.x.isLessThan(b1.ll.x) ||\n b1.ur.x.isLessThan(b2.ll.x) ||\n b2.ur.y.isLessThan(b1.ll.y) ||\n b1.ur.y.isLessThan(b2.ll.y) \n )\n return null\n\n // find the middle two X values\n const lowerX = b1.ll.x.isLessThan(b2.ll.x) ? b2.ll.x : b1.ll.x\n const upperX = b1.ur.x.isLessThan(b2.ur.x) ? b1.ur.x : b2.ur.x\n\n // find the middle two Y values\n const lowerY = b1.ll.y.isLessThan(b2.ll.y) ? b2.ll.y : b1.ll.y\n const upperY = b1.ur.y.isLessThan(b2.ur.y) ? b1.ur.y : b2.ur.y\n\n // put those middle values together to get the overlap\n return { ll: { x: lowerX, y: lowerY }, ur: { x: upperX, y: upperY } } as Bbox\n}\n","import { SplayTreeSet } from \"splaytree-ts\"\nimport { getBboxOverlap } from \"./bbox.js\"\nimport * as geomIn from \"./geom-in.js\"\nimport { Geom } from \"./geom-in.js\"\nimport * as geomOut from \"./geom-out.js\"\nimport { precision } from \"./precision.js\"\nimport SweepEvent from \"./sweep-event.js\"\nimport SweepLine from \"./sweep-line.js\"\n\nexport class Operation {\n type!: string\n numMultiPolys!: number\n\n run(type: string, geom: Geom, moreGeoms: Geom[]) {\n operation.type = type\n\n /* Convert inputs to MultiPoly objects */\n const multipolys = [new geomIn.MultiPolyIn(geom, true)]\n for (let i = 0, iMax = moreGeoms.length; i < iMax; i++) {\n multipolys.push(new geomIn.MultiPolyIn(moreGeoms[i], false))\n }\n operation.numMultiPolys = multipolys.length\n\n /* BBox optimization for difference operation\n * If the bbox of a multipolygon that's part of the clipping doesn't\n * intersect the bbox of the subject at all, we can just drop that\n * multiploygon. */\n if (operation.type === \"difference\") {\n // in place removal\n const subject = multipolys[0]\n let i = 1\n while (i < multipolys.length) {\n if (getBboxOverlap(multipolys[i].bbox, subject.bbox) !== null) i++\n else multipolys.splice(i, 1)\n }\n }\n\n /* BBox optimization for intersection operation\n * If we can find any pair of multipolygons whose bbox does not overlap,\n * then the result will be empty. */\n if (operation.type === \"intersection\") {\n // TODO: this is O(n^2) in number of polygons. By sorting the bboxes,\n // it could be optimized to O(n * ln(n))\n for (let i = 0, iMax = multipolys.length; i < iMax; i++) {\n const mpA = multipolys[i]\n for (let j = i + 1, jMax = multipolys.length; j < jMax; j++) {\n if (getBboxOverlap(mpA.bbox, multipolys[j].bbox) === null) return []\n }\n }\n }\n\n /* Put segment endpoints in a priority queue */\n const queue = new SplayTreeSet(SweepEvent.compare)\n for (let i = 0, iMax = multipolys.length; i < iMax; i++) {\n const sweepEvents = multipolys[i].getSweepEvents()\n for (let j = 0, jMax = sweepEvents.length; j < jMax; j++) {\n queue.add(sweepEvents[j])\n }\n }\n\n /* Pass the sweep line over those endpoints */\n const sweepLine = new SweepLine(queue)\n let evt = null\n if (queue.size != 0) {\n evt = queue.first()\n queue.delete(evt)\n }\n while (evt) {\n const newEvents = sweepLine.process(evt)\n for (let i = 0, iMax = newEvents.length; i < iMax; i++) {\n const evt = newEvents[i]\n if (evt.consumedBy === undefined) queue.add(evt)\n }\n if (queue.size != 0) {\n evt = queue.first()\n queue.delete(evt)\n } else {\n evt = null;\n }\n }\n\n // free some memory we don't need anymore\n precision.reset()\n\n /* Collect and compile segments we're keeping into a multipolygon */\n const ringsOut = geomOut.RingOut.factory(sweepLine.segments)\n const result = new geomOut.MultiPolyOut(ringsOut)\n return result.getGeom()\n }\n}\n\n// singleton available by import\nconst operation = new Operation()\n\nexport default operation\n","import * as bn from \"bignumber.js\";\n\nexport interface Vector {\n x: bn.BigNumber;\n y: bn.BigNumber;\n}\n\n/* Cross Product of two vectors with first point at origin */\nexport const crossProduct = (a: Vector, b: Vector) => a.x.times(b.y).minus(a.y.times(b.x))\n\n/* Dot Product of two vectors with first point at origin */\nexport const dotProduct = (a: Vector, b: Vector) => a.x.times(b.x).plus(a.y.times(b.y))\n\nexport const length = (v: Vector) => dotProduct(v, v).sqrt()\n\n/* Get the sine of the angle from pShared -> pAngle to pShaed -> pBase */\nexport const sineOfAngle = (pShared: Vector, pBase: Vector, pAngle: Vector) => {\n const vBase = { x: pBase.x.minus(pShared.x), y: pBase.y.minus(pShared.y) }\n const vAngle = { x: pAngle.x.minus(pShared.x), y: pAngle.y.minus(pShared.y) }\n return crossProduct(vAngle, vBase).div(length(vAngle)).div(length(vBase))\n}\n\n/* Get the cosine of the angle from pShared -> pAngle to pShaed -> pBase */\nexport const cosineOfAngle = (pShared: Vector, pBase: Vector, pAngle: Vector) => {\n const vBase = { x: pBase.x.minus(pShared.x), y: pBase.y.minus(pShared.y) }\n const vAngle = { x: pAngle.x.minus(pShared.x), y: pAngle.y.minus(pShared.y) }\n return dotProduct(vAngle, vBase).div(length(vAngle)).div(length(vBase))\n}\n\n/* Get the x coordinate where the given line (defined by a point and vector)\n * crosses the horizontal line with the given y coordiante.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const horizontalIntersection = (pt: Vector, v: Vector, y: bn.BigNumber) => {\n if (v.y.isZero()) return null\n return { x: pt.x.plus((v.x.div(v.y)).times(y.minus(pt.y))), y: y }\n}\n\n/* Get the y coordinate where the given line (defined by a point and vector)\n * crosses the vertical line with the given x coordiante.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const verticalIntersection = (pt: Vector, v: Vector, x: bn.BigNumber) => {\n if (v.x.isZero()) return null\n return { x: x, y: pt.y.plus((v.y.div(v.x)).times(x.minus(pt.x))) }\n}\n\n/* Get the intersection of two lines, each defined by a base point and a vector.\n * In the case of parrallel lines (including overlapping ones) returns null. */\nexport const intersection = (pt1: Vector, v1: Vector, pt2: Vector, v2: Vector) => {\n // take some shortcuts for vertical and horizontal lines\n // this also ensures we don't calculate an intersection and then discover\n // it's actually outside the bounding box of the line\n if (v1.x.isZero()) return verticalIntersection(pt2, v2, pt1.x)\n if (v2.x.isZero()) return verticalIntersection(pt1, v1, pt2.x)\n if (v1.y.isZero()) return horizontalIntersection(pt2, v2, pt1.y)\n if (v2.y.isZero()) return horizontalIntersection(pt1, v1, pt2.y)\n\n // General case for non-overlapping segments.\n // This algorithm is based on Schneider and Eberly.\n // http://www.cimec.org.ar/~ncalvo/Schneider_Eberly.pdf - pg 244\n\n const kross = crossProduct(v1, v2)\n if (kross.isZero()) return null\n\n const ve = { x: pt2.x.minus(pt1.x), y: pt2.y.minus(pt1.y) }\n const d1 = crossProduct(ve, v1).div(kross)\n const d2 = crossProduct(ve, v2).div(kross)\n\n // take the average of the two calculations to minimize rounding error\n const x1 = pt1.x.plus(d2.times(v1.x)),\n x2 = pt2.x.plus(d1.times(v2.x))\n const y1 = pt1.y.plus(d2.times(v1.y)),\n y2 = pt2.y.plus(d1.times(v2.y))\n const x = x1.plus(x2).div(2)\n const y = y1.plus(y2).div(2)\n return { x: x, y: y } as Vector\n}\n\n/* Given a vector, return one that is perpendicular */\nexport const perpendicular = (v: Vector) => {\n return { x: v.y.negated(), y: v.x }\n}","import BigNumber from \"bignumber.js\";\nimport Segment from \"./segment.js\"\nimport { cosineOfAngle, sineOfAngle, Vector } from \"./vector.js\"\n\nexport interface Point extends Vector {\n events: SweepEvent[];\n}\n\nexport default class SweepEvent {\n point: Point;\n isLeft: boolean;\n segment!: Segment;\n otherSE!: SweepEvent;\n consumedBy: SweepEvent | undefined;\n\n // for ordering sweep events in the sweep event queue\n static compare(a: SweepEvent, b: SweepEvent) {\n // favor event with a point that the sweep line hits first\n const ptCmp = SweepEvent.comparePoints(a.point, b.point)\n if (ptCmp !== 0) return ptCmp\n\n // the points are the same, so link them if needed\n if (a.point !== b.point) a.link(b)\n\n // favor right events over left\n if (a.isLeft !== b.isLeft) return a.isLeft ? 1 : -1\n\n // we have two matching left or right endpoints\n // ordering of this case is the same as for their segments\n return Segment.compare(a.segment, b.segment)\n }\n\n // for ordering points in sweep line order\n static comparePoints(aPt: Point, bPt: Point) {\n if (aPt.x.isLessThan(bPt.x)) return -1\n if (aPt.x.isGreaterThan(bPt.x)) return 1\n\n if (aPt.y.isLessThan(bPt.y)) return -1\n if (aPt.y.isGreaterThan(bPt.y)) return 1\n\n return 0\n }\n\n // Warning: 'point' input will be modified and re-used (for performance)\n constructor(point: Point, isLeft: boolean) {\n if (point.events === undefined) point.events = [this]\n else point.events.push(this)\n this.point = point\n this.isLeft = isLeft\n // this.segment, this.otherSE set by factory\n }\n\n link(other: SweepEvent) {\n if (other.point === this.point) {\n throw new Error(\"Tried to link already linked events\")\n }\n const otherEvents = other.point.events\n for (let i = 0, iMax = otherEvents.length; i < iMax; i++) {\n const evt = otherEvents[i]\n this.point.events.push(evt)\n evt.point = this.point\n }\n this.checkForConsuming()\n }\n\n /* Do a pass over our linked events and check to see if any pair\n * of segments match, and should be consumed. */\n checkForConsuming() {\n // FIXME: The loops in this method run O(n^2) => no good.\n // Maintain little ordered sweep event trees?\n // Can we maintaining an ordering that avoids the need\n // for the re-sorting with getLeftmostComparator in geom-out?\n\n // Compare each pair of events to see if other events also match\n const numEvents = this.point.events.length\n for (let i = 0; i < numEvents; i++) {\n const evt1 = this.point.events[i]\n if (evt1.segment.consumedBy !== undefined) continue\n for (let j = i + 1; j < numEvents; j++) {\n const evt2 = this.point.events[j]\n if (evt2.consumedBy !== undefined) continue\n if (evt1.otherSE.point.events !== evt2.otherSE.point.events) continue\n evt1.segment.consume(evt2.segment)\n }\n }\n }\n\n getAvailableLinkedEvents() {\n // point.events is always of length 2 or greater\n const events = []\n for (let i = 0, iMax = this.point.events.length; i < iMax; i++) {\n const evt = this.point.events[i]\n if (evt !== this && !evt.segment.ringOut && evt.segment.isInResult()) {\n events.push(evt)\n }\n }\n return events\n }\n\n /**\n * Returns a comparator function for sorting linked events that will\n * favor the event that will give us the smallest left-side angle.\n * All ring construction starts as low as possible heading to the right,\n * so by always turning left as sharp as possible we'll get polygons\n * without uncessary loops & holes.\n *\n * The comparator function has a compute cache such that it avoids\n * re-computing already-computed values.\n */\n getLeftmostComparator(baseEvent: SweepEvent) {\n const cache = new Map()\n\n const fillCache = (linkedEvent: SweepEvent) => {\n const nextEvent = linkedEvent.otherSE\n cache.set(linkedEvent, {\n sine: sineOfAngle(this.point, baseEvent.point, nextEvent.point),\n cosine: cosineOfAngle(this.point, baseEvent.point, nextEvent.point),\n })\n }\n\n return (a: SweepEvent, b: SweepEvent) => {\n if (!cache.has(a)) fillCache(a)\n if (!cache.has(b)) fillCache(b)\n\n const { sine: asine, cosine: acosine } = cache.get(a)!\n const { sine: bsine, cosine: bcosine } = cache.get(b)!\n\n // both on or above x-axis\n if (asine.isGreaterThanOrEqualTo(0) && bsine.isGreaterThanOrEqualTo(0)) {\n if (acosine.isLessThan(bcosine)) return 1\n if (acosine.isGreaterThan(bcosine)) return -1\n return 0\n }\n\n // both below x-axis\n if (asine.isLessThan(0) && bsine.isLessThan(0)) {\n if (acosine.isLessThan(bcosine)) return -1\n if (acosine.isGreaterThan(bcosine)) return 1\n return 0\n }\n\n // one above x-axis, one below\n if (bsine.isLessThan(asine)) return -1\n if (bsine.isGreaterThan(asine)) return 1\n return 0\n }\n }\n}\n","import { MultiPoly, Poly, Ring } from \"./geom-in.js\"\nimport { precision } from \"./precision.js\"\nimport Segment from \"./segment.js\"\nimport SweepEvent from \"./sweep-event.js\"\n\nexport class RingOut {\n events: SweepEvent[]\n poly: PolyOut | null\n _isExteriorRing: boolean | undefined\n _enclosingRing: RingOut | null | undefined\n \n /* Given the segments from the sweep line pass, compute & return a series\n * of closed rings from all the segments marked to be part of the result */\n static factory(allSegments: Segment[]) {\n const ringsOut = []\n\n for (let i = 0, iMax = allSegments.length; i < iMax; i++) {\n const segment = allSegments[i]\n if (!segment.isInResult() || segment.ringOut) continue\n\n let prevEvent = null\n let event = segment.leftSE\n let nextEvent = segment.rightSE\n const events = [event]\n\n const startingPoint = event.point\n const intersectionLEs = []\n\n /* Walk the chain of linked events to form a closed ring */\n while (true) {\n prevEvent = event\n event = nextEvent\n events.push(event)\n\n /* Is the ring complete? */\n if (event.point === startingPoint) break\n\n while (true) {\n const availableLEs = event.getAvailableLinkedEvents()\n\n /* Did we hit a dead end? This shouldn't happen. Indicates some earlier\n * part of the algorithm malfunctioned... please file a bug report. */\n if (availableLEs.length === 0) {\n const firstPt = events[0].point\n const lastPt = events[events.length - 1].point\n throw new Error(\n `Unable to complete output ring starting at [${firstPt.x},` +\n ` ${firstPt.y}]. Last matching segment found ends at` +\n ` [${lastPt.x}, ${lastPt.y}].`,\n )\n }\n\n /* Only one way to go, so cotinue on the path */\n if (availableLEs.length === 1) {\n nextEvent = availableLEs[0].otherSE\n break\n }\n\n /* We must have an intersection. Check for a completed loop */\n let indexLE = null\n for (let j = 0, jMax = intersectionLEs.length; j < jMax; j++) {\n if (intersectionLEs[j].point === event.point) {\n indexLE = j\n break\n }\n }\n /* Found a completed loop. Cut that off and make a ring */\n if (indexLE !== null) {\n const intersectionLE = intersectionLEs.splice(indexLE)[0]\n const ringEvents = events.splice(intersectionLE.index)\n ringEvents.unshift(ringEvents[0].otherSE)\n ringsOut.push(new RingOut(ringEvents.reverse()))\n continue\n }\n /* register the intersection */\n intersectionLEs.push({\n index: events.length,\n point: event.point,\n })\n /* Choose the left-most option to continue the walk */\n const comparator = event.getLeftmostComparator(prevEvent)\n nextEvent = availableLEs.sort(comparator)[0].otherSE\n break\n }\n }\n\n ringsOut.push(new RingOut(events))\n }\n return ringsOut\n }\n\n constructor(events: SweepEvent[]) {\n this.events = events\n for (let i = 0, iMax = events.length; i < iMax; i++) {\n events[i].segment.ringOut = this\n }\n this.poly = null\n }\n\n getGeom() {\n // Remove superfluous points (ie extra points along a straight line),\n let prevPt = this.events[0].point\n const points = [prevPt]\n for (let i = 1, iMax = this.events.length - 1; i < iMax; i++) {\n const pt = this.events[i].point\n const nextPt = this.events[i + 1].point\n if (precision.orient(pt, prevPt, nextPt) === 0) continue\n points.push(pt)\n prevPt = pt\n }\n\n // ring was all (within rounding error of angle calc) colinear points\n if (points.length === 1) return null\n\n // check if the starting point is necessary\n const pt = points[0]\n const nextPt = points[1]\n if (precision.orient(pt, prevPt, nextPt) === 0) points.shift()\n\n points.push(points[0])\n const step = this.isExteriorRing() ? 1 : -1\n const iStart = this.isExteriorRing() ? 0 : points.length - 1\n const iEnd = this.isExteriorRing() ? points.length : -1\n const orderedPoints: Ring = []\n for (let i = iStart; i != iEnd; i += step)\n orderedPoints.push([points[i].x.toNumber(), points[i].y.toNumber()])\n return orderedPoints\n }\n\n isExteriorRing(): boolean {\n if (this._isExteriorRing === undefined) {\n const enclosing = this.enclosingRing()\n this._isExteriorRing = enclosing ? !enclosing.isExteriorRing() : true\n }\n return this._isExteriorRing\n }\n\n enclosingRing() {\n if (this._enclosingRing === undefined) {\n this._enclosingRing = this._calcEnclosingRing()\n }\n return this._enclosingRing\n }\n\n /* Returns the ring that encloses this one, if any */\n _calcEnclosingRing(): RingOut | null | undefined {\n // start with the ealier sweep line event so that the prevSeg\n // chain doesn't lead us inside of a loop of ours\n let leftMostEvt = this.events[0]\n for (let i = 1, iMax = this.events.length; i < iMax; i++) {\n const evt = this.events[i]\n if (SweepEvent.compare(leftMostEvt, evt) > 0) leftMostEvt = evt\n }\n\n let prevSeg: Segment | null | undefined = leftMostEvt.segment.prevInResult()\n let prevPrevSeg: Segment | null | undefined = prevSeg ? prevSeg.prevInResult() : null\n\n while (true) {\n // no segment found, thus no ring can enclose us\n if (!prevSeg) return null\n\n // no segments below prev segment found, thus the ring of the prev\n // segment must loop back around and enclose us\n if (!prevPrevSeg) return prevSeg.ringOut\n\n // if the two segments are of different rings, the ring of the prev\n // segment must either loop around us or the ring of the prev prev\n // seg, which would make us and the ring of the prev peers\n if (prevPrevSeg.ringOut !== prevSeg.ringOut) {\n if (prevPrevSeg.ringOut?.enclosingRing() !== prevSeg.ringOut) {\n return prevSeg.ringOut\n } else return prevSeg.ringOut?.enclosingRing()\n }\n\n // two segments are from the same ring, so this was a penisula\n // of that ring. iterate downward, keep searching\n prevSeg = prevPrevSeg.prevInResult()\n prevPrevSeg = prevSeg ? prevSeg.prevInResult() : null\n }\n }\n}\n\nexport class PolyOut {\n exteriorRing: RingOut;\n interiorRings: RingOut[];\n\n constructor(exteriorRing: RingOut) {\n this.exteriorRing = exteriorRing\n exteriorRing.poly = this\n this.interiorRings = []\n }\n\n addInterior(ring: RingOut) {\n this.interiorRings.push(ring)\n ring.poly = this\n }\n\n getGeom() {\n const geom0 = this.exteriorRing.getGeom()\n // exterior ring was all (within rounding error of angle calc) colinear points\n if (geom0 === null) return null\n const geom: Poly = [geom0];\n for (let i = 0, iMax = this.interiorRings.length; i < iMax; i++) {\n const ringGeom = this.interiorRings[i].getGeom()\n // interior ring was all (within rounding error of angle calc) colinear points\n if (ringGeom === null) continue\n geom.push(ringGeom)\n }\n return geom\n }\n}\n\nexport class MultiPolyOut {\n rings: RingOut[];\n polys: PolyOut[];\n\n constructor(rings: RingOut[]) {\n this.rings = rings\n this.polys = this._composePolys(rings)\n }\n\n getGeom() {\n const geom: MultiPoly = []\n for (let i = 0, iMax = this.polys.length; i < iMax; i++) {\n const polyGeom = this.polys[i].getGeom()\n // exterior ring was all (within rounding error of angle calc) colinear points\n if (polyGeom === null) continue\n geom.push(polyGeom)\n }\n return geom\n }\n\n _composePolys(rings: RingOut[]) {\n const polys = []\n for (let i = 0, iMax = rings.length; i < iMax; i++) {\n const ring = rings[i]\n if (ring.poly) continue\n if (ring.isExteriorRing()) polys.push(new PolyOut(ring))\n else {\n const enclosingRing = ring.enclosingRing()\n if (!enclosingRing?.poly) polys.push(new PolyOut(enclosingRing!))\n enclosingRing?.poly?.addInterior(ring)\n }\n }\n return polys\n }\n}\n","import { SplayTreeSet } from \"splaytree-ts\"\nimport Segment from \"./segment.js\"\nimport SweepEvent, { Point } from \"./sweep-event.js\"\n\n/**\n * NOTE: We must be careful not to change any segments while\n * they are in the SplayTree. AFAIK, there's no way to tell\n * the tree to rebalance itself - thus before splitting\n * a segment that's in the tree, we remove it from the tree,\n * do the split, then re-insert it. (Even though splitting a\n * segment *shouldn't* change its correct position in the\n * sweep line tree, the reality is because of rounding errors,\n * it sometimes does.)\n */\n\nexport default class SweepLine {\n private queue: SplayTreeSet\n private tree: SplayTreeSet\n segments: Segment[]\n\n constructor(queue: SplayTreeSet, comparator = Segment.compare) {\n this.queue = queue\n this.tree = new SplayTreeSet(comparator)\n this.segments = []\n }\n\n process(event: SweepEvent) {\n const segment = event.segment\n const newEvents: SweepEvent[] = []\n\n // if we've already been consumed by another segment,\n // clean up our body parts and get out\n if (event.consumedBy) {\n if (event.isLeft) this.queue.delete(event.otherSE)\n else this.tree.delete(segment)\n return newEvents\n }\n\n if (event.isLeft) this.tree.add(segment);\n\n let prevSeg: Segment | null = segment\n let nextSeg: Segment | null = segment\n\n // skip consumed segments still in tree\n do {\n prevSeg = this.tree.lastBefore(prevSeg)\n } while (prevSeg != null && prevSeg.consumedBy != undefined)\n\n // skip consumed segments still in tree\n do {\n nextSeg = this.tree.firstAfter(nextSeg)\n } while (nextSeg != null && nextSeg.consumedBy != undefined)\n\n if (event.isLeft) {\n // Check for intersections against the previous segment in the sweep line\n let prevMySplitter = null\n if (prevSeg) {\n const prevInter = prevSeg.getIntersection(segment)\n if (prevInter !== null) {\n if (!segment.isAnEndpoint(prevInter)) prevMySplitter = prevInter\n if (!prevSeg.isAnEndpoint(prevInter)) {\n const newEventsFromSplit = this._splitSafely(prevSeg, prevInter)\n for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n newEvents.push(newEventsFromSplit[i])\n }\n }\n }\n }\n\n // Check for intersections against the next segment in the sweep line\n let nextMySplitter = null\n if (nextSeg) {\n const nextInter = nextSeg.getIntersection(segment)\n if (nextInter !== null) {\n if (!segment.isAnEndpoint(nextInter)) nextMySplitter = nextInter\n if (!nextSeg.isAnEndpoint(nextInter)) {\n const newEventsFromSplit = this._splitSafely(nextSeg, nextInter)\n for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n newEvents.push(newEventsFromSplit[i])\n }\n }\n }\n }\n\n // For simplicity, even if we find more than one intersection we only\n // spilt on the 'earliest' (sweep-line style) of the intersections.\n // The other intersection will be handled in a future process().\n if (prevMySplitter !== null || nextMySplitter !== null) {\n let mySplitter = null\n if (prevMySplitter === null) mySplitter = nextMySplitter\n else if (nextMySplitter === null) mySplitter = prevMySplitter\n else {\n const cmpSplitters = SweepEvent.comparePoints(\n prevMySplitter,\n nextMySplitter,\n )\n mySplitter = cmpSplitters <= 0 ? prevMySplitter : nextMySplitter\n }\n\n // Rounding errors can cause changes in ordering,\n // so remove afected segments and right sweep events before splitting\n this.queue.delete(segment.rightSE)\n newEvents.push(segment.rightSE)\n\n const newEventsFromSplit = segment.split(mySplitter!)\n for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n newEvents.push(newEventsFromSplit[i])\n }\n }\n\n if (newEvents.length > 0) {\n // We found some intersections, so re-do the current event to\n // make sure sweep line ordering is totally consistent for later\n // use with the segment 'prev' pointers\n this.tree.delete(segment)\n newEvents.push(event)\n } else {\n // done with left event\n this.segments.push(segment)\n segment.prev = prevSeg\n }\n } else {\n // event.isRight\n\n // since we're about to be removed from the sweep line, check for\n // intersections between our previous and next segments\n if (prevSeg && nextSeg) {\n const inter = prevSeg.getIntersection(nextSeg)\n if (inter !== null) {\n if (!prevSeg.isAnEndpoint(inter)) {\n const newEventsFromSplit = this._splitSafely(prevSeg, inter)\n for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n newEvents.push(newEventsFromSplit[i])\n }\n }\n if (!nextSeg.isAnEndpoint(inter)) {\n const newEventsFromSplit = this._splitSafely(nextSeg, inter)\n for (let i = 0, iMax = newEventsFromSplit.length; i < iMax; i++) {\n newEvents.push(newEventsFromSplit[i])\n }\n }\n }\n }\n\n this.tree.delete(segment)\n }\n\n return newEvents\n }\n\n /* Safely split a segment that is currently in the datastructures\n * IE - a segment other than the one that is currently being processed. */\n _splitSafely(seg: Segment, pt: Point) {\n // Rounding errors can cause changes in ordering,\n // so remove afected segments and right sweep events before splitting\n // removeNode() doesn't work, so have re-find the seg\n // https://github.com/w8r/splay-tree/pull/5\n this.tree.delete(seg)\n const rightSE = seg.rightSE\n this.queue.delete(rightSE)\n const newEvents = seg.split(pt)\n newEvents.push(rightSE)\n // splitting can trigger consumption\n if (seg.consumedBy === undefined) this.tree.add(seg)\n return newEvents\n }\n}\n","import { getBboxOverlap, isInBbox } from \"./bbox.js\"\nimport { MultiPolyIn, RingIn } from \"./geom-in.js\"\nimport { RingOut } from \"./geom-out.js\"\nimport operation from \"./operation.js\"\nimport { precision } from \"./precision.js\"\nimport SweepEvent, { Point } from \"./sweep-event.js\"\nimport { intersection } from \"./vector.js\"\n\ninterface State {\n rings: RingIn[],\n windings: number[],\n multiPolys: MultiPolyIn[]\n}\n\n// Give segments unique ID's to get consistent sorting of\n// segments and sweep events when all else is identical\nlet segmentId = 0\n\nexport default class Segment {\n id: number\n leftSE: SweepEvent\n rightSE: SweepEvent\n rings: RingIn[] | null\n windings: number[] | null\n ringOut: RingOut | undefined\n consumedBy: Segment | undefined\n prev: Segment | null | undefined\n _prevInResult: Segment | null | undefined\n _beforeState: State | undefined\n _afterState: State | undefined\n _isInResult: boolean | undefined\n\n /* This compare() function is for ordering segments in the sweep\n * line tree, and does so according to the following criteria:\n *\n * Consider the vertical line that lies an infinestimal step to the\n * right of the right-more of the two left endpoints of the input\n * segments. Imagine slowly moving a point up from negative infinity\n * in the increasing y direction. Which of the two segments will that\n * point intersect first? That segment comes 'before' the other one.\n *\n * If neither segment would be intersected by such a line, (if one\n * or more of the segments are vertical) then the line to be considered\n * is directly on the right-more of the two left inputs.\n */\n static compare(a: Segment, b: Segment) {\n const alx = a.leftSE.point.x\n const blx = b.leftSE.point.x\n const arx = a.rightSE.point.x\n const brx = b.rightSE.point.x\n\n // check if they're even in the same vertical plane\n if (brx.isLessThan(alx)) return 1\n if (arx.isLessThan(blx)) return -1\n\n const aly = a.leftSE.point.y\n const bly = b.leftSE.point.y\n const ary = a.rightSE.point.y\n const bry = b.rightSE.point.y\n\n // is left endpoint of segment B the right-more?\n if (alx.isLessThan(blx)) {\n // are the two segments in the same horizontal plane?\n if (bly.isLessThan(aly) && bly.isLessThan(ary)) return 1\n if (bly.isGreaterThan(aly) && bly.isGreaterThan(ary)) return -1\n\n // is the B left endpoint colinear to segment A?\n const aCmpBLeft = a.comparePoint(b.leftSE.point)\n if (aCmpBLeft < 0) return 1\n if (aCmpBLeft > 0) return -1\n\n // is the A right endpoint colinear to segment B ?\n const bCmpARight = b.comparePoint(a.rightSE.point)\n if (bCmpARight !== 0) return bCmpARight\n\n // colinear segments, consider the one with left-more\n // left endpoint to be first (arbitrary?)\n return -1\n }\n\n // is left endpoint of segment A the right-more?\n if (alx.isGreaterThan(blx)) {\n if (aly.isLessThan(bly) && aly.isLessThan(bry)) return -1\n if (aly.isGreaterThan(bly) && aly.isGreaterThan(bry)) return 1\n\n // is the A left endpoint colinear to segment B?\n const bCmpALeft = b.comparePoint(a.leftSE.point)\n if (bCmpALeft !== 0) return bCmpALeft\n\n // is the B right endpoint colinear to segment A?\n const aCmpBRight = a.comparePoint(b.rightSE.point)\n if (aCmpBRight < 0) return 1\n if (aCmpBRight > 0) return -1\n\n // colinear segments, consider the one with left-more\n // left endpoint to be first (arbitrary?)\n return 1\n }\n\n // if we get here, the two left endpoints are in the same\n // vertical plane, ie alx === blx\n\n // consider the lower left-endpoint to come first\n if (aly.isLessThan(bly)) return -1\n if (aly.isGreaterThan(bly)) return 1\n\n // left endpoints are identical\n // check for colinearity by using the left-more right endpoint\n\n // is the A right endpoint more left-more?\n if (arx.isLessThan(brx)) {\n const bCmpARight = b.comparePoint(a.rightSE.point)\n if (bCmpARight !== 0) return bCmpARight\n }\n\n // is the B right endpoint more left-more?\n if (arx.isGreaterThan(brx)) {\n const aCmpBRight = a.comparePoint(b.rightSE.point)\n if (aCmpBRight < 0) return 1\n if (aCmpBRight > 0) return -1\n }\n\n if (!arx.eq(brx)) {\n // are these two [almost] vertical segments with opposite orientation?\n // if so, the one with the lower right endpoint comes first\n const ay = ary.minus(aly)\n const ax = arx.minus(alx)\n const by = bry.minus(bly)\n const bx = brx.minus(blx)\n if (ay.isGreaterThan(ax) && by.isLessThan(bx)) return 1\n if (ay.isLessThan(ax) && by.isGreaterThan(bx)) return -1\n }\n\n // we have colinear segments with matching orientation\n // consider the one with more left-more right endpoint to be first\n if (arx.isGreaterThan(brx)) return 1\n if (arx.isLessThan(brx)) return -1\n\n // if we get here, two two right endpoints are in the same\n // vertical plane, ie arx === brx\n\n // consider the lower right-endpoint to come first\n if (ary.isLessThan(bry)) return -1\n if (ary.isGreaterThan(bry)) return 1\n\n // right endpoints identical as well, so the segments are idential\n // fall back on creation order as consistent tie-breaker\n if (a.id < b.id) return -1\n if (a.id > b.id) return 1\n\n // identical segment, ie a === b\n return 0\n }\n\n /* Warning: a reference to ringWindings input will be stored,\n * and possibly will be later modified */\n constructor(leftSE: SweepEvent, rightSE: SweepEvent, rings: RingIn[], windings: number[]) {\n this.id = ++segmentId\n this.leftSE = leftSE\n leftSE.segment = this\n leftSE.otherSE = rightSE\n this.rightSE = rightSE\n rightSE.segment = this\n rightSE.otherSE = leftSE\n this.rings = rings\n this.windings = windings\n // left unset for performance, set later in algorithm\n // this.ringOut, this.consumedBy, this.prev\n }\n\n static fromRing(pt1: Point, pt2: Point, ring: RingIn) {\n let leftPt: Point, rightPt: Point, winding: number\n\n // ordering the two points according to sweep line ordering\n const cmpPts = SweepEvent.comparePoints(pt1, pt2)\n if (cmpPts < 0) {\n leftPt = pt1\n rightPt = pt2\n winding = 1\n } else if (cmpPts > 0) {\n leftPt = pt2\n rightPt = pt1\n winding = -1\n } else\n throw new Error(\n `Tried to create degenerate segment at [${pt1.x}, ${pt1.y}]`,\n )\n\n const leftSE = new SweepEvent(leftPt, true)\n const rightSE = new SweepEvent(rightPt, false)\n return new Segment(leftSE, rightSE, [ring], [winding])\n }\n\n /* When a segment is split, the rightSE is replaced with a new sweep event */\n replaceRightSE(newRightSE: SweepEvent) {\n this.rightSE = newRightSE\n this.rightSE.segment = this\n this.rightSE.otherSE = this.leftSE\n this.leftSE.otherSE = this.rightSE\n }\n\n bbox() {\n const y1 = this.leftSE.point.y\n const y2 = this.rightSE.point.y\n return {\n ll: { x: this.leftSE.point.x, y: y1.isLessThan(y2) ? y1 : y2 },\n ur: { x: this.rightSE.point.x, y: y1.isGreaterThan(y2) ? y1 : y2 },\n }\n }\n\n /* A vector from the left point to the right */\n vector() {\n return {\n x: this.rightSE.point.x.minus(this.leftSE.point.x),\n y: this.rightSE.point.y.minus(this.leftSE.point.y),\n }\n }\n\n isAnEndpoint(pt: Point) {\n return (\n (pt.x.eq(this.leftSE.point.x) && pt.y.eq(this.leftSE.point.y)) ||\n (pt.x.eq(this.rightSE.point.x) && pt.y.eq(this.rightSE.point.y))\n )\n }\n\n /* Compare this segment with a point.\n *\n * A point P is considered to be colinear to a segment if there\n * exists a distance D such that if we travel along the segment\n * from one * endpoint towards the other a distance D, we find\n * ourselves at point P.\n *\n * Return value indicates:\n *\n * 1: point lies above the segment (to the left of vertical)\n * 0: point is colinear to segment\n * -1: point lies below the segment (to the right of vertical)\n */\n comparePoint(point: Point) {\n return precision.orient(this.leftSE.point, point, this.rightSE.point)\n }\n\n /**\n * Given another segment, returns the first non-trivial intersection\n * between the two segments (in terms of sweep line ordering), if it exists.\n *\n * A 'non-trivial' intersection is one that will cause one or both of the\n * segments to be split(). As such, 'trivial' vs. 'non-trivial' intersection:\n *\n * * endpoint of segA with endpoint of segB --> trivial\n * * endpoint of segA with point along segB --> non-trivial\n * * endpoint of segB with point along segA --> non-trivial\n * * point along segA with point along segB --> non-trivial\n *\n * If no non-trivial intersection exists, return null\n * Else, return null.\n */\n getIntersection(other: Segment) {\n // If bboxes don't overlap, there can't be any intersections\n const tBbox = this.bbox()\n const oBbox = other.bbox()\n const bboxOverlap = getBboxOverlap(tBbox, oBbox)\n if (bboxOverlap === null) return null\n\n // We first check to see if the endpoints can be considered intersections.\n // This will 'snap' intersections to endpoints if possible, and will\n // handle cases of colinearity.\n\n const tlp = this.leftSE.point\n const trp = this.rightSE.point\n const olp = other.leftSE.point\n const orp = other.rightSE.point\n\n // does each endpoint touch the other segment?\n // note that we restrict the 'touching' definition to only allow segments\n // to touch endpoints that lie forward from where we are in the sweep line pass\n const touchesOtherLSE = isInBbox(tBbox, olp) && this.comparePoint(olp) === 0\n const touchesThisLSE = isInBbox(oBbox, tlp) && other.comparePoint(tlp) === 0\n const touchesOtherRSE = isInBbox(tBbox, orp) && this.comparePoint(orp) === 0\n const touchesThisRSE = isInBbox(oBbox, trp) && other.comparePoint(trp) === 0\n\n // do left endpoints match?\n if (touchesThisLSE && touchesOtherLSE) {\n // these two cases are for colinear segments with matching left\n // endpoints, and one segment being longer than the other\n if (touchesThisRSE && !touchesOtherRSE) return trp\n if (!touchesThisRSE && touchesOtherRSE) return orp\n // either the two segments match exactly (two trival intersections)\n // or just on their left endpoint (one trivial intersection\n return null\n }\n\n // does this left endpoint matches (other doesn't)\n if (touchesThisLSE) {\n // check for segments that just intersect on opposing endpoints\n if (touchesOtherRSE) {\n if (tlp.x.eq(orp.x) && tlp.y.eq(orp.y)) return null\n }\n // t-intersection on left endpoint\n return tlp\n }\n\n // does other left endpoint matches (this doesn't)\n if (touchesOtherLSE) {\n // check for segments that just intersect on opposing endpoints\n if (touchesThisRSE) {\n if (trp.x.eq(olp.x) && trp.y.eq(olp.y)) return null\n }\n // t-intersection on left endpoint\n return olp\n }\n\n // trivial intersection on right endpoints\n if (touchesThisRSE && touchesOtherRSE) return null\n\n // t-intersections on just one right endpoint\n if (touchesThisRSE) return trp\n if (touchesOtherRSE) return orp\n\n // None of our endpoints intersect. Look for a general intersection between\n // infinite lines laid over the segments\n const pt = intersection(tlp, this.vector(), olp, other.vector())\n\n // are the segments parrallel? Note that if they were colinear with overlap,\n // they would have an endpoint intersection and that case was already handled above\n if (pt === null) return null\n\n // is the intersection found between the lines not on the segments?\n if (!isInBbox(bboxOverlap, pt)) return null\n\n // round the the computed point if needed\n return precision.snap(pt) as Point\n }\n\n /**\n * Split the given segment into multiple segments on the given points.\n * * Each existing segment will retain its leftSE and a new rightSE will be\n * generated for it.\n * * A new segment will be generated which will adopt the original segment's\n * rightSE, and a new leftSE will be generated for it.\n * * If there are more than two points given to split on, new segments\n * in the middle will be generated with new leftSE and rightSE's.\n * * An array of the newly generated SweepEvents will be returned.\n *\n * Warning: input array of points is modified\n */\n split(point: Point) {\n const newEvents = []\n const alreadyLinked = point.events !== undefined\n\n const newLeftSE = new SweepEvent(point, true)\n const newRightSE = new SweepEvent(point, false)\n const oldRightSE = this.rightSE\n this.replaceRightSE(newRightSE)\n newEvents.push(newRightSE)\n newEvents.push(newLeftSE)\n const newSeg = new Segment(\n newLeftSE,\n oldRightSE,\n this.rings!.slice(),\n this.windings!.slice(),\n )\n\n // when splitting a nearly vertical downward-facing segment,\n // sometimes one of the resulting new segments is vertical, in which\n // case its left and right events may need to be swapped\n if (\n SweepEvent.comparePoints(newSeg.leftSE.point, newSeg.rightSE.point) > 0\n ) {\n newSeg.swapEvents()\n }\n if (SweepEvent.comparePoints(this.leftSE.point, this.rightSE.point) > 0) {\n this.swapEvents()\n }\n\n // in the point we just used to create new sweep events with was already\n // linked to other events, we need to check if either of the affected\n // segments should be consumed\n if (alreadyLinked) {\n newLeftSE.checkForConsuming()\n newRightSE.checkForConsuming()\n }\n\n return newEvents\n }\n\n /* Swap which event is left and right */\n swapEvents() {\n const tmpEvt = this.rightSE\n this.rightSE = this.leftSE\n this.leftSE = tmpEvt\n this.leftSE.isLeft = true\n this.rightSE.isLeft = false\n for (let i = 0, iMax = this.windings!.length; i < iMax; i++) {\n this.windings![i] *= -1\n }\n }\n\n /* Consume another segment. We take their rings under our wing\n * and mark them as consumed. Use for perfectly overlapping segments */\n consume(other: Segment) {\n let consumer = this as Segment\n let consumee = other\n while (consumer.consumedBy) consumer = consumer.consumedBy\n while (consumee.consumedBy) consumee = consumee.consumedBy\n\n const cmp = Segment.compare(consumer, consumee)\n if (cmp === 0) return // already consumed\n // the winner of the consumption is the earlier segment\n // according to sweep line ordering\n if (cmp > 0) {\n const tmp = consumer\n consumer = consumee\n consumee = tmp\n }\n\n // make sure a segment doesn't consume it's prev\n if (consumer.prev === consumee) {\n const tmp = consumer\n consumer = consumee\n consumee = tmp\n }\n\n for (let i = 0, iMax = consumee.rings!.length; i < iMax; i++) {\n const ring = consumee.rings![i]\n const winding = consumee.windings![i]\n const index = consumer.rings!.indexOf(ring)\n if (index === -1) {\n consumer.rings!.push(ring)\n consumer.windings!.push(winding)\n } else consumer.windings![index] += winding\n }\n consumee.rings = null\n consumee.windings = null\n consumee.consumedBy = consumer\n\n // mark sweep events consumed as to maintain ordering in sweep event queue\n consumee.leftSE.consumedBy = consumer.leftSE\n consumee.rightSE.consumedBy = consumer.rightSE\n }\n\n /* The first segment previous segment chain that is in the result */\n prevInResult(): Segment | null | undefined {\n if (this._prevInResult !== undefined) return this._prevInResult\n if (!this.prev) this._prevInResult = null\n else if (this.prev.isInResult()) this._prevInResult = this.prev\n else this._prevInResult = this.prev.prevInResult()\n return this._prevInResult\n }\n\n beforeState(): State {\n if (this._beforeState !== undefined) return this._beforeState\n if (!this.prev)\n this._beforeState = {\n rings: [],\n windings: [],\n multiPolys: [],\n }\n else {\n const seg = this.prev.consumedBy || this.prev\n this._beforeState = seg.afterState()\n }\n return this._beforeState\n }\n\n afterState() {\n if (this._afterState !== undefined) return this._afterState\n\n const beforeState = this.beforeState()\n this._afterState = {\n rings: beforeState.rings.slice(0),\n windings: beforeState.windings.slice(0),\n multiPolys: [],\n }\n const ringsAfter = this._afterState.rings\n const windingsAfter = this._afterState.windings\n const mpsAfter = this._afterState.multiPolys\n\n // calculate ringsAfter, windingsAfter\n for (let i = 0, iMax = this.rings!.length; i < iMax; i++) {\n const ring = this.rings![i]\n const winding = this.windings![i]\n const index = ringsAfter.indexOf(ring)\n if (index === -1) {\n ringsAfter.push(ring)\n windingsAfter.push(winding)\n } else windingsAfter[index] += winding\n }\n\n // calcualte polysAfter\n const polysAfter = []\n const polysExclude = []\n for (let i = 0, iMax = ringsAfter.length; i < iMax; i++) {\n if (windingsAfter[i] === 0) continue // non-zero rule\n const ring = ringsAfter[i]\n const poly = ring.poly\n if (polysExclude.indexOf(poly) !== -1) continue\n if (ring.isExterior) polysAfter.push(poly)\n else {\n if (polysExclude.indexOf(poly) === -1) polysExclude.push(poly)\n const index = polysAfter.indexOf(ring.poly)\n if (index !== -1) polysAfter.splice(index, 1)\n }\n }\n\n // calculate multiPolysAfter\n for (let i = 0, iMax = polysAfter.length; i < iMax; i++) {\n const mp = polysAfter[i].multiPoly\n if (mpsAfter.indexOf(mp) === -1) mpsAfter.push(mp)\n }\n\n return this._afterState\n }\n\n /* Is this segment part of the final result? */\n isInResult() {\n // if we've been consumed, we're not in the result\n if (this.consumedBy) return false\n\n if (this._isInResult !== undefined) return this._isInResult\n\n const mpsBefore = this.beforeState().multiPolys\n const mpsAfter = this.afterState().multiPolys\n\n switch (operation.type) {\n case \"union\": {\n // UNION - included iff:\n // * On one side of us there is 0 poly interiors AND\n // * On the other side there is 1 or more.\n const noBefores = mpsBefore.length === 0\n const noAfters = mpsAfter.length === 0\n this._isInResult = noBefores !== noAfters\n break\n }\n\n case \"intersection\": {\n // INTERSECTION - included iff:\n // * on one side of us all multipolys are rep. with poly interiors AND\n // * on the other side of us, not all multipolys are repsented\n // with poly interiors\n let least\n let most\n if (mpsBefore.length < mpsAfter.length) {\n least = mpsBefore.length\n most = mpsAfter.length\n } else {\n least = mpsAfter.length\n most = mpsBefore.length\n }\n this._isInResult = most === operation.numMultiPolys && least < most\n break\n }\n\n case \"xor\": {\n // XOR - included iff:\n // * the difference between the number of multipolys represented\n // with poly interiors on our two sides is an odd number\n const diff = Math.abs(mpsBefore.length - mpsAfter.length)\n this._isInResult = diff % 2 === 1\n break\n }\n\n case \"difference\": {\n // DIFFERENCE included iff:\n // * on exactly one side, we have just the subject\n const isJustSubject = (mps: MultiPolyIn[]) => mps.length === 1 && mps[0].isSubject\n this._isInResult = isJustSubject(mpsBefore) !== isJustSubject(mpsAfter)\n break\n }\n }\n\n return this._isInResult\n }\n}\n","import { Geom } from \"./geom-in.js\"\nimport { precision } from \"./precision.js\"\nimport operation from \"./operation.js\"\n\nexport { Geom }\n\nexport const union = (geom: Geom, ...moreGeoms: Geom[]) =>\n operation.run(\"union\", geom, moreGeoms)\n\nexport const intersection = (geom: Geom, ...moreGeoms: Geom[]) =>\n operation.run(\"intersection\", geom, moreGeoms)\n\nexport const xor = (geom: Geom, ...moreGeoms: Geom[]) =>\n operation.run(\"xor\", geom, moreGeoms)\n\nexport const difference = (geom: Geom, ...moreGeoms: Geom[]) =>\n operation.run(\"difference\", geom, moreGeoms)\n\nexport const setPrecision = precision.set"],"mappings":";AAAA,OAAOA,gBAAe;;;ACAtB,IAAO,mBAAQ,CAAI,MAAS;AACxB,SAAO,MAAM;AACT,WAAO;AAAA,EACX;AACJ;;;ACDA,IAAO,kBAAQ,CAAC,QAAiB;AAC7B,QAAM,cAAc,MAAM,CAAC,GAAc,MACrC,EAAE,MAAM,CAAC,EAAE,IAAI,EAAE,oBAAoB,GAAG,IACtC,iBAAS,KAAK;AAEpB,SAAO,CAAC,GAAc,MAAiB;AACnC,QAAI,YAAY,GAAG,CAAC,EAAG,QAAO;AAE9B,WAAO,EAAE,WAAW,CAAC;AAAA,EACzB;AACJ;;;ACTe,SAAR,eAAkB,KAAc;AACnC,QAAM,kBAAkB,MAAM,CAAC,OAAkB,IAAe,IAAe,IAAe,OAC1F,MAAM,gBAAgB,CAAC,EAAE;AAAA,IACrB,GAAG,MAAM,EAAE,EAAE,gBAAgB,CAAC,EAAE,KAAK,GAAG,MAAM,EAAE,EAAE,gBAAgB,CAAC,CAAC,EAC/D,MAAM,GAAG;AAAA,EAAC,IACjB,iBAAS,KAAK;AAEpB,SAAO,CAAC,GAAW,GAAW,MAAc;AACxC,UAAM,KAAK,EAAE,GAAG,KAAK,EAAE,GAAG,KAAK,EAAE,GAAG,KAAK,EAAE;AAE3C,UAAM,QAAQ,GAAG,MAAM,EAAE,EAAE,MAAM,EAAE,EAAE,MAAM,EAAE,CAAC,EAAE,MAAM,GAAG,MAAM,EAAE,EAAE,MAAM,EAAE,EAAE,MAAM,EAAE,CAAC,CAAC;AAEvF,QAAI,gBAAgB,OAAO,IAAI,IAAI,IAAI,EAAE,EAAG,QAAO;AAEnD,WAAO,MAAM,WAAW,CAAC;AAAA,EAC7B;AACJ;;;ACpBA,OAAO,eAAe;AACtB,SAAS,oBAAoB;;;ACD7B,IAAO,mBAAQ,CAAI,MAAS;AACxB,SAAO;AACX;;;ADIA,IAAO,eAAQ,CAAC,QAAiB;AAC/B,MAAI,KAAK;AAEP,UAAM,QAAQ,IAAI,aAAa,gBAAQ,GAAG,CAAC;AAC3C,UAAM,QAAQ,IAAI,aAAa,gBAAQ,GAAG,CAAC;AAE3C,UAAM,YAAY,CAAC,OAAkB,SAAkC;AACrE,aAAO,KAAK,aAAa,KAAK;AAAA,IAChC;AAEA,UAAM,OAAO,CAAC,MAAc;AAC1B,aAAO;AAAA,QACL,GAAG,UAAU,EAAE,GAAG,KAAK;AAAA,QACvB,GAAG,UAAU,EAAE,GAAG,KAAK;AAAA,MACzB;AAAA,IACF;AAEA,SAAK,EAAE,GAAG,IAAI,UAAU,CAAC,GAAG,GAAG,IAAI,UAAU,CAAC,EAAC,CAAC;AAEhD,WAAO;AAAA,EACT;AAEA,SAAO;AACT;;;AEzBA,IAAM,MAAM,CAAC,QAAiB;AAC1B,SAAO;AAAA,IACH,KAAK,CAACC,SAAiB;AAAE,kBAAY,IAAIA,IAAG;AAAA,IAAE;AAAA,IAC9C,OAAO,MAAM,IAAI,GAAG;AAAA,IACpB,SAAS,gBAAQ,GAAG;AAAA,IACpB,MAAM,aAAK,GAAG;AAAA,IACd,QAAQ,eAAO,GAAG;AAAA,EACtB;AACJ;AAEO,IAAI,YAAoC,IAAI;;;ACA5C,IAAM,WAAW,CAAC,MAAY,UAAkB;AACrD,SACE,KAAK,GAAG,EAAE,oBAAoB,MAAM,CAAC,KACrC,MAAM,EAAE,oBAAoB,KAAK,GAAG,CAAC,KACrC,KAAK,GAAG,EAAE,oBAAoB,MAAM,CAAC,KACrC,MAAM,EAAE,oBAAoB,KAAK,GAAG,CAAC;AAEzC;AAKO,IAAM,iBAAiB,CAAC,IAAU,OAAa;AAEpD,MACE,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,KAC1B,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,KAC1B,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,KAC1B,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC;AAE1B,WAAO;AAGT,QAAM,SAAS,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,IAAI,GAAG,GAAG,IAAI,GAAG,GAAG;AAC7D,QAAM,SAAS,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,IAAI,GAAG,GAAG,IAAI,GAAG,GAAG;AAG7D,QAAM,SAAS,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,IAAI,GAAG,GAAG,IAAI,GAAG,GAAG;AAC7D,QAAM,SAAS,GAAG,GAAG,EAAE,WAAW,GAAG,GAAG,CAAC,IAAI,GAAG,GAAG,IAAI,GAAG,GAAG;AAG7D,SAAO,EAAE,IAAI,EAAE,GAAG,QAAQ,GAAG,OAAO,GAAG,IAAI,EAAE,GAAG,QAAQ,GAAG,OAAO,EAAE;AACtE;;;AC9CA,SAAS,gBAAAC,qBAAoB;;;ACQtB,IAAM,eAAe,CAAC,GAAW,MAAc,EAAE,EAAE,MAAM,EAAE,CAAC,EAAE,MAAM,EAAE,EAAE,MAAM,EAAE,CAAC,CAAC;AAGlF,IAAM,aAAa,CAAC,GAAW,MAAc,EAAE,EAAE,MAAM,EAAE,CAAC,EAAE,KAAK,EAAE,EAAE,MAAM,EAAE,CAAC,CAAC;AAE/E,IAAM,SAAS,CAAC,MAAc,WAAW,GAAG,CAAC,EAAE,KAAK;AAGpD,IAAM,cAAc,CAAC,SAAiB,OAAe,WAAmB;AAC7E,QAAM,QAAQ,EAAE,GAAG,MAAM,EAAE,MAAM,QAAQ,CAAC,GAAG,GAAG,MAAM,EAAE,MAAM,QAAQ,CAAC,EAAE;AACzE,QAAM,SAAS,EAAE,GAAG,OAAO,EAAE,MAAM,QAAQ,CAAC,GAAG,GAAG,OAAO,EAAE,MAAM,QAAQ,CAAC,EAAE;AAC5E,SAAO,aAAa,QAAQ,KAAK,EAAE,IAAI,OAAO,MAAM,CAAC,EAAE,IAAI,OAAO,KAAK,CAAC;AAC1E;AAGO,IAAM,gBAAgB,CAAC,SAAiB,OAAe,WAAmB;AAC/E,QAAM,QAAQ,EAAE,GAAG,MAAM,EAAE,MAAM,QAAQ,CAAC,GAAG,GAAG,MAAM,EAAE,MAAM,QAAQ,CAAC,EAAE;AACzE,QAAM,SAAS,EAAE,GAAG,OAAO,EAAE,MAAM,QAAQ,CAAC,GAAG,GAAG,OAAO,EAAE,MAAM,QAAQ,CAAC,EAAE;AAC5E,SAAO,WAAW,QAAQ,KAAK,EAAE,IAAI,OAAO,MAAM,CAAC,EAAE,IAAI,OAAO,KAAK,CAAC;AACxE;AAKO,IAAM,yBAAyB,CAAC,IAAY,GAAW,MAAoB;AAChF,MAAI,EAAE,EAAE,OAAO,EAAG,QAAO;AACzB,SAAO,EAAE,GAAG,GAAG,EAAE,KAAM,EAAE,EAAE,IAAI,EAAE,CAAC,EAAG,MAAM,EAAE,MAAM,GAAG,CAAC,CAAC,CAAC,GAAG,EAAK;AACnE;AAKO,IAAM,uBAAuB,CAAC,IAAY,GAAW,MAAoB;AAC9E,MAAI,EAAE,EAAE,OAAO,EAAG,QAAO;AACzB,SAAO,EAAE,GAAM,GAAG,GAAG,EAAE,KAAM,EAAE,EAAE,IAAI,EAAE,CAAC,EAAG,MAAM,EAAE,MAAM,GAAG,CAAC,CAAC,CAAC,EAAE;AACnE;AAIO,IAAM,eAAe,CAAC,KAAa,IAAY,KAAa,OAAe;AAIhF,MAAI,GAAG,EAAE,OAAO,EAAG,QAAO,qBAAqB,KAAK,IAAI,IAAI,CAAC;AAC7D,MAAI,GAAG,EAAE,OAAO,EAAG,QAAO,qBAAqB,KAAK,IAAI,IAAI,CAAC;AAC7D,MAAI,GAAG,EAAE,OAAO,EAAG,QAAO,uBAAuB,KAAK,IAAI,IAAI,CAAC;AAC/D,MAAI,GAAG,EAAE,OAAO,EAAG,QAAO,uBAAuB,KAAK,IAAI,IAAI,CAAC;AAM/D,QAAM,QAAQ,aAAa,IAAI,EAAE;AACjC,MAAI,MAAM,OAAO,EAAG,QAAO;AAE3B,QAAM,KAAK,EAAE,GAAG,IAAI,EAAE,MAAM,IAAI,CAAC,GAAG,GAAG,IAAI,EAAE,MAAM,IAAI,CAAC,EAAE;AAC1D,QAAM,KAAK,aAAa,IAAI,EAAE,EAAE,IAAI,KAAK;AACzC,QAAM,KAAK,aAAa,IAAI,EAAE,EAAE,IAAI,KAAK;AAGzC,QAAM,KAAK,IAAI,EAAE,KAAK,GAAG,MAAM,GAAG,CAAC,CAAC,GAClC,KAAK,IAAI,EAAE,KAAK,GAAG,MAAM,GAAG,CAAC,CAAC;AAChC,QAAM,KAAK,IAAI,EAAE,KAAK,GAAG,MAAM,GAAG,CAAC,CAAC,GAClC,KAAK,IAAI,EAAE,KAAK,GAAG,MAAM,GAAG,CAAC,CAAC;AAChC,QAAM,IAAI,GAAG,KAAK,EAAE,EAAE,IAAI,CAAC;AAC3B,QAAM,IAAI,GAAG,KAAK,EAAE,EAAE,IAAI,CAAC;AAC3B,SAAO,EAAE,GAAM,EAAK;AACtB;;;ACnEA,IAAqB,aAArB,MAAqB,YAAW;AAAA,EAC9B;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA;AAAA,EAGA,OAAO,QAAQ,GAAe,GAAe;AAE3C,UAAM,QAAQ,YAAW,cAAc,EAAE,OAAO,EAAE,KAAK;AACvD,QAAI,UAAU,EAAG,QAAO;AAGxB,QAAI,EAAE,UAAU,EAAE,MAAO,GAAE,KAAK,CAAC;AAGjC,QAAI,EAAE,WAAW,EAAE,OAAQ,QAAO,EAAE,SAAS,IAAI;AAIjD,WAAO,QAAQ,QAAQ,EAAE,SAAS,EAAE,OAAO;AAAA,EAC7C;AAAA;AAAA,EAGA,OAAO,cAAc,KAAY,KAAY;AAC3C,QAAI,IAAI,EAAE,WAAW,IAAI,CAAC,EAAG,QAAO;AACpC,QAAI,IAAI,EAAE,cAAc,IAAI,CAAC,EAAG,QAAO;AAEvC,QAAI,IAAI,EAAE,WAAW,IAAI,CAAC,EAAG,QAAO;AACpC,QAAI,IAAI,EAAE,cAAc,IAAI,CAAC,EAAG,QAAO;AAEvC,WAAO;AAAA,EACT;AAAA;AAAA,EAGA,YAAY,OAAc,QAAiB;AACzC,QAAI,MAAM,WAAW,OAAW,OAAM,SAAS,CAAC,IAAI;AAAA,QAC/C,OAAM,OAAO,KAAK,IAAI;AAC3B,SAAK,QAAQ;AACb,SAAK,SAAS;AAAA,EAEhB;AAAA,EAEA,KAAK,OAAmB;AACtB,QAAI,MAAM,UAAU,KAAK,OAAO;AAC9B,YAAM,IAAI,MAAM,qCAAqC;AAAA,IACvD;AACA,UAAM,cAAc,MAAM,MAAM;AAChC,aAAS,IAAI,GAAG,OAAO,YAAY,QAAQ,IAAI,MAAM,KAAK;AACxD,YAAM,MAAM,YAAY,CAAC;AACzB,WAAK,MAAM,OAAO,KAAK,GAAG;AAC1B,UAAI,QAAQ,KAAK;AAAA,IACnB;AACA,SAAK,kBAAkB;AAAA,EACzB;AAAA;AAAA;AAAA,EAIA,oBAAoB;AAOlB,UAAM,YAAY,KAAK,MAAM,OAAO;AACpC,aAAS,IAAI,GAAG,IAAI,WAAW,KAAK;AAClC,YAAM,OAAO,KAAK,MAAM,OAAO,CAAC;AAChC,UAAI,KAAK,QAAQ,eAAe,OAAW;AAC3C,eAAS,IAAI,IAAI,GAAG,IAAI,WAAW,KAAK;AACtC,cAAM,OAAO,KAAK,MAAM,OAAO,CAAC;AAChC,YAAI,KAAK,eAAe,OAAW;AACnC,YAAI,KAAK,QAAQ,MAAM,WAAW,KAAK,QAAQ,MAAM,OAAQ;AAC7D,aAAK,QAAQ,QAAQ,KAAK,OAAO;AAAA,MACnC;AAAA,IACF;AAAA,EACF;AAAA,EAEA,2BAA2B;AAEzB,UAAM,SAAS,CAAC;AAChB,aAAS,IAAI,GAAG,OAAO,KAAK,MAAM,OAAO,QAAQ,IAAI,MAAM,KAAK;AAC9D,YAAM,MAAM,KAAK,MAAM,OAAO,CAAC;AAC/B,UAAI,QAAQ,QAAQ,CAAC,IAAI,QAAQ,WAAW,IAAI,QAAQ,WAAW,GAAG;AACpE,eAAO,KAAK,GAAG;AAAA,MACjB;AAAA,IACF;AACA,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,sBAAsB,WAAuB;AAC3C,UAAM,QAAQ,oBAAI,IAAwD;AAE1E,UAAM,YAAY,CAAC,gBAA4B;AAC7C,YAAM,YAAY,YAAY;AAC9B,YAAM,IAAI,aAAa;AAAA,QACrB,MAAM,YAAY,KAAK,OAAO,UAAU,OAAO,UAAU,KAAK;AAAA,QAC9D,QAAQ,cAAc,KAAK,OAAO,UAAU,OAAO,UAAU,KAAK;AAAA,MACpE,CAAC;AAAA,IACH;AAEA,WAAO,CAAC,GAAe,MAAkB;AACvC,UAAI,CAAC,MAAM,IAAI,CAAC,EAAG,WAAU,CAAC;AAC9B,UAAI,CAAC,MAAM,IAAI,CAAC,EAAG,WAAU,CAAC;AAE9B,YAAM,EAAE,MAAM,OAAO,QAAQ,QAAQ,IAAI,MAAM,IAAI,CAAC;AACpD,YAAM,EAAE,MAAM,OAAO,QAAQ,QAAQ,IAAI,MAAM,IAAI,CAAC;AAGpD,UAAI,MAAM,uBAAuB,CAAC,KAAK,MAAM,uBAAuB,CAAC,GAAG;AACtE,YAAI,QAAQ,WAAW,OAAO,EAAG,QAAO;AACxC,YAAI,QAAQ,cAAc,OAAO,EAAG,QAAO;AAC3C,eAAO;AAAA,MACT;AAGA,UAAI,MAAM,WAAW,CAAC,KAAK,MAAM,WAAW,CAAC,GAAG;AAC9C,YAAI,QAAQ,WAAW,OAAO,EAAG,QAAO;AACxC,YAAI,QAAQ,cAAc,OAAO,EAAG,QAAO;AAC3C,eAAO;AAAA,MACT;AAGA,UAAI,MAAM,WAAW,KAAK,EAAG,QAAO;AACpC,UAAI,MAAM,cAAc,KAAK,EAAG,QAAO;AACvC,aAAO;AAAA,IACT;AAAA,EACF;AACF;;;AC9IO,IAAM,UAAN,MAAM,SAAQ;AAAA,EACnB;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA;AAAA;AAAA,EAIA,OAAO,QAAQ,aAAwB;AACrC,UAAM,WAAW,CAAC;AAElB,aAAS,IAAI,GAAG,OAAO,YAAY,QAAQ,IAAI,MAAM,KAAK;AACxD,YAAM,UAAU,YAAY,CAAC;AAC7B,UAAI,CAAC,QAAQ,WAAW,KAAK,QAAQ,QAAS;AAE9C,UAAI,YAAY;AAChB,UAAI,QAAQ,QAAQ;AACpB,UAAI,YAAY,QAAQ;AACxB,YAAM,SAAS,CAAC,KAAK;AAErB,YAAM,gBAAgB,MAAM;AAC5B,YAAM,kBAAkB,CAAC;AAGzB,aAAO,MAAM;AACX,oBAAY;AACZ,gBAAQ;AACR,eAAO,KAAK,KAAK;AAGjB,YAAI,MAAM,UAAU,cAAe;AAEnC,eAAO,MAAM;AACX,gBAAM,eAAe,MAAM,yBAAyB;AAIpD,cAAI,aAAa,WAAW,GAAG;AAC7B,kBAAM,UAAU,OAAO,CAAC,EAAE;AAC1B,kBAAM,SAAS,OAAO,OAAO,SAAS,CAAC,EAAE;AACzC,kBAAM,IAAI;AAAA,cACR,+CAA+C,QAAQ,CAAC,KAClD,QAAQ,CAAC,2CACR,OAAO,CAAC,KAAK,OAAO,CAAC;AAAA,YAC9B;AAAA,UACF;AAGA,cAAI,aAAa,WAAW,GAAG;AAC7B,wBAAY,aAAa,CAAC,EAAE;AAC5B;AAAA,UACF;AAGA,cAAI,UAAU;AACd,mBAAS,IAAI,GAAG,OAAO,gBAAgB,QAAQ,IAAI,MAAM,KAAK;AAC5D,gBAAI,gBAAgB,CAAC,EAAE,UAAU,MAAM,OAAO;AAC5C,wBAAU;AACV;AAAA,YACF;AAAA,UACF;AAEA,cAAI,YAAY,MAAM;AACpB,kBAAM,iBAAiB,gBAAgB,OAAO,OAAO,EAAE,CAAC;AACxD,kBAAM,aAAa,OAAO,OAAO,eAAe,KAAK;AACrD,uBAAW,QAAQ,WAAW,CAAC,EAAE,OAAO;AACxC,qBAAS,KAAK,IAAI,SAAQ,WAAW,QAAQ,CAAC,CAAC;AAC/C;AAAA,UACF;AAEA,0BAAgB,KAAK;AAAA,YACnB,OAAO,OAAO;AAAA,YACd,OAAO,MAAM;AAAA,UACf,CAAC;AAED,gBAAM,aAAa,MAAM,sBAAsB,SAAS;AACxD,sBAAY,aAAa,KAAK,UAAU,EAAE,CAAC,EAAE;AAC7C;AAAA,QACF;AAAA,MACF;AAEA,eAAS,KAAK,IAAI,SAAQ,MAAM,CAAC;AAAA,IACnC;AACA,WAAO;AAAA,EACT;AAAA,EAEA,YAAY,QAAsB;AAChC,SAAK,SAAS;AACd,aAAS,IAAI,GAAG,OAAO,OAAO,QAAQ,IAAI,MAAM,KAAK;AACnD,aAAO,CAAC,EAAE,QAAQ,UAAU;AAAA,IAC9B;AACA,SAAK,OAAO;AAAA,EACd;AAAA,EAEA,UAAU;AAER,QAAI,SAAS,KAAK,OAAO,CAAC,EAAE;AAC5B,UAAM,SAAS,CAAC,MAAM;AACtB,aAAS,IAAI,GAAG,OAAO,KAAK,OAAO,SAAS,GAAG,IAAI,MAAM,KAAK;AAC5D,YAAMC,MAAK,KAAK,OAAO,CAAC,EAAE;AAC1B,YAAMC,UAAS,KAAK,OAAO,IAAI,CAAC,EAAE;AAClC,UAAI,UAAU,OAAOD,KAAI,QAAQC,OAAM,MAAM,EAAG;AAChD,aAAO,KAAKD,GAAE;AACd,eAASA;AAAA,IACX;AAGA,QAAI,OAAO,WAAW,EAAG,QAAO;AAGhC,UAAM,KAAK,OAAO,CAAC;AACnB,UAAM,SAAS,OAAO,CAAC;AACvB,QAAI,UAAU,OAAO,IAAI,QAAQ,MAAM,MAAM,EAAG,QAAO,MAAM;AAE7D,WAAO,KAAK,OAAO,CAAC,CAAC;AACrB,UAAM,OAAO,KAAK,eAAe,IAAI,IAAI;AACzC,UAAM,SAAS,KAAK,eAAe,IAAI,IAAI,OAAO,SAAS;AAC3D,UAAM,OAAO,KAAK,eAAe,IAAI,OAAO,SAAS;AACrD,UAAM,gBAAsB,CAAC;AAC7B,aAAS,IAAI,QAAQ,KAAK,MAAM,KAAK;AACnC,oBAAc,KAAK,CAAC,OAAO,CAAC,EAAE,EAAE,SAAS,GAAG,OAAO,CAAC,EAAE,EAAE,SAAS,CAAC,CAAC;AACrE,WAAO;AAAA,EACT;AAAA,EAEA,iBAA0B;AACxB,QAAI,KAAK,oBAAoB,QAAW;AACtC,YAAM,YAAY,KAAK,cAAc;AACrC,WAAK,kBAAkB,YAAY,CAAC,UAAU,eAAe,IAAI;AAAA,IACnE;AACA,WAAO,KAAK;AAAA,EACd;AAAA,EAEA,gBAAgB;AACd,QAAI,KAAK,mBAAmB,QAAW;AACrC,WAAK,iBAAiB,KAAK,mBAAmB;AAAA,IAChD;AACA,WAAO,KAAK;AAAA,EACd;AAAA;AAAA,EAGA,qBAAiD;AAG/C,QAAI,cAAc,KAAK,OAAO,CAAC;AAC/B,aAAS,IAAI,GAAG,OAAO,KAAK,OAAO,QAAQ,IAAI,MAAM,KAAK;AACxD,YAAM,MAAM,KAAK,OAAO,CAAC;AACzB,UAAI,WAAW,QAAQ,aAAa,GAAG,IAAI,EAAG,eAAc;AAAA,IAC9D;AAEA,QAAI,UAAsC,YAAY,QAAQ,aAAa;AAC3E,QAAI,cAA0C,UAAU,QAAQ,aAAa,IAAI;AAEjF,WAAO,MAAM;AAEX,UAAI,CAAC,QAAS,QAAO;AAIrB,UAAI,CAAC,YAAa,QAAO,QAAQ;AAKjC,UAAI,YAAY,YAAY,QAAQ,SAAS;AAC3C,YAAI,YAAY,SAAS,cAAc,MAAM,QAAQ,SAAS;AAC5D,iBAAO,QAAQ;AAAA,QACjB,MAAO,QAAO,QAAQ,SAAS,cAAc;AAAA,MAC/C;AAIA,gBAAU,YAAY,aAAa;AACnC,oBAAc,UAAU,QAAQ,aAAa,IAAI;AAAA,IACnD;AAAA,EACF;AACF;AAEO,IAAM,UAAN,MAAc;AAAA,EACnB;AAAA,EACA;AAAA,EAEA,YAAY,cAAuB;AACjC,SAAK,eAAe;AACpB,iBAAa,OAAO;AACpB,SAAK,gBAAgB,CAAC;AAAA,EACxB;AAAA,EAEA,YAAY,MAAe;AACzB,SAAK,cAAc,KAAK,IAAI;AAC5B,SAAK,OAAO;AAAA,EACd;AAAA,EAEA,UAAU;AACR,UAAM,QAAQ,KAAK,aAAa,QAAQ;AAExC,QAAI,UAAU,KAAM,QAAO;AAC3B,UAAM,OAAa,CAAC,KAAK;AACzB,aAAS,IAAI,GAAG,OAAO,KAAK,cAAc,QAAQ,IAAI,MAAM,KAAK;AAC/D,YAAM,WAAW,KAAK,cAAc,CAAC,EAAE,QAAQ;AAE/C,UAAI,aAAa,KAAM;AACvB,WAAK,KAAK,QAAQ;AAAA,IACpB;AACA,WAAO;AAAA,EACT;AACF;AAEO,IAAM,eAAN,MAAmB;AAAA,EACxB;AAAA,EACA;AAAA,EAEA,YAAY,OAAkB;AAC5B,SAAK,QAAQ;AACb,SAAK,QAAQ,KAAK,cAAc,KAAK;AAAA,EACvC;AAAA,EAEA,UAAU;AACR,UAAM,OAAkB,CAAC;AACzB,aAAS,IAAI,GAAG,OAAO,KAAK,MAAM,QAAQ,IAAI,MAAM,KAAK;AACvD,YAAM,WAAW,KAAK,MAAM,CAAC,EAAE,QAAQ;AAEvC,UAAI,aAAa,KAAM;AACvB,WAAK,KAAK,QAAQ;AAAA,IACpB;AACA,WAAO;AAAA,EACT;AAAA,EAEA,cAAc,OAAkB;AAC9B,UAAM,QAAQ,CAAC;AACf,aAAS,IAAI,GAAG,OAAO,MAAM,QAAQ,IAAI,MAAM,KAAK;AAClD,YAAM,OAAO,MAAM,CAAC;AACpB,UAAI,KAAK,KAAM;AACf,UAAI,KAAK,eAAe,EAAG,OAAM,KAAK,IAAI,QAAQ,IAAI,CAAC;AAAA,WAClD;AACH,cAAM,gBAAgB,KAAK,cAAc;AACzC,YAAI,CAAC,eAAe,KAAM,OAAM,KAAK,IAAI,QAAQ,aAAc,CAAC;AAChE,uBAAe,MAAM,YAAY,IAAI;AAAA,MACvC;AAAA,IACF;AACA,WAAO;AAAA,EACT;AACF;;;ACtPA,SAAS,gBAAAE,qBAAoB;AAe7B,IAAqB,YAArB,MAA+B;AAAA,EACrB;AAAA,EACA;AAAA,EACR;AAAA,EAEA,YAAY,OAAiC,aAAa,QAAQ,SAAS;AACzE,SAAK,QAAQ;AACb,SAAK,OAAO,IAAIC,cAAa,UAAU;AACvC,SAAK,WAAW,CAAC;AAAA,EACnB;AAAA,EAEA,QAAQ,OAAmB;AACzB,UAAM,UAAU,MAAM;AACtB,UAAM,YAA0B,CAAC;AAIjC,QAAI,MAAM,YAAY;AACpB,UAAI,MAAM,OAAQ,MAAK,MAAM,OAAO,MAAM,OAAO;AAAA,UAC5C,MAAK,KAAK,OAAO,OAAO;AAC7B,aAAO;AAAA,IACT;AAEA,QAAI,MAAM,OAAQ,MAAK,KAAK,IAAI,OAAO;AAEvC,QAAI,UAA0B;AAC9B,QAAI,UAA0B;AAG9B,OAAG;AACD,gBAAU,KAAK,KAAK,WAAW,OAAO;AAAA,IACxC,SAAS,WAAW,QAAQ,QAAQ,cAAc;AAGlD,OAAG;AACD,gBAAU,KAAK,KAAK,WAAW,OAAO;AAAA,IACxC,SAAS,WAAW,QAAQ,QAAQ,cAAc;AAElD,QAAI,MAAM,QAAQ;AAEhB,UAAI,iBAAiB;AACrB,UAAI,SAAS;AACX,cAAM,YAAY,QAAQ,gBAAgB,OAAO;AACjD,YAAI,cAAc,MAAM;AACtB,cAAI,CAAC,QAAQ,aAAa,SAAS,EAAG,kBAAiB;AACvD,cAAI,CAAC,QAAQ,aAAa,SAAS,GAAG;AACpC,kBAAM,qBAAqB,KAAK,aAAa,SAAS,SAAS;AAC/D,qBAAS,IAAI,GAAG,OAAO,mBAAmB,QAAQ,IAAI,MAAM,KAAK;AAC/D,wBAAU,KAAK,mBAAmB,CAAC,CAAC;AAAA,YACtC;AAAA,UACF;AAAA,QACF;AAAA,MACF;AAGA,UAAI,iBAAiB;AACrB,UAAI,SAAS;AACX,cAAM,YAAY,QAAQ,gBAAgB,OAAO;AACjD,YAAI,cAAc,MAAM;AACtB,cAAI,CAAC,QAAQ,aAAa,SAAS,EAAG,kBAAiB;AACvD,cAAI,CAAC,QAAQ,aAAa,SAAS,GAAG;AACpC,kBAAM,qBAAqB,KAAK,aAAa,SAAS,SAAS;AAC/D,qBAAS,IAAI,GAAG,OAAO,mBAAmB,QAAQ,IAAI,MAAM,KAAK;AAC/D,wBAAU,KAAK,mBAAmB,CAAC,CAAC;AAAA,YACtC;AAAA,UACF;AAAA,QACF;AAAA,MACF;AAKA,UAAI,mBAAmB,QAAQ,mBAAmB,MAAM;AACtD,YAAI,aAAa;AACjB,YAAI,mBAAmB,KAAM,cAAa;AAAA,iBACjC,mBAAmB,KAAM,cAAa;AAAA,aAC1C;AACH,gBAAM,eAAe,WAAW;AAAA,YAC9B;AAAA,YACA;AAAA,UACF;AACA,uBAAa,gBAAgB,IAAI,iBAAiB;AAAA,QACpD;AAIA,aAAK,MAAM,OAAO,QAAQ,OAAO;AACjC,kBAAU,KAAK,QAAQ,OAAO;AAE9B,cAAM,qBAAqB,QAAQ,MAAM,UAAW;AACpD,iBAAS,IAAI,GAAG,OAAO,mBAAmB,QAAQ,IAAI,MAAM,KAAK;AAC/D,oBAAU,KAAK,mBAAmB,CAAC,CAAC;AAAA,QACtC;AAAA,MACF;AAEA,UAAI,UAAU,SAAS,GAAG;AAIxB,aAAK,KAAK,OAAO,OAAO;AACxB,kBAAU,KAAK,KAAK;AAAA,MACtB,OAAO;AAEL,aAAK,SAAS,KAAK,OAAO;AAC1B,gBAAQ,OAAO;AAAA,MACjB;AAAA,IACF,OAAO;AAKL,UAAI,WAAW,SAAS;AACtB,cAAM,QAAQ,QAAQ,gBAAgB,OAAO;AAC7C,YAAI,UAAU,MAAM;AAClB,cAAI,CAAC,QAAQ,aAAa,KAAK,GAAG;AAChC,kBAAM,qBAAqB,KAAK,aAAa,SAAS,KAAK;AAC3D,qBAAS,IAAI,GAAG,OAAO,mBAAmB,QAAQ,IAAI,MAAM,KAAK;AAC/D,wBAAU,KAAK,mBAAmB,CAAC,CAAC;AAAA,YACtC;AAAA,UACF;AACA,cAAI,CAAC,QAAQ,aAAa,KAAK,GAAG;AAChC,kBAAM,qBAAqB,KAAK,aAAa,SAAS,KAAK;AAC3D,qBAAS,IAAI,GAAG,OAAO,mBAAmB,QAAQ,IAAI,MAAM,KAAK;AAC/D,wBAAU,KAAK,mBAAmB,CAAC,CAAC;AAAA,YACtC;AAAA,UACF;AAAA,QACF;AAAA,MACF;AAEA,WAAK,KAAK,OAAO,OAAO;AAAA,IAC1B;AAEA,WAAO;AAAA,EACT;AAAA;AAAA;AAAA,EAIA,aAAa,KAAc,IAAW;AAKpC,SAAK,KAAK,OAAO,GAAG;AACpB,UAAM,UAAU,IAAI;AACpB,SAAK,MAAM,OAAO,OAAO;AACzB,UAAM,YAAY,IAAI,MAAM,EAAE;AAC9B,cAAU,KAAK,OAAO;AAEtB,QAAI,IAAI,eAAe,OAAW,MAAK,KAAK,IAAI,GAAG;AACnD,WAAO;AAAA,EACT;AACF;;;AJ7JO,IAAM,YAAN,MAAgB;AAAA,EACrB;AAAA,EACA;AAAA,EAEA,IAAI,MAAc,MAAY,WAAmB;AAC/C,cAAU,OAAO;AAGjB,UAAM,aAAa,CAAC,IAAW,YAAY,MAAM,IAAI,CAAC;AACtD,aAAS,IAAI,GAAG,OAAO,UAAU,QAAQ,IAAI,MAAM,KAAK;AACtD,iBAAW,KAAK,IAAW,YAAY,UAAU,CAAC,GAAG,KAAK,CAAC;AAAA,IAC7D;AACA,cAAU,gBAAgB,WAAW;AAMrC,QAAI,UAAU,SAAS,cAAc;AAEnC,YAAM,UAAU,WAAW,CAAC;AAC5B,UAAI,IAAI;AACR,aAAO,IAAI,WAAW,QAAQ;AAC5B,YAAI,eAAe,WAAW,CAAC,EAAE,MAAM,QAAQ,IAAI,MAAM,KAAM;AAAA,YAC1D,YAAW,OAAO,GAAG,CAAC;AAAA,MAC7B;AAAA,IACF;AAKA,QAAI,UAAU,SAAS,gBAAgB;AAGrC,eAAS,IAAI,GAAG,OAAO,WAAW,QAAQ,IAAI,MAAM,KAAK;AACvD,cAAM,MAAM,WAAW,CAAC;AACxB,iBAAS,IAAI,IAAI,GAAG,OAAO,WAAW,QAAQ,IAAI,MAAM,KAAK;AAC3D,cAAI,eAAe,IAAI,MAAM,WAAW,CAAC,EAAE,IAAI,MAAM,KAAM,QAAO,CAAC;AAAA,QACrE;AAAA,MACF;AAAA,IACF;AAGA,UAAM,QAAQ,IAAIC,cAAa,WAAW,OAAO;AACjD,aAAS,IAAI,GAAG,OAAO,WAAW,QAAQ,IAAI,MAAM,KAAK;AACvD,YAAM,cAAc,WAAW,CAAC,EAAE,eAAe;AACjD,eAAS,IAAI,GAAG,OAAO,YAAY,QAAQ,IAAI,MAAM,KAAK;AACxD,cAAM,IAAI,YAAY,CAAC,CAAC;AAAA,MAC1B;AAAA,IACF;AAGA,UAAM,YAAY,IAAI,UAAU,KAAK;AACrC,QAAI,MAAM;AACV,QAAI,MAAM,QAAQ,GAAG;AACnB,YAAM,MAAM,MAAM;AAClB,YAAM,OAAO,GAAG;AAAA,IAClB;AACA,WAAO,KAAK;AACV,YAAM,YAAY,UAAU,QAAQ,GAAG;AACvC,eAAS,IAAI,GAAG,OAAO,UAAU,QAAQ,IAAI,MAAM,KAAK;AACtD,cAAMC,OAAM,UAAU,CAAC;AACvB,YAAIA,KAAI,eAAe,OAAW,OAAM,IAAIA,IAAG;AAAA,MACjD;AACA,UAAI,MAAM,QAAQ,GAAG;AACnB,cAAM,MAAM,MAAM;AAClB,cAAM,OAAO,GAAG;AAAA,MAClB,OAAO;AACL,cAAM;AAAA,MACR;AAAA,IACF;AAGA,cAAU,MAAM;AAGhB,UAAM,WAAmB,QAAQ,QAAQ,UAAU,QAAQ;AAC3D,UAAM,SAAS,IAAY,aAAa,QAAQ;AAChD,WAAO,OAAO,QAAQ;AAAA,EACxB;AACF;AAGA,IAAM,YAAY,IAAI,UAAU;AAEhC,IAAO,oBAAQ;;;AK9Ef,IAAI,YAAY;AAEhB,IAAqB,UAArB,MAAqB,SAAQ;AAAA,EAC3B;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAeA,OAAO,QAAQ,GAAY,GAAY;AACrC,UAAM,MAAM,EAAE,OAAO,MAAM;AAC3B,UAAM,MAAM,EAAE,OAAO,MAAM;AAC3B,UAAM,MAAM,EAAE,QAAQ,MAAM;AAC5B,UAAM,MAAM,EAAE,QAAQ,MAAM;AAG5B,QAAI,IAAI,WAAW,GAAG,EAAG,QAAO;AAChC,QAAI,IAAI,WAAW,GAAG,EAAG,QAAO;AAEhC,UAAM,MAAM,EAAE,OAAO,MAAM;AAC3B,UAAM,MAAM,EAAE,OAAO,MAAM;AAC3B,UAAM,MAAM,EAAE,QAAQ,MAAM;AAC5B,UAAM,MAAM,EAAE,QAAQ,MAAM;AAG5B,QAAI,IAAI,WAAW,GAAG,GAAG;AAEvB,UAAI,IAAI,WAAW,GAAG,KAAK,IAAI,WAAW,GAAG,EAAG,QAAO;AACvD,UAAI,IAAI,cAAc,GAAG,KAAK,IAAI,cAAc,GAAG,EAAG,QAAO;AAG7D,YAAM,YAAY,EAAE,aAAa,EAAE,OAAO,KAAK;AAC/C,UAAI,YAAY,EAAG,QAAO;AAC1B,UAAI,YAAY,EAAG,QAAO;AAG1B,YAAM,aAAa,EAAE,aAAa,EAAE,QAAQ,KAAK;AACjD,UAAI,eAAe,EAAG,QAAO;AAI7B,aAAO;AAAA,IACT;AAGA,QAAI,IAAI,cAAc,GAAG,GAAG;AAC1B,UAAI,IAAI,WAAW,GAAG,KAAK,IAAI,WAAW,GAAG,EAAG,QAAO;AACvD,UAAI,IAAI,cAAc,GAAG,KAAK,IAAI,cAAc,GAAG,EAAG,QAAO;AAG7D,YAAM,YAAY,EAAE,aAAa,EAAE,OAAO,KAAK;AAC/C,UAAI,cAAc,EAAG,QAAO;AAG5B,YAAM,aAAa,EAAE,aAAa,EAAE,QAAQ,KAAK;AACjD,UAAI,aAAa,EAAG,QAAO;AAC3B,UAAI,aAAa,EAAG,QAAO;AAI3B,aAAO;AAAA,IACT;AAMA,QAAI,IAAI,WAAW,GAAG,EAAG,QAAO;AAChC,QAAI,IAAI,cAAc,GAAG,EAAG,QAAO;AAMnC,QAAI,IAAI,WAAW,GAAG,GAAG;AACvB,YAAM,aAAa,EAAE,aAAa,EAAE,QAAQ,KAAK;AACjD,UAAI,eAAe,EAAG,QAAO;AAAA,IAC/B;AAGA,QAAI,IAAI,cAAc,GAAG,GAAG;AAC1B,YAAM,aAAa,EAAE,aAAa,EAAE,QAAQ,KAAK;AACjD,UAAI,aAAa,EAAG,QAAO;AAC3B,UAAI,aAAa,EAAG,QAAO;AAAA,IAC7B;AAEA,QAAI,CAAC,IAAI,GAAG,GAAG,GAAG;AAGhB,YAAM,KAAK,IAAI,MAAM,GAAG;AACxB,YAAM,KAAK,IAAI,MAAM,GAAG;AACxB,YAAM,KAAK,IAAI,MAAM,GAAG;AACxB,YAAM,KAAK,IAAI,MAAM,GAAG;AACxB,UAAI,GAAG,cAAc,EAAE,KAAK,GAAG,WAAW,EAAE,EAAG,QAAO;AACtD,UAAI,GAAG,WAAW,EAAE,KAAK,GAAG,cAAc,EAAE,EAAG,QAAO;AAAA,IACxD;AAIA,QAAI,IAAI,cAAc,GAAG,EAAG,QAAO;AACnC,QAAI,IAAI,WAAW,GAAG,EAAG,QAAO;AAMhC,QAAI,IAAI,WAAW,GAAG,EAAG,QAAO;AAChC,QAAI,IAAI,cAAc,GAAG,EAAG,QAAO;AAInC,QAAI,EAAE,KAAK,EAAE,GAAI,QAAO;AACxB,QAAI,EAAE,KAAK,EAAE,GAAI,QAAO;AAGxB,WAAO;AAAA,EACT;AAAA;AAAA;AAAA,EAIA,YAAY,QAAoB,SAAqB,OAAiB,UAAoB;AACxF,SAAK,KAAK,EAAE;AACZ,SAAK,SAAS;AACd,WAAO,UAAU;AACjB,WAAO,UAAU;AACjB,SAAK,UAAU;AACf,YAAQ,UAAU;AAClB,YAAQ,UAAU;AAClB,SAAK,QAAQ;AACb,SAAK,WAAW;AAAA,EAGlB;AAAA,EAEA,OAAO,SAAS,KAAY,KAAY,MAAc;AACpD,QAAI,QAAe,SAAgB;AAGnC,UAAM,SAAS,WAAW,cAAc,KAAK,GAAG;AAChD,QAAI,SAAS,GAAG;AACd,eAAS;AACT,gBAAU;AACV,gBAAU;AAAA,IACZ,WAAW,SAAS,GAAG;AACrB,eAAS;AACT,gBAAU;AACV,gBAAU;AAAA,IACZ;AACE,YAAM,IAAI;AAAA,QACR,0CAA0C,IAAI,CAAC,KAAK,IAAI,CAAC;AAAA,MAC3D;AAEF,UAAM,SAAS,IAAI,WAAW,QAAQ,IAAI;AAC1C,UAAM,UAAU,IAAI,WAAW,SAAS,KAAK;AAC7C,WAAO,IAAI,SAAQ,QAAQ,SAAS,CAAC,IAAI,GAAG,CAAC,OAAO,CAAC;AAAA,EACvD;AAAA;AAAA,EAGA,eAAe,YAAwB;AACrC,SAAK,UAAU;AACf,SAAK,QAAQ,UAAU;AACvB,SAAK,QAAQ,UAAU,KAAK;AAC5B,SAAK,OAAO,UAAU,KAAK;AAAA,EAC7B;AAAA,EAEA,OAAO;AACL,UAAM,KAAK,KAAK,OAAO,MAAM;AAC7B,UAAM,KAAK,KAAK,QAAQ,MAAM;AAC9B,WAAO;AAAA,MACL,IAAI,EAAE,GAAG,KAAK,OAAO,MAAM,GAAG,GAAG,GAAG,WAAW,EAAE,IAAI,KAAK,GAAG;AAAA,MAC7D,IAAI,EAAE,GAAG,KAAK,QAAQ,MAAM,GAAG,GAAG,GAAG,cAAc,EAAE,IAAI,KAAK,GAAG;AAAA,IACnE;AAAA,EACF;AAAA;AAAA,EAGA,SAAS;AACP,WAAO;AAAA,MACL,GAAG,KAAK,QAAQ,MAAM,EAAE,MAAM,KAAK,OAAO,MAAM,CAAC;AAAA,MACjD,GAAG,KAAK,QAAQ,MAAM,EAAE,MAAM,KAAK,OAAO,MAAM,CAAC;AAAA,IACnD;AAAA,EACF;AAAA,EAEA,aAAa,IAAW;AACtB,WACG,GAAG,EAAE,GAAG,KAAK,OAAO,MAAM,CAAC,KAAK,GAAG,EAAE,GAAG,KAAK,OAAO,MAAM,CAAC,KAC3D,GAAG,EAAE,GAAG,KAAK,QAAQ,MAAM,CAAC,KAAK,GAAG,EAAE,GAAG,KAAK,QAAQ,MAAM,CAAC;AAAA,EAElE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAeA,aAAa,OAAc;AACzB,WAAO,UAAU,OAAO,KAAK,OAAO,OAAO,OAAO,KAAK,QAAQ,KAAK;AAAA,EACtE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAiBA,gBAAgB,OAAgB;AAE9B,UAAM,QAAQ,KAAK,KAAK;AACxB,UAAM,QAAQ,MAAM,KAAK;AACzB,UAAM,cAAc,eAAe,OAAO,KAAK;AAC/C,QAAI,gBAAgB,KAAM,QAAO;AAMjC,UAAM,MAAM,KAAK,OAAO;AACxB,UAAM,MAAM,KAAK,QAAQ;AACzB,UAAM,MAAM,MAAM,OAAO;AACzB,UAAM,MAAM,MAAM,QAAQ;AAK1B,UAAM,kBAAkB,SAAS,OAAO,GAAG,KAAK,KAAK,aAAa,GAAG,MAAM;AAC3E,UAAM,iBAAiB,SAAS,OAAO,GAAG,KAAK,MAAM,aAAa,GAAG,MAAM;AAC3E,UAAM,kBAAkB,SAAS,OAAO,GAAG,KAAK,KAAK,aAAa,GAAG,MAAM;AAC3E,UAAM,iBAAiB,SAAS,OAAO,GAAG,KAAK,MAAM,aAAa,GAAG,MAAM;AAG3E,QAAI,kBAAkB,iBAAiB;AAGrC,UAAI,kBAAkB,CAAC,gBAAiB,QAAO;AAC/C,UAAI,CAAC,kBAAkB,gBAAiB,QAAO;AAG/C,aAAO;AAAA,IACT;AAGA,QAAI,gBAAgB;AAElB,UAAI,iBAAiB;AACnB,YAAI,IAAI,EAAE,GAAG,IAAI,CAAC,KAAK,IAAI,EAAE,GAAG,IAAI,CAAC,EAAG,QAAO;AAAA,MACjD;AAEA,aAAO;AAAA,IACT;AAGA,QAAI,iBAAiB;AAEnB,UAAI,gBAAgB;AAClB,YAAI,IAAI,EAAE,GAAG,IAAI,CAAC,KAAK,IAAI,EAAE,GAAG,IAAI,CAAC,EAAG,QAAO;AAAA,MACjD;AAEA,aAAO;AAAA,IACT;AAGA,QAAI,kBAAkB,gBAAiB,QAAO;AAG9C,QAAI,eAAgB,QAAO;AAC3B,QAAI,gBAAiB,QAAO;AAI5B,UAAM,KAAK,aAAa,KAAK,KAAK,OAAO,GAAG,KAAK,MAAM,OAAO,CAAC;AAI/D,QAAI,OAAO,KAAM,QAAO;AAGxB,QAAI,CAAC,SAAS,aAAa,EAAE,EAAG,QAAO;AAGvC,WAAO,UAAU,KAAK,EAAE;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAcA,MAAM,OAAc;AAClB,UAAM,YAAY,CAAC;AACnB,UAAM,gBAAgB,MAAM,WAAW;AAEvC,UAAM,YAAY,IAAI,WAAW,OAAO,IAAI;AAC5C,UAAM,aAAa,IAAI,WAAW,OAAO,KAAK;AAC9C,UAAM,aAAa,KAAK;AACxB,SAAK,eAAe,UAAU;AAC9B,cAAU,KAAK,UAAU;AACzB,cAAU,KAAK,SAAS;AACxB,UAAM,SAAS,IAAI;AAAA,MACjB;AAAA,MACA;AAAA,MACA,KAAK,MAAO,MAAM;AAAA,MAClB,KAAK,SAAU,MAAM;AAAA,IACvB;AAKA,QACE,WAAW,cAAc,OAAO,OAAO,OAAO,OAAO,QAAQ,KAAK,IAAI,GACtE;AACA,aAAO,WAAW;AAAA,IACpB;AACA,QAAI,WAAW,cAAc,KAAK,OAAO,OAAO,KAAK,QAAQ,KAAK,IAAI,GAAG;AACvE,WAAK,WAAW;AAAA,IAClB;AAKA,QAAI,eAAe;AACjB,gBAAU,kBAAkB;AAC5B,iBAAW,kBAAkB;AAAA,IAC/B;AAEA,WAAO;AAAA,EACT;AAAA;AAAA,EAGA,aAAa;AACX,UAAM,SAAS,KAAK;AACpB,SAAK,UAAU,KAAK;AACpB,SAAK,SAAS;AACd,SAAK,OAAO,SAAS;AACrB,SAAK,QAAQ,SAAS;AACtB,aAAS,IAAI,GAAG,OAAO,KAAK,SAAU,QAAQ,IAAI,MAAM,KAAK;AAC3D,WAAK,SAAU,CAAC,KAAK;AAAA,IACvB;AAAA,EACF;AAAA;AAAA;AAAA,EAIA,QAAQ,OAAgB;AACtB,QAAI,WAAW;AACf,QAAI,WAAW;AACf,WAAO,SAAS,WAAY,YAAW,SAAS;AAChD,WAAO,SAAS,WAAY,YAAW,SAAS;AAEhD,UAAM,MAAM,SAAQ,QAAQ,UAAU,QAAQ;AAC9C,QAAI,QAAQ,EAAG;AAGf,QAAI,MAAM,GAAG;AACX,YAAM,MAAM;AACZ,iBAAW;AACX,iBAAW;AAAA,IACb;AAGA,QAAI,SAAS,SAAS,UAAU;AAC9B,YAAM,MAAM;AACZ,iBAAW;AACX,iBAAW;AAAA,IACb;AAEA,aAAS,IAAI,GAAG,OAAO,SAAS,MAAO,QAAQ,IAAI,MAAM,KAAK;AAC5D,YAAM,OAAO,SAAS,MAAO,CAAC;AAC9B,YAAM,UAAU,SAAS,SAAU,CAAC;AACpC,YAAM,QAAQ,SAAS,MAAO,QAAQ,IAAI;AAC1C,UAAI,UAAU,IAAI;AAChB,iBAAS,MAAO,KAAK,IAAI;AACzB,iBAAS,SAAU,KAAK,OAAO;AAAA,MACjC,MAAO,UAAS,SAAU,KAAK,KAAK;AAAA,IACtC;AACA,aAAS,QAAQ;AACjB,aAAS,WAAW;AACpB,aAAS,aAAa;AAGtB,aAAS,OAAO,aAAa,SAAS;AACtC,aAAS,QAAQ,aAAa,SAAS;AAAA,EACzC;AAAA;AAAA,EAGA,eAA2C;AACzC,QAAI,KAAK,kBAAkB,OAAW,QAAO,KAAK;AAClD,QAAI,CAAC,KAAK,KAAM,MAAK,gBAAgB;AAAA,aAC5B,KAAK,KAAK,WAAW,EAAG,MAAK,gBAAgB,KAAK;AAAA,QACtD,MAAK,gBAAgB,KAAK,KAAK,aAAa;AACjD,WAAO,KAAK;AAAA,EACd;AAAA,EAEA,cAAqB;AACnB,QAAI,KAAK,iBAAiB,OAAW,QAAO,KAAK;AACjD,QAAI,CAAC,KAAK;AACR,WAAK,eAAe;AAAA,QAClB,OAAO,CAAC;AAAA,QACR,UAAU,CAAC;AAAA,QACX,YAAY,CAAC;AAAA,MACf;AAAA,SACG;AACH,YAAM,MAAM,KAAK,KAAK,cAAc,KAAK;AACzC,WAAK,eAAe,IAAI,WAAW;AAAA,IACrC;AACA,WAAO,KAAK;AAAA,EACd;AAAA,EAEA,aAAa;AACX,QAAI,KAAK,gBAAgB,OAAW,QAAO,KAAK;AAEhD,UAAM,cAAc,KAAK,YAAY;AACrC,SAAK,cAAc;AAAA,MACjB,OAAO,YAAY,MAAM,MAAM,CAAC;AAAA,MAChC,UAAU,YAAY,SAAS,MAAM,CAAC;AAAA,MACtC,YAAY,CAAC;AAAA,IACf;AACA,UAAM,aAAa,KAAK,YAAY;AACpC,UAAM,gBAAgB,KAAK,YAAY;AACvC,UAAM,WAAW,KAAK,YAAY;AAGlC,aAAS,IAAI,GAAG,OAAO,KAAK,MAAO,QAAQ,IAAI,MAAM,KAAK;AACxD,YAAM,OAAO,KAAK,MAAO,CAAC;AAC1B,YAAM,UAAU,KAAK,SAAU,CAAC;AAChC,YAAM,QAAQ,WAAW,QAAQ,IAAI;AACrC,UAAI,UAAU,IAAI;AAChB,mBAAW,KAAK,IAAI;AACpB,sBAAc,KAAK,OAAO;AAAA,MAC5B,MAAO,eAAc,KAAK,KAAK;AAAA,IACjC;AAGA,UAAM,aAAa,CAAC;AACpB,UAAM,eAAe,CAAC;AACtB,aAAS,IAAI,GAAG,OAAO,WAAW,QAAQ,IAAI,MAAM,KAAK;AACvD,UAAI,cAAc,CAAC,MAAM,EAAG;AAC5B,YAAM,OAAO,WAAW,CAAC;AACzB,YAAM,OAAO,KAAK;AAClB,UAAI,aAAa,QAAQ,IAAI,MAAM,GAAI;AACvC,UAAI,KAAK,WAAY,YAAW,KAAK,IAAI;AAAA,WACpC;AACH,YAAI,aAAa,QAAQ,IAAI,MAAM,GAAI,cAAa,KAAK,IAAI;AAC7D,cAAM,QAAQ,WAAW,QAAQ,KAAK,IAAI;AAC1C,YAAI,UAAU,GAAI,YAAW,OAAO,OAAO,CAAC;AAAA,MAC9C;AAAA,IACF;AAGA,aAAS,IAAI,GAAG,OAAO,WAAW,QAAQ,IAAI,MAAM,KAAK;AACvD,YAAM,KAAK,WAAW,CAAC,EAAE;AACzB,UAAI,SAAS,QAAQ,EAAE,MAAM,GAAI,UAAS,KAAK,EAAE;AAAA,IACnD;AAEA,WAAO,KAAK;AAAA,EACd;AAAA;AAAA,EAGA,aAAa;AAEX,QAAI,KAAK,WAAY,QAAO;AAE5B,QAAI,KAAK,gBAAgB,OAAW,QAAO,KAAK;AAEhD,UAAM,YAAY,KAAK,YAAY,EAAE;AACrC,UAAM,WAAW,KAAK,WAAW,EAAE;AAEnC,YAAQ,kBAAU,MAAM;AAAA,MACtB,KAAK,SAAS;AAIZ,cAAM,YAAY,UAAU,WAAW;AACvC,cAAM,WAAW,SAAS,WAAW;AACrC,aAAK,cAAc,cAAc;AACjC;AAAA,MACF;AAAA,MAEA,KAAK,gBAAgB;AAKnB,YAAI;AACJ,YAAI;AACJ,YAAI,UAAU,SAAS,SAAS,QAAQ;AACtC,kBAAQ,UAAU;AAClB,iBAAO,SAAS;AAAA,QAClB,OAAO;AACL,kBAAQ,SAAS;AACjB,iBAAO,UAAU;AAAA,QACnB;AACA,aAAK,cAAc,SAAS,kBAAU,iBAAiB,QAAQ;AAC/D;AAAA,MACF;AAAA,MAEA,KAAK,OAAO;AAIV,cAAM,OAAO,KAAK,IAAI,UAAU,SAAS,SAAS,MAAM;AACxD,aAAK,cAAc,OAAO,MAAM;AAChC;AAAA,MACF;AAAA,MAEA,KAAK,cAAc;AAGjB,cAAM,gBAAgB,CAAC,QAAuB,IAAI,WAAW,KAAK,IAAI,CAAC,EAAE;AACzE,aAAK,cAAc,cAAc,SAAS,MAAM,cAAc,QAAQ;AACtE;AAAA,MACF;AAAA,IACF;AAEA,WAAO,KAAK;AAAA,EACd;AACF;;;AbljBO,IAAM,SAAN,MAAa;AAAA,EAClB;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EAEA,YAAY,UAAgB,MAAc,YAAqB;AAC7D,QAAI,CAAC,MAAM,QAAQ,QAAQ,KAAK,SAAS,WAAW,GAAG;AACrD,YAAM,IAAI,MAAM,uDAAuD;AAAA,IACzE;AAEA,SAAK,OAAO;AACZ,SAAK,aAAa;AAClB,SAAK,WAAW,CAAC;AAEjB,QACE,OAAO,SAAS,CAAC,EAAE,CAAC,MAAM,YAC1B,OAAO,SAAS,CAAC,EAAE,CAAC,MAAM,UAC1B;AACA,YAAM,IAAI,MAAM,uDAAuD;AAAA,IACzE;AAEA,UAAM,aAAa,UAAU,KAAK,EAAE,GAAG,IAAIC,WAAU,SAAS,CAAC,EAAE,CAAC,CAAC,GAAG,GAAG,IAAIA,WAAU,SAAS,CAAC,EAAE,CAAC,CAAC,EAAE,CAAC;AACxG,SAAK,OAAO;AAAA,MACV,IAAI,EAAE,GAAG,WAAW,GAAG,GAAG,WAAW,EAAE;AAAA,MACvC,IAAI,EAAE,GAAG,WAAW,GAAG,GAAG,WAAW,EAAE;AAAA,IACzC;AAEA,QAAI,YAAY;AAChB,aAAS,IAAI,GAAG,OAAO,SAAS,QAAQ,IAAI,MAAM,KAAK;AACrD,UACE,OAAO,SAAS,CAAC,EAAE,CAAC,MAAM,YAC1B,OAAO,SAAS,CAAC,EAAE,CAAC,MAAM,UAC1B;AACA,cAAM,IAAI,MAAM,uDAAuD;AAAA,MACzE;AACA,YAAM,QAAQ,UAAU,KAAK,EAAE,GAAG,IAAIA,WAAU,SAAS,CAAC,EAAE,CAAC,CAAC,GAAG,GAAG,IAAIA,WAAU,SAAS,CAAC,EAAE,CAAC,CAAC,EAAE,CAAC;AAEnG,UAAI,MAAM,EAAE,GAAG,UAAU,CAAC,KAAK,MAAM,EAAE,GAAG,UAAU,CAAC,EAAG;AACxD,WAAK,SAAS,KAAK,QAAQ,SAAS,WAAW,OAAO,IAAI,CAAC;AAC3D,UAAI,MAAM,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,MAAM;AAC/D,UAAI,MAAM,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,MAAM;AAC/D,UAAI,MAAM,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,MAAM;AAClE,UAAI,MAAM,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,MAAM;AAClE,kBAAY;AAAA,IACd;AAEA,QAAI,CAAC,WAAW,EAAE,GAAG,UAAU,CAAC,KAAK,CAAC,WAAW,EAAE,GAAG,UAAU,CAAC,GAAG;AAClE,WAAK,SAAS,KAAK,QAAQ,SAAS,WAAW,YAAY,IAAI,CAAC;AAAA,IAClE;AAAA,EACF;AAAA,EAEA,iBAAiB;AACf,UAAM,cAAc,CAAC;AACrB,aAAS,IAAI,GAAG,OAAO,KAAK,SAAS,QAAQ,IAAI,MAAM,KAAK;AAC1D,YAAM,UAAU,KAAK,SAAS,CAAC;AAC/B,kBAAY,KAAK,QAAQ,MAAM;AAC/B,kBAAY,KAAK,QAAQ,OAAO;AAAA,IAClC;AACA,WAAO;AAAA,EACT;AACF;AAEO,IAAM,SAAN,MAAa;AAAA,EAClB;AAAA,EACA;AAAA,EACA;AAAA,EACA;AAAA,EAEA,YAAY,UAAgB,WAAwB;AAClD,QAAI,CAAC,MAAM,QAAQ,QAAQ,GAAG;AAC5B,YAAM,IAAI,MAAM,uDAAuD;AAAA,IACzE;AACA,SAAK,eAAe,IAAI,OAAO,SAAS,CAAC,GAAG,MAAM,IAAI;AAEtD,SAAK,OAAO;AAAA,MACV,IAAI,EAAE,GAAG,KAAK,aAAa,KAAK,GAAG,GAAG,GAAG,KAAK,aAAa,KAAK,GAAG,EAAE;AAAA,MACrE,IAAI,EAAE,GAAG,KAAK,aAAa,KAAK,GAAG,GAAG,GAAG,KAAK,aAAa,KAAK,GAAG,EAAE;AAAA,IACvE;AACA,SAAK,gBAAgB,CAAC;AACtB,aAAS,IAAI,GAAG,OAAO,SAAS,QAAQ,IAAI,MAAM,KAAK;AACrD,YAAM,OAAO,IAAI,OAAO,SAAS,CAAC,GAAG,MAAM,KAAK;AAChD,UAAI,KAAK,KAAK,GAAG,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAC7E,UAAI,KAAK,KAAK,GAAG,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAC7E,UAAI,KAAK,KAAK,GAAG,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAChF,UAAI,KAAK,KAAK,GAAG,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAChF,WAAK,cAAc,KAAK,IAAI;AAAA,IAC9B;AACA,SAAK,YAAY;AAAA,EACnB;AAAA,EAEA,iBAAiB;AACf,UAAM,cAAc,KAAK,aAAa,eAAe;AACrD,aAAS,IAAI,GAAG,OAAO,KAAK,cAAc,QAAQ,IAAI,MAAM,KAAK;AAC/D,YAAM,kBAAkB,KAAK,cAAc,CAAC,EAAE,eAAe;AAC7D,eAAS,IAAI,GAAG,OAAO,gBAAgB,QAAQ,IAAI,MAAM,KAAK;AAC5D,oBAAY,KAAK,gBAAgB,CAAC,CAAC;AAAA,MACrC;AAAA,IACF;AACA,WAAO;AAAA,EACT;AACF;AAEO,IAAM,cAAN,MAAkB;AAAA,EACvB;AAAA,EACA;AAAA,EACA;AAAA,EAEA,YAAY,MAAY,WAAoB;AAC1C,QAAI,CAAC,MAAM,QAAQ,IAAI,GAAG;AACxB,YAAM,IAAI,MAAM,uDAAuD;AAAA,IACzE;AAEA,QAAI;AAEF,UAAI,OAAO,KAAK,CAAC,EAAE,CAAC,EAAE,CAAC,MAAM,SAAU,QAAO,CAAC,IAAY;AAAA,IAC7D,SAAS,IAAI;AAAA,IAGb;AAEA,SAAK,QAAQ,CAAC;AACd,SAAK,OAAO;AAAA,MACV,IAAI,EAAE,GAAG,IAAIA,WAAU,OAAO,iBAAiB,GAAG,GAAG,IAAIA,WAAU,OAAO,iBAAiB,EAAE;AAAA,MAC7F,IAAI,EAAE,GAAG,IAAIA,WAAU,OAAO,iBAAiB,GAAG,GAAG,IAAIA,WAAU,OAAO,iBAAiB,EAAE;AAAA,IAC/F;AACA,aAAS,IAAI,GAAG,OAAO,KAAK,QAAQ,IAAI,MAAM,KAAK;AACjD,YAAM,OAAO,IAAI,OAAO,KAAK,CAAC,GAAW,IAAI;AAC7C,UAAI,KAAK,KAAK,GAAG,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAC7E,UAAI,KAAK,KAAK,GAAG,EAAE,WAAW,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAC7E,UAAI,KAAK,KAAK,GAAG,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAChF,UAAI,KAAK,KAAK,GAAG,EAAE,cAAc,KAAK,KAAK,GAAG,CAAC,EAAG,MAAK,KAAK,GAAG,IAAI,KAAK,KAAK,GAAG;AAChF,WAAK,MAAM,KAAK,IAAI;AAAA,IACtB;AACA,SAAK,YAAY;AAAA,EACnB;AAAA,EAEA,iBAAiB;AACf,UAAM,cAAc,CAAC;AACrB,aAAS,IAAI,GAAG,OAAO,KAAK,MAAM,QAAQ,IAAI,MAAM,KAAK;AACvD,YAAM,kBAAkB,KAAK,MAAM,CAAC,EAAE,eAAe;AACrD,eAAS,IAAI,GAAG,OAAO,gBAAgB,QAAQ,IAAI,MAAM,KAAK;AAC5D,oBAAY,KAAK,gBAAgB,CAAC,CAAC;AAAA,MACrC;AAAA,IACF;AACA,WAAO;AAAA,EACT;AACF;;;AcxJO,IAAM,QAAQ,CAAC,SAAe,cACnC,kBAAU,IAAI,SAAS,MAAM,SAAS;AAEjC,IAAMC,gBAAe,CAAC,SAAe,cAC1C,kBAAU,IAAI,gBAAgB,MAAM,SAAS;AAExC,IAAM,MAAM,CAAC,SAAe,cACjC,kBAAU,IAAI,OAAO,MAAM,SAAS;AAE/B,IAAM,aAAa,CAAC,SAAe,cACxC,kBAAU,IAAI,cAAc,MAAM,SAAS;AAEtC,IAAM,eAAe,UAAU;","names":["BigNumber","eps","SplayTreeSet","pt","nextPt","SplayTreeSet","SplayTreeSet","SplayTreeSet","evt","BigNumber","intersection"]}