{"version":3,"sources":["jsdelivr-header.js","/npm/curve-matcher@1.1.1/src/utils.ts","/npm/curve-matcher@1.1.1/src/geometry.ts","/npm/curve-matcher@1.1.1/src/frechetDistance.ts","/npm/curve-matcher@1.1.1/src/procrustesAnalysis.ts","/npm/curve-matcher@1.1.1/src/shapeSimilarity.ts"],"names":[],"mappings":"AAAA;AACA;AACA;AACA;AACA;AACA;AACA,gMCLO,IAAM,EAAU,SAAI,GAAgB,OAAA,EAAI,EAAI,OAAS,EAAE,EAGjD,EAAS,SAAC,GACrB,OAAA,EAAI,QAAO,SAAC,EAAK,GAAQ,OAAA,EAAM,CAAG,GAAE,EAApC,EAGW,EAAa,SAAC,GAEzB,OADY,EAAI,QAAO,SAAC,EAAK,GAAQ,OAAA,EAAM,CAAG,GAAE,GACnC,EAAI,MACnB,ECDa,EAAW,SAAC,EAAW,GAAqB,OACvD,EAAG,EAAG,EAAI,EAAG,EACb,EAAG,EAAG,EAAI,EAAG,EACd,EAEK,EAAY,SAAC,G,IAAE,EAAA,EAAA,EAAG,EAAA,EAAA,EAAe,OAAA,KAAK,KAAK,EAAI,EAAI,EAAI,EAAtB,EAO1B,EAAgB,SAAC,EAAe,GAC3C,OAAA,EAAU,EAAS,EAAQ,GAA3B,EAMW,EAAc,SAAC,GAC1B,IAAI,EAAY,EAAO,GAEvB,OADwB,EAAO,MAAM,GACd,QAAO,SAAC,EAAK,GAClC,IAAM,EAAO,EAAc,EAAO,GAElC,OADA,EAAY,EACL,EAAM,C,GACZ,EACL,EASa,EAAoB,SAAC,EAAW,EAAW,GACtD,IAAM,EAAO,EAAS,EAAI,GACpB,EAAO,EAAO,EAAU,GAC9B,MAAO,CAAE,EAAG,EAAG,EAAI,EAAO,EAAK,EAAG,EAAG,EAAG,EAAI,EAAO,EAAK,EAC1D,EA6Ca,EAAiB,SAC5B,EACA,GAQA,IANQ,IAAA,EAAA,EAAA,iBAAA,IAAA,EAAA,GAAA,EAEF,EADW,EAAY,IACE,EAAY,GACrC,EAAgB,CAAC,EAAM,IACvB,EAAW,EAAQ,GACnB,EAAuB,EAAM,MAAM,GAChC,EAAI,EAAG,EAAI,EAAY,EAAG,IAIjC,IAHA,IAAI,EAAY,EAAQ,GACpB,EAAgB,EAChB,GAAoB,GAChB,GAAmB,CACzB,IAAM,EAAgB,EAAc,EAAW,EAAqB,IACpE,GAAI,EAAgB,EAClB,GAAiB,EACjB,EAAY,EAAqB,YAC5B,CACL,IAAM,EAAY,EAChB,EACA,EAAqB,GACrB,EAAgB,GAElB,EAAc,KAAK,GACnB,GAAoB,C,EAK1B,OADA,EAAc,KAAK,GACZ,CACT,EAOa,EAAc,SAAC,EAAc,GACxC,OAAO,EAAM,KAAI,SAAA,GAAS,OACxB,EAAG,KAAK,KAAK,EAAI,GAAS,EAAM,EAAI,KAAK,KAAK,EAAI,GAAS,EAAM,EACjE,EAAG,KAAK,KAAK,EAAI,GAAS,EAAM,EAAI,KAAK,KAAK,EAAI,GAAS,EAAM,EAClE,GACH,ECpIM,EAAc,SAAC,EAAe,GA8BlC,IA7BA,IAAM,EAAY,EAAO,QAAU,EAAO,OAAS,EAAS,EACtD,EAAa,EAAO,QAAU,EAAO,OAAS,EAAS,EACvD,EAAU,SACd,EACA,EACA,EACA,GAEA,GAAU,IAAN,GAAiB,IAAN,EACb,OAAO,EAAc,EAAU,GAAI,EAAW,IAEhD,GAAI,EAAI,GAAW,IAAN,EACX,OAAO,KAAK,IACV,EAAe,GACf,EAAc,EAAU,GAAI,EAAW,KAG3C,IAAM,EAAa,EAAc,EAAc,OAAS,GACxD,OAAU,IAAN,GAAW,EAAI,EACV,KAAK,IAAI,EAAY,EAAc,EAAU,GAAI,EAAW,KAG9D,KAAK,IACV,KAAK,IAAI,EAAe,GAAI,EAAe,EAAI,GAAI,GACnD,EAAc,EAAU,GAAI,EAAW,I,EAIvC,EAA2B,GACtB,EAAI,EAAG,EAAI,EAAU,OAAQ,IAAK,CAEzC,IADA,IAAM,EAA0B,GACvB,EAAI,EAAG,EAAI,EAAW,OAAQ,IAKrC,EAAc,KAAK,EAAQ,EAAG,EAAG,EAAgB,IAEnD,EAAiB,C,CAGnB,OAAO,EAAe,EAAW,OAAS,EAC5C,EC5Ba,EAA2B,SACtC,EACA,QAAA,IAAA,MAAA,IAEQ,IAAA,EAAA,EAAA,iBAAA,IAAA,KAAkB,EAAA,EAAA,iBACpB,EAAgB,EAClB,EAAe,EAAO,CAAE,eAFF,IAAA,EAAA,GAAA,IAGtB,EAGE,EAAc,CAAE,EAFR,EAAW,EAAc,KAAI,SAAA,GAAS,OAAA,EAAM,CAAC,KAE3B,EADlB,EAAW,EAAc,KAAI,SAAA,GAAS,OAAA,EAAM,CAAC,MAErD,EAAkB,EAAc,KAAI,SAAA,GAAS,OAAA,EAAS,EAAO,EAAK,IAClE,EAAQ,KAAK,KACjB,EAAW,EAAgB,KAAI,SAAC,G,IAAE,EAAA,EAAA,EAAG,EAAA,EAAA,EAAQ,OAAA,EAAI,EAAI,EAAI,C,MAE3D,OAAO,EAAgB,KAAI,SAAA,GAAS,OAClC,EAAG,EAAM,EAAI,EACb,EAAG,EAAM,EAAI,EACd,GACH,EAWa,EAA8B,SACzC,EACA,GAEA,GAAI,EAAM,SAAW,EAAc,OACjC,MAAM,IAAI,MAAM,qDAGlB,IAAM,EAAY,EAChB,EAAM,KAAI,SAAC,EAAU,G,IAAR,EAAA,EAAA,EAAc,OAAX,EAAA,EAAe,EAAc,GAAG,EAAI,EAAI,EAAc,GAAG,C,KAErE,EAAc,EAClB,EAAM,KAAI,SAAC,EAAU,G,IAAR,EAAA,EAAA,EAAG,EAAA,EAAA,EAAW,OAAA,EAAI,EAAc,GAAG,EAAI,EAAI,EAAc,GAAG,C,KAE3E,OAAO,KAAK,MAAM,EAAW,EAC/B,E,yEFN8B,SAC5B,EACA,QAAA,IAAA,MAAA,IAEQ,IAAA,EAAA,EAAA,cAAA,IAAA,EAAA,IAAA,EACF,EAAW,EAAM,MAAM,EAAG,GAgBhC,OAfA,EAAM,MAAM,GAAG,SAAQ,SAAA,GACrB,IAAM,EAAY,EAAS,EAAS,OAAS,GACvC,EAAS,EAAc,EAAO,GACpC,GAAI,EAAS,EAGX,IAFA,IAAM,EAAe,KAAK,KAAK,EAAS,GAClC,EAAY,EAAS,EAClB,EAAI,EAAG,EAAI,EAAc,IAChC,EAAS,KACP,EAAkB,EAAO,GAAY,EAAI,GAAa,EAAI,UAI9D,EAAS,KAAK,E,IAGX,CACT,E,qFEL2C,SACzC,EACA,GAEA,IAAM,EAAQ,EAA4B,EAAO,GACjD,OAAO,EAAY,EAAO,EAC5B,E,+EC9D+B,SAC7B,EACA,EACA,QAAA,IAAA,MAAA,IAGE,IAAA,EAAA,EAAA,wBAAA,IAAA,EAAA,GAAA,EACA,EAAA,EAAA,iBAAA,IAAA,EAAA,GAAA,EACA,EAAA,EAAA,6BAAA,IAAA,EAAA,KAAA,GAAA,EACA,EAAA,EAAA,sBAAA,IAAA,KAEF,GAAI,KAAK,IAAI,GAAyB,KAAK,GACzC,MAAM,IAAI,MAAM,kDAElB,IAAM,EAAmB,EAAyB,EAAQ,CACxD,iBAAgB,IAEZ,EAAmB,EAAyB,EAAQ,CACxD,iBAAgB,IAGZ,EAAiB,KAAK,KAC1B,EAAY,GAAoB,EAAY,IAGxC,EAAgB,CAAC,GAEvB,GAAI,EAAgB,CAClB,IAAI,EAAkB,EACpB,EACA,GAGE,EAAkB,KAAK,KACzB,GAAoC,EAAI,KAAK,IAGzB,IAApB,GACA,KAAK,IAAI,GAAmB,GAE5B,EAAc,KAAK,GAErB,IAAK,IAAI,EAAI,EAAG,EAAI,EAAW,IAAK,CAClC,IAAM,GACH,EAAI,EACJ,EAAI,EAAI,GAA0B,EAAY,GAEnC,IAAV,GAAe,IAAU,KAAK,IAChC,EAAc,KAAK,E,EAKzB,IAAI,EAAiB,IASrB,OAPA,EAAc,SAAQ,SAAA,GACpB,IAAM,EAAgB,EAAY,EAAkB,GAC9C,EAAO,EAAgB,EAAe,GACxC,EAAO,IAAgB,EAAiB,E,IAIvC,KAAK,IAAI,EAAI,GAAkB,EAAiB,KAAK,KAAK,IAAK,EACxE,E","file":"/npm/curve-matcher@1.1.1/dist/index.umd.js","sourceRoot":"","sourcesContent":["/**\n * Minified by jsDelivr using Terser v5.39.0.\n * Original file: /npm/curve-matcher@1.1.1/dist/index.umd.js\n *\n * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files\n */\n","/** @hidden */\nexport const arrLast = (arr: T[]): T => arr[arr.length - 1];\n\n/** @hidden */\nexport const arrSum = (arr: number[]): number =>\n arr.reduce((acc, val) => acc + val, 0);\n\n/** @hidden */\nexport const arrAverage = (arr: number[]): number => {\n const sum = arr.reduce((acc, val) => val + acc, 0);\n return sum / arr.length;\n};\n","import { arrLast } from './utils';\n\nexport interface Point {\n x: number;\n y: number;\n}\n\nexport type Curve = Point[];\n\n/** @hidden */\nexport const subtract = (v1: Point, v2: Point): Point => ({\n x: v1.x - v2.x,\n y: v1.y - v2.y\n});\n\nconst magnitude = ({ x, y }: Point) => Math.sqrt(x * x + y * y);\n\n/**\n * Calculate the distance between 2 points\n * @param point1\n * @param point2\n */\nexport const pointDistance = (point1: Point, point2: Point) =>\n magnitude(subtract(point1, point2));\n\n/**\n * calculate the length of the curve\n * @param points\n */\nexport const curveLength = (points: Curve) => {\n let lastPoint = points[0];\n const pointsSansFirst = points.slice(1);\n return pointsSansFirst.reduce((acc, point) => {\n const dist = pointDistance(point, lastPoint);\n lastPoint = point;\n return acc + dist;\n }, 0);\n};\n\n/**\n * return a new point, p3, which is on the same line as p1 and p2, but away from p2\n * p1, p2, p3 will always lie on the line in that order (as long as dist is positive)\n * @param p1\n * @param p2\n * @param dist\n */\nexport const extendPointOnLine = (p1: Point, p2: Point, dist: number) => {\n const vect = subtract(p2, p1);\n const norm = dist / magnitude(vect);\n return { x: p2.x + norm * vect.x, y: p2.y + norm * vect.y };\n};\n\nexport interface SubdivideCurveOpts {\n maxLen?: number;\n}\n\n/**\n * Break up long segments in the curve into smaller segments of len maxLen or smaller\n * @param curve\n * @param options\n */\nexport const subdivideCurve = (\n curve: Curve,\n options: SubdivideCurveOpts = {}\n): Curve => {\n const { maxLen = 0.05 } = options;\n const newCurve = curve.slice(0, 1);\n curve.slice(1).forEach(point => {\n const prevPoint = newCurve[newCurve.length - 1];\n const segLen = pointDistance(point, prevPoint);\n if (segLen > maxLen) {\n const numNewPoints = Math.ceil(segLen / maxLen);\n const newSegLen = segLen / numNewPoints;\n for (let i = 0; i < numNewPoints; i++) {\n newCurve.push(\n extendPointOnLine(point, prevPoint, -1 * newSegLen * (i + 1))\n );\n }\n } else {\n newCurve.push(point);\n }\n });\n return newCurve;\n};\n\nexport interface RebalanceCurveOpts {\n numPoints?: number;\n}\n\n/**\n * Redraw the curve using `numPoints` points equally spaced along the length of the curve\n * This may result in a slightly different shape than the original if `numPoints` is low\n * @param curve\n * @param options\n */\nexport const rebalanceCurve = (\n curve: Curve,\n options: RebalanceCurveOpts\n): Curve => {\n const { numPoints = 50 } = options;\n const curveLen = curveLength(curve);\n const segmentLen = curveLen / (numPoints - 1);\n const outlinePoints = [curve[0]];\n const endPoint = arrLast(curve);\n const remainingCurvePoints = curve.slice(1);\n for (let i = 0; i < numPoints - 2; i++) {\n let lastPoint = arrLast(outlinePoints);\n let remainingDist = segmentLen;\n let outlinePointFound = false;\n while (!outlinePointFound) {\n const nextPointDist = pointDistance(lastPoint, remainingCurvePoints[0]);\n if (nextPointDist < remainingDist) {\n remainingDist -= nextPointDist;\n lastPoint = remainingCurvePoints.shift() as Point;\n } else {\n const nextPoint = extendPointOnLine(\n lastPoint,\n remainingCurvePoints[0],\n remainingDist - nextPointDist\n );\n outlinePoints.push(nextPoint);\n outlinePointFound = true;\n }\n }\n }\n outlinePoints.push(endPoint);\n return outlinePoints;\n};\n\n/**\n * Rotate the curve around the origin\n * @param curve\n * @param theta the angle to rotate by, in radians\n */\nexport const rotateCurve = (curve: Curve, theta: number): Curve => {\n return curve.map(point => ({\n x: Math.cos(-1 * theta) * point.x - Math.sin(-1 * theta) * point.y,\n y: Math.sin(-1 * theta) * point.x + Math.cos(-1 * theta) * point.y\n }));\n};\n","import { Curve, pointDistance } from './geometry';\n\n/**\n * Discrete Frechet distance between 2 curves\n * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf\n * modified to be iterative and have better memory usage\n */\nconst frechetDist = (curve1: Curve, curve2: Curve) => {\n const longCurve = curve1.length >= curve2.length ? curve1 : curve2;\n const shortCurve = curve1.length >= curve2.length ? curve2 : curve1;\n const calcVal = (\n i: number,\n j: number,\n prevResultsCol: number[],\n curResultsCol: number[]\n ): number => {\n if (i === 0 && j === 0) {\n return pointDistance(longCurve[0], shortCurve[0]);\n }\n if (i > 0 && j === 0) {\n return Math.max(\n prevResultsCol[0],\n pointDistance(longCurve[i], shortCurve[0])\n );\n }\n const lastResult = curResultsCol[curResultsCol.length - 1];\n if (i === 0 && j > 0) {\n return Math.max(lastResult, pointDistance(longCurve[0], shortCurve[j]));\n }\n\n return Math.max(\n Math.min(prevResultsCol[j], prevResultsCol[j - 1], lastResult),\n pointDistance(longCurve[i], shortCurve[j])\n );\n };\n\n let prevResultsCol: number[] = [];\n for (let i = 0; i < longCurve.length; i++) {\n const curResultsCol: number[] = [];\n for (let j = 0; j < shortCurve.length; j++) {\n // we only need the results from i - 1 and j - 1 to continue the calculation\n // so we only need to hold onto the last column of calculated results\n // prevResultsCol is results[i-1][:] in the original algorithm\n // curResultsCol is results[i][:j-1] in the original algorithm\n curResultsCol.push(calcVal(i, j, prevResultsCol, curResultsCol));\n }\n prevResultsCol = curResultsCol;\n }\n\n return prevResultsCol[shortCurve.length - 1];\n};\n\nexport default frechetDist;\n","import {\n Curve,\n Point,\n rebalanceCurve,\n rotateCurve,\n subtract\n} from './geometry';\nimport { arrAverage, arrSum } from './utils';\n\nexport interface ProcrustesNormalizeCurveOpts {\n rebalance?: boolean;\n estimationPoints?: number;\n}\n\n/**\n * Translate and scale curve by Procrustes Analysis\n *\n * Optionally runs [[rebalanceCurve]] first (default true)\n * from https://en.wikipedia.org/wiki/Procrustes_analysis\n * @param curve\n * @param options\n */\nexport const procrustesNormalizeCurve = (\n curve: Curve,\n options: ProcrustesNormalizeCurveOpts = {}\n): Curve => {\n const { rebalance = true, estimationPoints = 50 } = options;\n const balancedCurve = rebalance\n ? rebalanceCurve(curve, { numPoints: estimationPoints })\n : curve;\n const meanX = arrAverage(balancedCurve.map(point => point.x));\n const meanY = arrAverage(balancedCurve.map(point => point.y));\n const mean: Point = { x: meanX, y: meanY };\n const translatedCurve = balancedCurve.map(point => subtract(point, mean));\n const scale = Math.sqrt(\n arrAverage(translatedCurve.map(({ x, y }) => x * x + y * y))\n );\n return translatedCurve.map(point => ({\n x: point.x / scale,\n y: point.y / scale\n }));\n};\n\n/**\n * Find the angle to rotate `curve` to match the rotation of `relativeCurve` using procrustes analysis\n *\n * from https://en.wikipedia.org/wiki/Procrustes_analysis\n * `curve` and `relativeCurve` must have the same number of points\n * `curve` and `relativeCurve` should both be run through [[procrustesNormalizeCurve]] first\n * @param curve\n * @param relativeCurve\n */\nexport const findProcrustesRotationAngle = (\n curve: Curve,\n relativeCurve: Curve\n): number => {\n if (curve.length !== relativeCurve.length) {\n throw new Error('curve and relativeCurve must have the same length');\n }\n\n const numerator = arrSum(\n curve.map(({ x, y }, i) => y * relativeCurve[i].x - x * relativeCurve[i].y)\n );\n const denominator = arrSum(\n curve.map(({ x, y }, i) => x * relativeCurve[i].x + y * relativeCurve[i].y)\n );\n return Math.atan2(numerator, denominator);\n};\n\n/**\n * Rotate `curve` to match the rotation of `relativeCurve` using procrustes analysis\n *\n * from https://en.wikipedia.org/wiki/Procrustes_analysis\n * `curve` and `relativeCurve` must have the same number of points\n * `curve` and `relativeCurve` should both be run through [[procrustesNormalizeCurve]] first\n * @param curve\n * @param relativeCurve\n */\nexport const procrustesNormalizeRotation = (\n curve: Curve,\n relativeCurve: Curve\n): Curve => {\n const angle = findProcrustesRotationAngle(curve, relativeCurve);\n return rotateCurve(curve, angle);\n};\n","import frechetDistance from './frechetDistance';\nimport { Curve, curveLength, rotateCurve } from './geometry';\nimport {\n findProcrustesRotationAngle,\n procrustesNormalizeCurve\n} from './procrustesAnalysis';\n\nexport interface ShapeSimilarityOpts {\n estimationPoints?: number;\n checkRotations?: boolean;\n rotations?: number;\n restrictRotationAngle?: number;\n}\n\n/**\n * Estimate how similar the shapes of 2 curves are to each\n * accounting for translation, scale, and rotation\n * @param curve1\n * @param curve2\n * @param options\n * @returns between 1 and 0 depending on how similar the shapes are, where 1 means identical.\n */\nexport const shapeSimilarity = (\n curve1: Curve,\n curve2: Curve,\n options: ShapeSimilarityOpts = {}\n): number => {\n const {\n estimationPoints = 50,\n rotations = 10,\n restrictRotationAngle = Math.PI,\n checkRotations = true\n } = options;\n if (Math.abs(restrictRotationAngle) > Math.PI) {\n throw new Error('restrictRotationAngle cannot be larger than PI');\n }\n const normalizedCurve1 = procrustesNormalizeCurve(curve1, {\n estimationPoints\n });\n const normalizedCurve2 = procrustesNormalizeCurve(curve2, {\n estimationPoints\n });\n\n const geoAvgCurveLen = Math.sqrt(\n curveLength(normalizedCurve1) * curveLength(normalizedCurve2)\n );\n\n const thetasToCheck = [0];\n\n if (checkRotations) {\n let procrustesTheta = findProcrustesRotationAngle(\n normalizedCurve1,\n normalizedCurve2\n );\n // use a negative rotation rather than a large positive rotation\n if (procrustesTheta > Math.PI) {\n procrustesTheta = procrustesTheta - 2 * Math.PI;\n }\n if (\n procrustesTheta !== 0 &&\n Math.abs(procrustesTheta) < restrictRotationAngle\n ) {\n thetasToCheck.push(procrustesTheta);\n }\n for (let i = 0; i < rotations; i++) {\n const theta =\n -1 * restrictRotationAngle +\n (2 * i * restrictRotationAngle) / (rotations - 1);\n // 0 and Math.PI are already being checked, no need to check twice\n if (theta !== 0 && theta !== Math.PI) {\n thetasToCheck.push(theta);\n }\n }\n }\n\n let minFrechetDist = Infinity;\n // check some other thetas here just in case the procrustes theta isn't the best rotation\n thetasToCheck.forEach(theta => {\n const rotatedCurve1 = rotateCurve(normalizedCurve1, theta);\n const dist = frechetDistance(rotatedCurve1, normalizedCurve2);\n if (dist < minFrechetDist) minFrechetDist = dist;\n });\n\n // divide by Math.sqrt(2) to try to get the low results closer to 0\n return Math.max(1 - minFrechetDist / (geoAvgCurveLen / Math.sqrt(2)), 0);\n};\n\nexport default shapeSimilarity;\n"]}