Brunobkr/llama.cpp_AlgMor24_github

1export type Point = [number, number];2 3// distance between 2 points4function distance(p1: Point, p2: Point): number {5  return Math.sqrt(distanceSq(p1, p2));6}7 8// distance between 2 points squared9function distanceSq(p1: Point, p2: Point): number {10  return Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2);11}12 13// Sistance squared from a point p to the line segment vw14function distanceToSegmentSq(p: Point, v: Point, w: Point): number {15  const l2 = distanceSq(v, w);16  if (l2 === 0) {17    return distanceSq(p, v);18  }19  let t = ((p[0] - v[0]) * (w[0] - v[0]) + (p[1] - v[1]) * (w[1] - v[1])) / l2;20  t = Math.max(0, Math.min(1, t));21  return distanceSq(p, lerp(v, w, t));22}23 24function lerp(a: Point, b: Point, t: number): Point {25  return [26    a[0] + (b[0] - a[0]) * t,27    a[1] + (b[1] - a[1]) * t,28  ];29}30 31// Adapted from https://seant23.wordpress.com/2010/11/12/offset-bezier-curves/32function flatness(points: Point[], offset: number): number {33  const p1 = points[offset + 0];34  const p2 = points[offset + 1];35  const p3 = points[offset + 2];36  const p4 = points[offset + 3];37 38  let ux = 3 * p2[0] - 2 * p1[0] - p4[0]; ux *= ux;39  let uy = 3 * p2[1] - 2 * p1[1] - p4[1]; uy *= uy;40  let vx = 3 * p3[0] - 2 * p4[0] - p1[0]; vx *= vx;41  let vy = 3 * p3[1] - 2 * p4[1] - p1[1]; vy *= vy;42 43  if (ux < vx) {44    ux = vx;45  }46 47  if (uy < vy) {48    uy = vy;49  }50 51  return ux + uy;52}53 54function getPointsOnBezierCurveWithSplitting(points: Point[], offset: number, tolerance: number, newPoints?: Point[]): Point[] {55  const outPoints = newPoints || [];56  if (flatness(points, offset) < tolerance) {57    const p0 = points[offset + 0];58    if (outPoints.length) {59      const d = distance(outPoints[outPoints.length - 1], p0);60      if (d > 1) {61        outPoints.push(p0);62      }63    } else {64      outPoints.push(p0);65    }66    outPoints.push(points[offset + 3]);67  } else {68    // subdivide69    const t = .5;70    const p1 = points[offset + 0];71    const p2 = points[offset + 1];72    const p3 = points[offset + 2];73    const p4 = points[offset + 3];74 75    const q1 = lerp(p1, p2, t);76    const q2 = lerp(p2, p3, t);77    const q3 = lerp(p3, p4, t);78 79    const r1 = lerp(q1, q2, t);80    const r2 = lerp(q2, q3, t);81 82    const red = lerp(r1, r2, t);83 84    getPointsOnBezierCurveWithSplitting([p1, q1, r1, red], 0, tolerance, outPoints);85    getPointsOnBezierCurveWithSplitting([red, r2, q3, p4], 0, tolerance, outPoints);86  }87  return outPoints;88}89 90export function simplify(points: Point[], distance: number): Point[] {91  return simplifyPoints(points, 0, points.length, distance);92}93 94// Ramer–Douglas–Peucker algorithm95// https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm96function simplifyPoints(points: Point[], start: number, end: number, epsilon: number, newPoints?: Point[]): Point[] {97  const outPoints = newPoints || [];98 99  // find the most distance point from the endpoints100  const s = points[start];101  const e = points[end - 1];102  let maxDistSq = 0;103  let maxNdx = 1;104  for (let i = start + 1; i < end - 1; ++i) {105    const distSq = distanceToSegmentSq(points[i], s, e);106    if (distSq > maxDistSq) {107      maxDistSq = distSq;108      maxNdx = i;109    }110  }111 112  // if that point is too far, split113  if (Math.sqrt(maxDistSq) > epsilon) {114    simplifyPoints(points, start, maxNdx + 1, epsilon, outPoints);115    simplifyPoints(points, maxNdx, end, epsilon, outPoints);116  } else {117    if (!outPoints.length) {118      outPoints.push(s);119    }120    outPoints.push(e);121  }122 123  return outPoints;124}125 126export function pointsOnBezierCurves(points: Point[], tolerance: number = 0.15, distance?: number): Point[] {127  const newPoints: Point[] = [];128  const numSegments = (points.length - 1) / 3;129  for (let i = 0; i < numSegments; i++) {130    const offset = i * 3;131    getPointsOnBezierCurveWithSplitting(points, offset, tolerance, newPoints);132  }133  if (distance && distance > 0) {134    return simplifyPoints(newPoints, 0, newPoints.length, distance);135  }136  return newPoints;137}