Help with understanding some code (Bezier curves)

Hi, I’m working on an app that has a drawing canvas, and there’s a react native package called luncheon/simplify-svg-path, which simplifies strokes (sets of points) into Bezier curves. Does anyone with some calculus knowledge know what’s going on in the below code? (Comments were left by the creator. I attached the full file, but it’s quite long)

index.js (11.8 KB)

// Use least-squares method to find Bezier control points for region.
const generateBezier = (points, first, last, uPrime, tan1, tan2) => {
const epsilon = /#=/ EPSILON, abs = Math.abs, pt1 = points[first], pt2 = points[last],
// Create the C and X matrices
C = [
[0, 0],
[0, 0],
], X = [0, 0];
for (let i = 0, l = last - first + 1; i < l; i++) {
const u = uPrime[i], t = 1 - u, b = 3 * u * t, b0 = t * t * t, b1 = b * t, b2 = b * u, b3 = u * u * u, a1 = tan1._normalize(b1), a2 = tan2._normalize(b2), tmp = points[first + i]._subtract(pt1._multiply(b0 + b1))._subtract(pt2._multiply(b2 + b3));
C[0][0] += a1._dot(a1);
C[0][1] += a1._dot(a2);
// C[1][0] += a1.dot(a2);
C[1][0] = C[0][1];
C[1][1] += a2._dot(a2);
X[0] += a1._dot(tmp);
X[1] += a2._dot(tmp);
}
// Compute the determinants of C and X
const detC0C1 = C[0][0] * C[1][1] - C[1][0] * C[0][1];
let alpha1;
let alpha2;
if (abs(detC0C1) > epsilon) {
// Kramer’s rule
const detC0X = C[0][0] * X[1] - C[1][0] * X[0], detXC1 = X[0] * C[1][1] - X[1] * C[0][1];
// Derive alpha values
alpha1 = detXC1 / detC0C1;
alpha2 = detC0X / detC0C1;
}
else {
// Matrix is under-determined, try assuming alpha1 == alpha2
const c0 = C[0][0] + C[0][1], c1 = C[1][0] + C[1][1];
alpha1 = alpha2 = abs(c0) > epsilon ? X[0] / c0 : abs(c1) > epsilon ? X[1] / c1 : 0;
}
// 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.
const segLength = pt2._getDistance(pt1), eps = epsilon * segLength;
let handle1, handle2;
if (alpha1 < eps || alpha2 < eps) {
// fall back on standard (probably inaccurate) formula,
// and subdivide further if needed.
alpha1 = alpha2 = segLength / 3;
}
else {
// Check if the found control points are in the right order when
// projected onto the line through pt1 and pt2.
const line = pt2._subtract(pt1);
// Control points 1 and 2 are positioned an alpha distance out
// on the tangent vectors, left and right, respectively
handle1 = tan1._normalize(alpha1);
handle2 = tan2._normalize(alpha2);
if (handle1._dot(line) - handle2._dot(line) > segLength * segLength) {
// Fall back to the Wu/Barsky heuristic above.
alpha1 = alpha2 = segLength / 3;
handle1 = handle2 = null; // Force recalculation
}
}
// First and last control points of the Bezier curve are
// positioned exactly at the first and last data points
return [pt1, pt1._add(handle1 || tan1._normalize(alpha1)), pt2._add(handle2 || tan2._normalize(alpha2)), pt2];
};

Thanks!

If you google “bezier curve”, you get this Wikipedia page.

I know what a Bezier curve is, I just want to understand what the code is doing. It says that it is using least-squares method. Is that minimizing the cost function or something?

It certainly sounds like that, but I don’t know anything about Bezier Curves other than how to google that. If you already know Bezier Curves, does the definition involve a least squares cost function?

I scanned the Wikipedia article and I don’t see any mention of least squares or a cost function.

But note in the comment that it says that it is using Least Squares to determine the Bezier control points. So there is some kind of higher level algorithm going on here. It is trying to solve an optimization to figure out what the Bezier Curve should be.

A little more googling finds this article on the MathWorks site.

Sorry, maybe I didn’t make it clear. I know already that its trying to fit a Bezier Curve. Basically, given a set of points (x,y,t), where t is a timestamp, it tries to fit a cubic bezier curve to it. If you can understand what the code is doing, can you explain? Thanks.