aboutsummaryrefslogtreecommitdiff
path: root/src/client/util/bezierFit.ts
diff options
context:
space:
mode:
Diffstat (limited to 'src/client/util/bezierFit.ts')
-rw-r--r--src/client/util/bezierFit.ts401
1 files changed, 221 insertions, 180 deletions
diff --git a/src/client/util/bezierFit.ts b/src/client/util/bezierFit.ts
index 8fc6de6f9..d6f3f2340 100644
--- a/src/client/util/bezierFit.ts
+++ b/src/client/util/bezierFit.ts
@@ -1,4 +1,8 @@
-import { Point } from "../../pen-gestures/ndollar";
+/* eslint-disable no-use-before-define */
+/* eslint-disable prefer-destructuring */
+/* eslint-disable no-param-reassign */
+/* eslint-disable camelcase */
+import { Point } from '../../pen-gestures/ndollar';
class SmartRect {
minx: number = 0;
@@ -6,20 +10,43 @@ class SmartRect {
maxx: number = 0;
maxy: number = 0;
- constructor(mix: number = 0, miy: number = 0, max: number = 0, may: number = 0) { this.minx = mix; this.miny = miy; this.maxx = max; this.maxy = may; }
+ constructor(mix: number = 0, miy: number = 0, max: number = 0, may: number = 0) {
+ this.minx = mix;
+ this.miny = miy;
+ this.maxx = max;
+ this.maxy = may;
+ }
- public get Center() { return new Point((this.maxx + this.minx) / 2.0, (this.maxy + this.miny) / 2.0); }
- public get TopLeft() { return new Point(this.minx, this.miny); }
- public get TopRight() { return new Point(this.maxx, this.miny); }
- public get BotLeft() { return new Point(this.minx, this.maxy); }
- public get BotRight() { return new Point(this.maxx, this.maxy); }
- public get Width() { return this.maxx - this.minx; }
- public get Height() { return this.maxy - this.miny; }
- public static Intersect(a: SmartRect, b: SmartRect) { return a.Intersect(b); }
- public Intersect(b: SmartRect) { return !((this.minx > b.maxx) || (this.miny > b.maxy) || (b.minx > this.maxx) || (b.miny > this.maxy)); }
+ public get Center() {
+ return new Point((this.maxx + this.minx) / 2.0, (this.maxy + this.miny) / 2.0);
+ }
+ public get TopLeft() {
+ return new Point(this.minx, this.miny);
+ }
+ public get TopRight() {
+ return new Point(this.maxx, this.miny);
+ }
+ public get BotLeft() {
+ return new Point(this.minx, this.maxy);
+ }
+ public get BotRight() {
+ return new Point(this.maxx, this.maxy);
+ }
+ public get Width() {
+ return this.maxx - this.minx;
+ }
+ public get Height() {
+ return this.maxy - this.miny;
+ }
+ public static Intersect(a: SmartRect, b: SmartRect) {
+ return a.Intersect(b);
+ }
+ public Intersect(b: SmartRect) {
+ return !(this.minx > b.maxx || this.miny > b.maxy || b.minx > this.maxx || b.miny > this.maxy);
+ }
public ContainsPercentage(other: SmartRect, axis: Point) {
- var ret = 0;
+ let ret = 0;
const minx = Math.max(other.TopLeft.X * axis.X + other.TopLeft.Y * axis.Y, this.TopLeft.X * axis.X + this.TopLeft.Y * axis.Y);
const maxx = Math.max(other.BotRight.X * axis.X + other.BotRight.Y * axis.Y, this.BotRight.X * axis.X + this.BotRight.Y * axis.Y);
ret = maxx > minx ? (maxx - minx) / (axis === new Point(1, 0) ? other.Width : other.Height) : 0;
@@ -36,7 +63,7 @@ class SmartRect {
if (r.minx > r.maxx) [r.minx, r.maxx] = [r.maxx, r.minx];
if (r.miny > r.maxy) [r.miny, r.maxy] = [r.maxy, r.miny];
- for (const pt of p) {
+ p.forEach(pt => {
if (pt.X < r.minx) {
r.minx = pt.X;
} else if (pt.X > r.maxx) {
@@ -47,7 +74,7 @@ class SmartRect {
} else if (pt.Y > r.maxy) {
r.maxy = pt.Y;
}
- }
+ });
}
return r;
}
@@ -64,18 +91,18 @@ export function Normalize(p: Point) {
function ReparameterizeBezier(d: Point[], first: number, last: number, u: number[], bezCurve: Point[]) {
const uPrime = new Array<number>(last - first + 1); // New parameter values
- for (var i = first; i <= last; i++) {
+ for (let i = first; i <= last; i++) {
uPrime[i - first] = NewtonRaphsonRootFind(bezCurve, d[i], u[i - first]);
}
return uPrime;
}
function ComputeMaxError(d: Point[], first: number, last: number, bezCurve: Point[], u: number[]) {
- var maxError = 0; // Maximum error
- var splitPoint2D = (last - first + 1) / 2;
- for (var i = first + 1; i < last; i++) {
- const P = [0, 0]; // point on curve
+ let maxError = 0; // Maximum error
+ let splitPoint2D = (last - first + 1) / 2;
+ for (let i = first + 1; i < last; i++) {
+ const P = [0, 0]; // point on curve
EvalBezierFast(bezCurve, u[i - first], P);
- const dx = P[0] - d[i].X;// offset from point to curve
+ const dx = P[0] - d[i].X; // offset from point to curve
const dy = P[1] - d[i].Y;
const dist = Math.sqrt(dx * dx + dy * dy); // Current error
if (dist >= maxError) {
@@ -88,11 +115,11 @@ function ComputeMaxError(d: Point[], first: number, last: number, bezCurve: Poin
return { maxError, splitPoint2D };
}
function ChordLengthParameterize(d: Point[], first: number, last: number) {
- const u = new Array<number>(last - first + 1);// Parameterization
+ const u = new Array<number>(last - first + 1); // Parameterization
- var prev = 0.0;
+ let prev = 0.0;
u[0] = prev;
- for (var i = first + 1; i <= last; i++) {
+ for (let i = first + 1; i <= last; i++) {
const lastd = d[i - 1];
const curd = d[i];
const dx = lastd.X - curd.X;
@@ -101,27 +128,38 @@ function ChordLengthParameterize(d: Point[], first: number, last: number) {
}
const ulastfirst = u[last - first];
- for (var i = first + 1; i <= last; i++) {
+ for (let i = first + 1; i <= last; i++) {
u[i - first] /= ulastfirst;
}
return u;
}
/*
-* B0, B1, B2, B3 :
-* Bezier multipliers
-*/
-function B0(u: number) { const tmp = 1.0 - u; return tmp * tmp * tmp; }
-function B1(u: number) { const tmp = 1.0 - u; return 3 * u * tmp * tmp; }
-function B2(u: number) { const tmp = 1.0 - u; return 3 * u * u * tmp; }
-function B3(u: number) { return u * u * u; }
+ * B0, B1, B2, B3 :
+ * Bezier multipliers
+ */
+function B0(u: number) {
+ const tmp = 1.0 - u;
+ return tmp * tmp * tmp;
+}
+function B1(u: number) {
+ const tmp = 1.0 - u;
+ return 3 * u * tmp * tmp;
+}
+function B2(u: number) {
+ const tmp = 1.0 - u;
+ return 3 * u * u * tmp;
+}
+function B3(u: number) {
+ return u * u * u;
+}
function bounds(p: Point[]) {
const r = new SmartRect(p[0].X, p[0].Y, p[3].X, p[3].Y); // These are the most likely to be extremal
- if (r.minx > r.maxx) (r.minx, r.maxx);
+ if (r.minx > r.maxx) [r.minx, r.maxx] = [r.maxx, r.minx];
if (r.miny > r.maxy) [r.miny, r.maxy] = [r.maxy, r.miny]; // swap min & max
- for (var i = 1; i < 3; i++) {
+ for (let i = 1; i < 3; i++) {
if (p[i].X < r.minx) r.minx = p[i].X;
else if (p[i].X > r.maxx) r.maxx = p[i].X;
@@ -131,37 +169,36 @@ function bounds(p: Point[]) {
return r;
}
-
function splitCubic(p: Point[], t: number, left: Point[], right: Point[]) {
const sz = 4;
const Vtemp = new Array<Array<Point>>(4);
- for (var i = 0; i < 4; i++) Vtemp[i] = new Array<Point>(4);
+ for (let i = 0; i < 4; i++) Vtemp[i] = new Array<Point>(4);
/* Copy control points */
// std::copy(p.begin(), p.end(), Vtemp[0]);
- for (var i = 0; i < sz; i++) {
+ for (let i = 0; i < sz; i++) {
Vtemp[0][i].X = p[i].X;
Vtemp[0][i].Y = p[i].Y;
}
/* Triangle computation */
- for (var i = 1; i < sz; i++) {
- for (var j = 0; j < sz - i; j++) {
+ for (let i = 1; i < sz; i++) {
+ for (let j = 0; j < sz - i; j++) {
const a = Vtemp[i - 1][j];
const b = Vtemp[i - 1][j + 1];
Vtemp[i][j].X = b.X * t + a.X * (1 - t);
- Vtemp[i][j].Y = b.Y * t + a.Y * (1 - t); // Vtemp[i][j] = Point2D::Lerp(Vtemp[i - 1][j], Vtemp[i - 1][j + 1], t);
+ Vtemp[i][j].Y = b.Y * t + a.Y * (1 - t); // Vtemp[i][j] = Point2D::Lerp(Vtemp[i - 1][j], Vtemp[i - 1][j + 1], t);
}
}
if (left) {
- for (var j = 0; j < sz; j++) {
+ for (let j = 0; j < sz; j++) {
left[j].X = Vtemp[j][0].X;
left[j].Y = Vtemp[j][0].Y;
}
}
if (right) {
- for (var j = 0; j < sz; j++) {
+ for (let j = 0; j < sz; j++) {
right[j].X = Vtemp[sz - 1 - j][j].X;
right[j].Y = Vtemp[sz - 1 - j][j].Y;
}
@@ -169,51 +206,54 @@ function splitCubic(p: Point[], t: number, left: Point[], right: Point[]) {
}
/*
-* Recursively intersect two curves keeping track of their real parameters
-* and depths of intersection.
-* The results are returned in a 2-D array of doubles indicating the parameters
-* for which intersections are found. The parameters are in the order the
-* intersections were found, which is probably not in sorted order.
-* When an intersection is found, the parameter value for each of the two
-* is stored in the index elements array, and the index is incremented.
-*
-* If either of the curves has subdivisions left before it is straight
-* (depth > 0)
-* that curve (possibly both) is (are) subdivided at its (their) midpoint(s).
-* the depth(s) is (are) decremented, and the parameter value(s) corresponding
-* to the midpoints(s) is (are) computed.
-* Then each of the subcurves of one curve is intersected with each of the
-* subcurves of the other curve, first by testing the bounding boxes for
-* interference. If there is any bounding box interference, the corresponding
-* subcurves are recursively intersected.
-*
-* If neither curve has subdivisions left, the line segments from the first
-* to last control point of each segment are intersected. (Actually the
-* only the parameter value corresponding to the intersection point is found).
-*
-* The apriori flatness test is probably more efficient than testing at each
-* level of recursion, although a test after three or four levels would
-* probably be worthwhile, since many curves become flat faster than their
-* asymptotic rate for the first few levels of recursion.
-*
-* The bounding box test fails much more frequently than it succeeds, providing
-* substantial pruning of the search space.
-*
-* Each (sub)curve is subdivided only once, hence it is not possible that for
-* one final line intersection test the subdivision was at one level, while
-* for another final line intersection test the subdivision (of the same curve)
-* was at another. Since the line segments share endpoints, the intersection
-* is robust: a near-tangential intersection will yield zero or two
-* intersections.
-*/
+ * Recursively intersect two curves keeping track of their real parameters
+ * and depths of intersection.
+ * The results are returned in a 2-D array of doubles indicating the parameters
+ * for which intersections are found. The parameters are in the order the
+ * intersections were found, which is probably not in sorted order.
+ * When an intersection is found, the parameter value for each of the two
+ * is stored in the index elements array, and the index is incremented.
+ *
+ * If either of the curves has subdivisions left before it is straight
+ * (depth > 0)
+ * that curve (possibly both) is (are) subdivided at its (their) midpoint(s).
+ * the depth(s) is (are) decremented, and the parameter value(s) corresponding
+ * to the midpoints(s) is (are) computed.
+ * Then each of the subcurves of one curve is intersected with each of the
+ * subcurves of the other curve, first by testing the bounding boxes for
+ * interference. If there is any bounding box interference, the corresponding
+ * subcurves are recursively intersected.
+ *
+ * If neither curve has subdivisions left, the line segments from the first
+ * to last control point of each segment are intersected. (Actually the
+ * only the parameter value corresponding to the intersection point is found).
+ *
+ * The apriori flatness test is probably more efficient than testing at each
+ * level of recursion, although a test after three or four levels would
+ * probably be worthwhile, since many curves become flat faster than their
+ * asymptotic rate for the first few levels of recursion.
+ *
+ * The bounding box test fails much more frequently than it succeeds, providing
+ * substantial pruning of the search space.
+ *
+ * Each (sub)curve is subdivided only once, hence it is not possible that for
+ * one final line intersection test the subdivision was at one level, while
+ * for another final line intersection test the subdivision (of the same curve)
+ * was at another. Since the line segments share endpoints, the intersection
+ * is robust: a near-tangential intersection will yield zero or two
+ * intersections.
+ */
+// eslint-disable-next-line @typescript-eslint/no-unused-vars
function recursively_intersect(a: Point[], t0: number, t1: number, deptha: number, b: Point[], u0: number, u1: number, depthb: number, parameters: number[][]) {
if (deptha > 0) {
- const a1 = new Array<Point>(4), a2 = new Array<Point>(4);
+ const a1 = new Array<Point>(4);
+ const a2 = new Array<Point>(4);
splitCubic(a, 0.5, a1, a2);
const tmid = (t0 + t1) * 0.5;
deptha--;
if (depthb > 0) {
- const b1 = new Array<Point>(4), b2 = new Array<Point>(4);
+ const b1 = new Array<Point>(4);
+ const b2 = new Array<Point>(4);
splitCubic(b, 0.5, b1, b2);
const umid = (u0 + u1) * 0.5;
depthb--;
@@ -229,8 +269,7 @@ function recursively_intersect(a: Point[], t0: number, t1: number, deptha: numbe
if (SmartRect.Intersect(bounds(a2), bounds(b2))) {
recursively_intersect(a2, tmid, t1, deptha, b2, umid, u1, depthb, parameters);
}
- }
- else {
+ } else {
if (SmartRect.Intersect(bounds(a1), bounds(b))) {
recursively_intersect(a1, t0, tmid, deptha, b, u0, u1, depthb, parameters);
}
@@ -238,50 +277,45 @@ function recursively_intersect(a: Point[], t0: number, t1: number, deptha: numbe
recursively_intersect(a2, tmid, t1, deptha, b, u0, u1, depthb, parameters);
}
}
- }
+ } else if (depthb > 0) {
+ const b1 = new Array<Point>(4);
+ const b2 = new Array<Point>(4);
+ splitCubic(b, 0.5, b1, b2);
+ const umid = (u0 + u1) * 0.5;
+ depthb--;
+ if (SmartRect.Intersect(bounds(a), bounds(b1))) {
+ recursively_intersect(a, t0, t1, deptha, b1, u0, umid, depthb, parameters);
+ }
+ if (SmartRect.Intersect(bounds(a), bounds(b2))) {
+ recursively_intersect(a, t0, t1, deptha, b2, umid, u1, depthb, parameters);
+ }
+ } // Both segments are fully subdivided; now do line segments
else {
- if (depthb > 0) {
- const b1 = new Array<Point>(4), b2 = new Array<Point>(4);
- splitCubic(b, 0.5, b1, b2);
- const umid = (u0 + u1) * 0.5;
- depthb--;
- if (SmartRect.Intersect(bounds(a), bounds(b1))) {
- recursively_intersect(a, t0, t1, deptha, b1, u0, umid, depthb, parameters);
- }
- if (SmartRect.Intersect(bounds(a), bounds(b2))) {
- recursively_intersect(a, t0, t1, deptha, b2, umid, u1, depthb, parameters);
- }
+ const xlk = a[3].X - a[0].X;
+ const ylk = a[3].Y - a[0].Y;
+ const xnm = b[3].X - b[0].X;
+ const ynm = b[3].Y - b[0].Y;
+ const xmk = b[0].X - a[0].X;
+ const ymk = b[0].Y - a[0].Y;
+ const det = xnm * ylk - ynm * xlk;
+ if (1.0 + det === 1.0) {
+ return;
}
- else // Both segments are fully subdivided; now do line segments
- {
- const xlk = a[3].X - a[0].X;
- const ylk = a[3].Y - a[0].Y;
- const xnm = b[3].X - b[0].X;
- const ynm = b[3].Y - b[0].Y;
- const xmk = b[0].X - a[0].X;
- const ymk = b[0].Y - a[0].Y;
- const det = xnm * ylk - ynm * xlk;
- if (1.0 + det === 1.0) {
- return;
- }
- else {
- const detinv = 1.0 / det;
- const s = (xnm * ymk - ynm * xmk) * detinv;
- const t = (xlk * ymk - ylk * xmk) * detinv;
- if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0) || Number.isNaN(s) || Number.isNaN(t)) {
- return;
- }
- parameters.push([t0 + s * (t1 - t0), u0 + t * (u1 - u0)]);
- }
+ const detinv = 1.0 / det;
+ const s = (xnm * ymk - ynm * xmk) * detinv;
+ const t = (xlk * ymk - ylk * xmk) * detinv;
+ if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0 || isNaN(s) || isNaN(t)) {
+ return;
}
+ parameters.push([t0 + s * (t1 - t0), u0 + t * (u1 - u0)]);
}
}
/*
-* EvalBezier :
-* Evaluate a Bezier curve at a particular parameter value
-*
-*/
+ * EvalBezier :
+ * Evaluate a Bezier curve at a particular parameter value
+ *
+ */
const MAX_DEGREE = 5;
function EvalBezier(V: Point[], degree: number, t: number, result: number[]) {
if (degree + 1 > MAX_DEGREE) {
@@ -293,35 +327,36 @@ function EvalBezier(V: Point[], degree: number, t: number, result: number[]) {
const Vtemp = [new Point(0, 0), new Point(0, 0), new Point(0, 0), new Point(0, 0)]; // Local copy of control points
/* Copy array */
- for (var i = 0; i <= degree; i++) {
+ for (let i = 0; i <= degree; i++) {
Vtemp[i].X = V[i].X;
Vtemp[i].Y = V[i].Y;
}
/* Triangle computation */
- for (var i = 1; i <= degree; i++) {
- for (var j = 0; j <= degree - i; j++) {
+ for (let i = 1; i <= degree; i++) {
+ for (let j = 0; j <= degree - i; j++) {
Vtemp[j].X = (1.0 - t) * Vtemp[j].X + t * Vtemp[j + 1].X;
Vtemp[j].Y = (1.0 - t) * Vtemp[j].Y + t * Vtemp[j + 1].Y;
}
}
result[0] = Vtemp[0].X;
- result[1] = Vtemp[0].Y;// Point on curve at parameter t
+ result[1] = Vtemp[0].Y; // Point on curve at parameter t
}
function EvalBezierFast(p: Point[], t: number, result: number[]) {
const n = 3;
const u = 1.0 - t;
- var bc = 1, tn = 1;
- var tmpX = p[0].X * u;
- var tmpY = p[0].Y * u;
- tn = tn * t;
- bc = bc * (n - 1 + 1) / 1;
+ let bc = 1;
+ let tn = 1;
+ let tmpX = p[0].X * u;
+ let tmpY = p[0].Y * u;
+ tn *= t;
+ bc = (bc * (n - 1 + 1)) / 1;
tmpX = (tmpX + tn * bc * p[1].X) * u;
tmpY = (tmpY + tn * bc * p[1].Y) * u;
- tn = tn * t;
- bc = bc * (n - 2 + 1) / 2;
+ tn *= t;
+ bc = (bc * (n - 2 + 1)) / 2;
tmpX = (tmpX + tn * bc * p[2].X) * u;
tmpY = (tmpY + tn * bc * p[2].Y) * u;
@@ -329,9 +364,9 @@ function EvalBezierFast(p: Point[], t: number, result: number[]) {
result[1] = tmpY + tn * t * p[3].Y;
}
/*
-* ComputeLeftTangent, ComputeRightTangent, ComputeCenterTangent :
-*Approximate unit tangents at endpoints and "center" of digitized curve
-*/
+ * ComputeLeftTangent, ComputeRightTangent, ComputeCenterTangent :
+ *Approximate unit tangents at endpoints and "center" of digitized curve
+ */
function ComputeLeftTangent(d: Point[], end: number) {
const use = 1;
const tHat1 = new Point(d[end + use].X - d[end].X, d[end + use].Y - d[end].Y);
@@ -348,19 +383,19 @@ function ComputeCenterTangent(d: Point[], center: number) {
}
const V1 = ComputeLeftTangent(d, center); // d[center] - d[center-1];
const V2 = ComputeRightTangent(d, center); // d[center] - d[center + 1];
- var tHatCenter = new Point((-V1.X + V2.X) / 2.0, (-V1.Y + V2.Y) / 2.0);
+ let tHatCenter = new Point((-V1.X + V2.X) / 2.0, (-V1.Y + V2.Y) / 2.0);
if (tHatCenter === new Point(0, 0)) {
- tHatCenter = new Point(-V1.Y, -V1.X);// V1.Perp();
+ tHatCenter = new Point(-V1.Y, -V1.X); // V1.Perp();
}
return Normalize(tHatCenter);
}
function GenerateBezier(d: Point[], first: number, last: number, uPrime: number[], tHat1: Point, tHat2: Point, result: Point[] /* must be prealloacted to size 4 */) {
const nPts = last - first + 1; // Number of pts in sub-curve
- const Ax = new Array<number>(nPts * 2);// Precomputed rhs for eqn //std::vector<Vector2D> A(nPts * 2);
- const Ay = new Array<number>(nPts * 2);// Precomputed rhs for eqn //std::vector<Vector2D> A(nPts * 2);
+ const Ax = new Array<number>(nPts * 2); // Precomputed rhs for eqn //std::vector<Vector2D> A(nPts * 2);
+ const Ay = new Array<number>(nPts * 2); // Precomputed rhs for eqn //std::vector<Vector2D> A(nPts * 2);
/* Compute the A's */
- for (var i = 0; i < nPts; i++) {
+ for (let i = 0; i < nPts; i++) {
const uprime = uPrime[i];
const b1 = B1(uprime);
const b2 = B2(uprime);
@@ -371,39 +406,42 @@ function GenerateBezier(d: Point[], first: number, last: number, uPrime: number[
}
/* Create the C and X matrices */
- const C = [[0, 0], [0, 0]];
+ const C = [
+ [0, 0],
+ [0, 0],
+ ];
const df = d[first];
const dl = d[last];
- const X = [0, 0]; // Matrix X
- for (var i = 0; i < nPts; i++) {
- C[0][0] += Ax[i] * Ax[i] + Ay[i] * Ay[i]; //A[i+0*nPts].Dot(A[i+0*nPts]);
- C[0][1] += Ax[i] * Ax[i + nPts] + Ay[i] * Ay[i + nPts];//A[i+0*nPts].Dot(A[i+1*nPts]);
+ const X = [0, 0]; // Matrix X
+ for (let i = 0; i < nPts; i++) {
+ C[0][0] += Ax[i] * Ax[i] + Ay[i] * Ay[i]; // A[i+0*nPts].Dot(A[i+0*nPts]);
+ C[0][1] += Ax[i] * Ax[i + nPts] + Ay[i] * Ay[i + nPts]; // A[i+0*nPts].Dot(A[i+1*nPts]);
C[1][0] = C[0][1];
- C[1][1] += Ax[i + nPts] * Ax[i + nPts] + Ay[i + nPts] * Ay[i + nPts];// A[i+1*nPts].Dot(A[i+1*nPts]);
+ C[1][1] += Ax[i + nPts] * Ax[i + nPts] + Ay[i + nPts] * Ay[i + nPts]; // A[i+1*nPts].Dot(A[i+1*nPts]);
const uprime = uPrime[i];
const b0plb1 = B0(uprime) + B1(uprime);
const b2plb3 = B2(uprime) + B3(uprime);
const df1 = d[first + i];
- const tmpX = df1.X - (df.X * b0plb1 + (dl.X * b2plb3));
- const tmpY = df1.Y - (df.Y * b0plb1 + (dl.Y * b2plb3));
+ const tmpX = df1.X - (df.X * b0plb1 + dl.X * b2plb3);
+ const tmpY = df1.Y - (df.Y * b0plb1 + dl.Y * b2plb3);
X[0] += Ax[i] * tmpX + Ay[i] * tmpY; // A[i+0*nPts].Dot(tmp)
- X[1] += Ax[i + nPts] * tmpX + Ay[i + nPts] * tmpY; //A[i+1*nPts].Dot(tmp)
+ X[1] += Ax[i + nPts] * tmpX + Ay[i + nPts] * tmpY; // A[i+1*nPts].Dot(tmp)
}
/* Compute the determinants of C and X */
- const det_C0_C1 = (C[0][0] * C[1][1] - C[1][0] * C[0][1]) || (C[0][0] * C[1][1]) * 10e-12;
+ const det_C0_C1 = C[0][0] * C[1][1] - C[1][0] * C[0][1] || C[0][0] * C[1][1] * 10e-12;
const det_C0_X = C[0][0] * X[1] - C[0][1] * X[0];
const det_X_C1 = X[0] * C[1][1] - X[1] * C[0][1];
/* Finally, derive alpha values */
- var alpha_l = (det_C0_C1 === 0) ? 0.0 : det_X_C1 / det_C0_C1;
- var alpha_r = (det_C0_C1 === 0) ? 0.0 : det_C0_X / det_C0_C1;
+ let alpha_l = det_C0_C1 === 0 ? 0.0 : det_X_C1 / det_C0_C1;
+ let alpha_r = det_C0_C1 === 0 ? 0.0 : det_C0_X / det_C0_C1;
/* If alpha negative, use the Wu/Barsky heuristic (see text) */
/* (if alpha is 0, you get coincident control points that lead to
- * divide by zero in any subsequent NewtonRaphsonRootFind() call. */
+ * divide by zero in any subsequent NewtonRaphsonRootFind() call. */
const segLength = Math.sqrt((df.X - dl.X) * (df.X - dl.X) + (df.Y - dl.Y) * (df.Y - dl.Y));
const epsilon = 1.0e-6 * segLength;
if (alpha_l < epsilon || alpha_r < epsilon) {
@@ -415,10 +453,10 @@ function GenerateBezier(d: Point[], first: number, last: number, uPrime: number[
/* positioned exactly at the first and last data points */
/* Control points 1 and 2 are positioned an alpha distance out */
/* on the tangent vectors, left and right, respectively */
- result[0] = df;// RETURN bezier curve ctl pts
+ result[0] = df; // RETURN bezier curve ctl pts
result[3] = dl;
- result[1] = new Point(df.X + (tHat1.X * alpha_l), df.Y + (tHat1.Y * alpha_l));
- result[2] = new Point(dl.X + (tHat2.X * alpha_r), dl.Y + (tHat2.Y * alpha_r));
+ result[1] = new Point(df.X + tHat1.X * alpha_l, df.Y + tHat1.Y * alpha_l);
+ result[2] = new Point(dl.X + tHat2.X * alpha_r, dl.Y + tHat2.Y * alpha_r);
}
/*
@@ -426,21 +464,24 @@ function GenerateBezier(d: Point[], first: number, last: number, uPrime: number[
* Use Newton-Raphson iteration to find better root.
*/
function NewtonRaphsonRootFind(Q: Point[], P: Point, u: number) {
- const Q1 = [new Point(0, 0), new Point(0, 0), new Point(0, 0)], Q2 = [new Point(0, 0), new Point(0, 0)]; // Q' and Q''
- const Q_u = [0, 0], Q1_u = [0, 0], Q2_u = [0, 0]; //u evaluated at Q, Q', & Q''
+ const Q1 = [new Point(0, 0), new Point(0, 0), new Point(0, 0)];
+ const Q2 = [new Point(0, 0), new Point(0, 0)]; // Q' and Q''
+ const Q_u = [0, 0];
+ const Q1_u = [0, 0];
+ const Q2_u = [0, 0]; // u evaluated at Q, Q', & Q''
/* Compute Q(u) */
- var uPrime: number; // Improved u
+ let uPrime: number; // Improved u
EvalBezierFast(Q, u, Q_u);
/* Generate control vertices for Q' */
- for (var i = 0; i <= 2; i++) {
+ for (let i = 0; i <= 2; i++) {
Q1[i].X = (Q[i + 1].X - Q[i].X) * 3.0;
Q1[i].Y = (Q[i + 1].Y - Q[i].Y) * 3.0;
}
/* Generate control vertices for Q'' */
- for (var i = 0; i <= 1; i++) {
+ for (let i = 0; i <= 1; i++) {
Q2[i].X = (Q1[i + 1].X - Q1[i].X) * 2.0;
Q2[i].Y = (Q1[i + 1].Y - Q1[i].Y) * 2.0;
}
@@ -450,20 +491,20 @@ function NewtonRaphsonRootFind(Q: Point[], P: Point, u: number) {
EvalBezier(Q2, 1, u, Q2_u);
/* Compute f(u)/f'(u) */
- const numerator = (Q_u[0] - P.X) * (Q1_u[0]) + (Q_u[1] - P.Y) * (Q1_u[1]);
- const denominator = (Q1_u[0]) * (Q1_u[0]) + (Q1_u[1]) * (Q1_u[1]) + (Q_u[0] - P.X) * (Q2_u[0]) + (Q_u[1] - P.Y) * (Q2_u[1]);
+ const numerator = (Q_u[0] - P.X) * Q1_u[0] + (Q_u[1] - P.Y) * Q1_u[1];
+ const denominator = Q1_u[0] * Q1_u[0] + Q1_u[1] * Q1_u[1] + (Q_u[0] - P.X) * Q2_u[0] + (Q_u[1] - P.Y) * Q2_u[1];
if (denominator === 0.0) {
uPrime = u;
- } else uPrime = u - (numerator / denominator);/* u = u - f(u)/f'(u) */
+ } else uPrime = u - numerator / denominator; /* u = u - f(u)/f'(u) */
return uPrime;
}
function FitCubic(d: Point[], first: number, last: number, tHat1: Point, tHat2: Point, error: number, result: Point[]) {
- const bezCurve = new Array<Point>(4); // Control points of fitted Bezier curve
- const maxIterations = 4; // Max times to try iterating
+ const bezCurve = new Array<Point>(4); // Control points of fitted Bezier curve
+ const maxIterations = 4; // Max times to try iterating
const iterationError = error * error; // Error below which you try iterating
- const nPts = last - first + 1; // Number of points in subset
+ const nPts = last - first + 1; // Number of points in subset
/* Use heuristic if region only has two points in it */
if (nPts === 2) {
@@ -471,8 +512,8 @@ function FitCubic(d: Point[], first: number, last: number, tHat1: Point, tHat2:
bezCurve[0] = d[first];
bezCurve[3] = d[last];
- bezCurve[1] = new Point(bezCurve[0].X + (tHat1.X * dist), bezCurve[0].Y + (tHat1.Y * dist));
- bezCurve[2] = new Point(bezCurve[3].X + (tHat2.X * dist), bezCurve[3].Y + (tHat2.Y * dist));
+ bezCurve[1] = new Point(bezCurve[0].X + tHat1.X * dist, bezCurve[0].Y + tHat1.Y * dist);
+ bezCurve[2] = new Point(bezCurve[3].X + tHat2.X * dist, bezCurve[3].Y + tHat2.Y * dist);
result.push(bezCurve[1]);
result.push(bezCurve[2]);
@@ -481,11 +522,11 @@ function FitCubic(d: Point[], first: number, last: number, tHat1: Point, tHat2:
}
/* Parameterize points, and attempt to fit curve */
- var u = ChordLengthParameterize(d, first, last);
+ let u = ChordLengthParameterize(d, first, last);
GenerateBezier(d, first, last, u, tHat1, tHat2, bezCurve);
/* Find max deviation of points to fitted curve */
- const { maxError, splitPoint2D } = ComputeMaxError(d, first, last, bezCurve, u); // Maximum fitting error
+ const { maxError, splitPoint2D } = ComputeMaxError(d, first, last, bezCurve, u); // Maximum fitting error
if (maxError < Math.abs(error)) {
result.push(bezCurve[1]);
result.push(bezCurve[2]);
@@ -496,11 +537,11 @@ function FitCubic(d: Point[], first: number, last: number, tHat1: Point, tHat2:
/* If error not too large, try some reparameterization */
/* and iteration */
if (maxError < iterationError) {
- for (var i = 0; i < maxIterations; i++) {
- const uPrime = ReparameterizeBezier(d, first, last, u, bezCurve); // Improved parameter values
+ for (let i = 0; i < maxIterations; i++) {
+ const uPrime = ReparameterizeBezier(d, first, last, u, bezCurve); // Improved parameter values
GenerateBezier(d, first, last, uPrime, tHat1, tHat2, bezCurve);
- const { maxError } = ComputeMaxError(d, first, last, bezCurve, uPrime);
- if (maxError < error) {
+ const { maxError: maximumError } = ComputeMaxError(d, first, last, bezCurve, uPrime);
+ if (maximumError < error) {
result.push(bezCurve[1]);
result.push(bezCurve[2]);
result.push(bezCurve[3]);
@@ -527,13 +568,13 @@ export function FitOneCurve(d: Point[], tHat1?: Point, tHat2?: Point) {
tHat1 = tHat1 ?? Normalize(ComputeLeftTangent(d, 0));
tHat2 = tHat2 ?? Normalize(ComputeRightTangent(d, d.length - 1));
tHat2 = new Point(-tHat2.X, -tHat2.Y);
- var u = ChordLengthParameterize(d, 0, d.length - 1);
+ let u = ChordLengthParameterize(d, 0, d.length - 1);
const bezCurveCtrls = [new Point(0, 0), new Point(0, 0), new Point(0, 0), new Point(0, 0)];
- GenerateBezier(d, 0, d.length - 1, u, tHat1, tHat2, bezCurveCtrls); /* Find max deviation of points to fitted curve */
- var finalCtrls = bezCurveCtrls.slice();
- var { maxError: error } = ComputeMaxError(d, 0, d.length - 1, bezCurveCtrls, u);
- for (var i = 0; i < 10; i++) {
- const uPrime = ReparameterizeBezier(d, 0, d.length - 1, u, bezCurveCtrls); // Improved parameter values
+ GenerateBezier(d, 0, d.length - 1, u, tHat1, tHat2, bezCurveCtrls); /* Find max deviation of points to fitted curve */
+ let finalCtrls = bezCurveCtrls.slice();
+ let { maxError: error } = ComputeMaxError(d, 0, d.length - 1, bezCurveCtrls, u);
+ for (let i = 0; i < 10; i++) {
+ const uPrime = ReparameterizeBezier(d, 0, d.length - 1, u, bezCurveCtrls); // Improved parameter values
GenerateBezier(d, 0, d.length - 1, uPrime, tHat1, tHat2, bezCurveCtrls);
const { maxError } = ComputeMaxError(d, 0, d.length - 1, bezCurveCtrls, uPrime);
if (maxError < error) {
@@ -1428,4 +1469,4 @@ spliceR[0] += v;
}
#endif
-*/ \ No newline at end of file
+*/
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-10-07 18:24:15 +0000