function getPointAtLengthLookup(lengthLookup, length) {
let foundT = false;
let pt;
let {
points,
lengths
} = lengthLookup;
let [p0, cp1, cp2, p] = [points[0], points[1], points[2], points[3]];
let tStep = 1 / (lengths.length - 1);
let lengthTotal = lengths[lengths.length - 1];
if (length === 0) {
return p0;
}
if (length.toFixed(3) === lengthTotal.toFixed(3)) {
return p;
}
for (let i = 0; i < lengths.length && !foundT; i++) {
let lengthAtT = lengths[i];
let lengthAtTPrev = i > 0 ? lengths[i - 1] : lengths[i];
if (lengthAtT > length) {
let t = tStep * i;
let tSegLength = lengthAtT - lengthAtTPrev;
let diffLength = lengthAtT - length;
let tScale = (1 / tSegLength) * diffLength;
let newT = t - tStep * tScale;
foundT = true;
pt = getPointAtCubicSegmentT(p0, cp1, cp2, p, newT);
}
}
return pt;
}
function getPathLengthLookup(points, tDivisions = 10) {
let lengthLookup = {
points: points,
lengths: [],
diviations: []
};
let pL = points.length;
let p0 = points[0],
cp1 = points[1],
cp2,
p = points[pL - 1];
if (points.length === 4) {
cp2 = points[2];
}
let lengthCalc = cubicBezierLength(p0, cp1, cp2, p, 1);
for (let i = 0; i < tDivisions; i++) {
let t = (1 / tDivisions) * i;
let len = cubicBezierLength(p0, cp1, cp2, p, t);
lengthLookup.lengths.push(len);
}
lengthLookup.lengths.push(lengthCalc);
lengthLookup.diviations.push(0);
return lengthLookup;
}
function cubicBezierLength(p0, cp1, cp2, p, t = 1) {
if (t === 0) {
return 0;
}
const base3 = (t, p1, p2, p3, p4) => {
let t1 = -3 * p1 + 9 * p2 - 9 * p3 + 3 * p4,
t2 = t * t1 + 6 * p1 - 12 * p2 + 6 * p3;
return t * t2 - 3 * p1 + 3 * p2;
};
t = t > 1 ? 1 : t < 0 ? 0 : t;
let t2 = t / 2;
let Tvalues = [-0.1252,
0.1252, -0.3678,
0.3678, -0.5873,
0.5873, -0.7699,
0.7699, -0.9041,
0.9041, -0.9816,
0.9816
];
let Cvalues = [
0.2491,
0.2491,
0.2335,
0.2335,
0.2032,
0.2032,
0.1601,
0.1601,
0.1069,
0.1069,
0.0472,
0.0472
];
let n = Tvalues.length;
let sum = 0;
for (let i = 0; i < n; i++) {
let ct = t2 * Tvalues[i] + t2,
xbase = base3(ct, p0.x, cp1.x, cp2.x, p.x),
ybase = base3(ct, p0.y, cp1.y, cp2.y, p.y),
comb = xbase * xbase + ybase * ybase;
sum += Cvalues[i] * Math.sqrt(comb);
}
return t2 * sum;
}
function quadraticBezierLength(p0, cp1, p, t = 1) {
if (t === 0) {
return 0;
}
const interpolate = (p1, p2, t) => {
let pt = {
x: (p2.x - p1.x) * t + p1.x,
y: (p2.y - p1.y) * t + p1.y
};
return pt;
};
const getLineLength = (p1, p2) => {
return Math.sqrt(
(p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)
);
};
let l1 = getLineLength(p0, cp1) + getLineLength(cp1, p);
let l2 = getLineLength(p0, p);
if (l1 === l2) {
let m1 = interpolate(p0, cp1, t);
let m2 = interpolate(cp1, p, t);
p = interpolate(m1, m2, t);
let lengthL;
lengthL = Math.sqrt(
(p.x - p0.x) * (p.x - p0.x) + (p.y - p0.y) * (p.y - p0.y)
);
return lengthL;
}
let a, b, c, d, e, e1, d1, v1x, v1y;
v1x = cp1.x * 2;
v1y = cp1.y * 2;
d = p0.x - v1x + p.x;
d1 = p0.y - v1y + p.y;
e = v1x - 2 * p0.x;
e1 = v1y - 2 * p0.y;
a = 4 * (d * d + d1 * d1);
b = 4 * (d * e + d1 * e1);
c = e * e + e1 * e1;
const bt = b / (2 * a),
ct = c / a,
ut = t + bt,
k = ct - bt ** 2;
return (
(Math.sqrt(a) / 2) *
(ut * Math.sqrt(ut ** 2 + k) -
bt * Math.sqrt(bt ** 2 + k) +
k *
Math.log((ut + Math.sqrt(ut ** 2 + k)) / (bt + Math.sqrt(bt ** 2 + k))))
);
}
function getLineLength(p1, p2) {
return Math.sqrt(
(p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)
);
}
function interpolatedPoint(p1, p2, t = 0.5) {
if (Array.isArray(p1)) {
p1.x = p1[0];
p1.y = p1[1];
}
if (Array.isArray(p2)) {
p2.x = p2[0];
p2.y = p2[1];
}
let [x, y] = [(p2.x - p1.x) * t + p1.x, (p2.y - p1.y) * t + p1.y];
return {
x: x,
y: y
};
}
function getPointAtCubicSegmentT(p0, cp1, cp2, p, t = 0.5) {
let t1 = 1 - t;
return {
x: t1 ** 3 * p0.x +
3 * t1 ** 2 * t * cp1.x +
3 * t1 * t ** 2 * cp2.x +
t ** 3 * p.x,
y: t1 ** 3 * p0.y +
3 * t1 ** 2 * t * cp1.y +
3 * t1 * t ** 2 * cp2.y +
t ** 3 * p.y
};
}
function renderPoint(
svg,
coords,
fill = "red",
r = "2",
opacity = "1",
id = "",
className = ""
) {
if (Array.isArray(coords)) {
coords = {
x: coords[0],
y: coords[1]
};
}
let marker = `<circle class="${className}" opacity="${opacity}" id="${id}" cx="${coords.x}" cy="${coords.y}" r="${r}" fill="${fill}">
<title>${coords.x} ${coords.y}</title></circle>`;
svg.insertAdjacentHTML("beforeend", marker);
}
<p>
<label>t division <span id="spanT"></span><input class="inputs" id="inpT" type="range" value="36" min="5" max="72" step="1"></label>
<label>points on path <span id="spanPoints"></span><input class="inputs" id="inpPoints" type="range" value="10" min="5" max="500" step="1"></label>
</p>
<p><strong>Performance:</strong> native: <span id="perfN"></span> calculated:<span id="perfC"></span></p>
<svg id="svg" viewBox="0 0 300 300 " style="border:1px solid #ccc">
<path id="path" d="" stroke="#999" fill="none" stroke-width="1%"></path>
<g id="segs"></g>
</svg>
<script>
window.addEventListener('DOMContentLoaded', e => {
let p0 = {
x: 150,
y: 50
},
cp1 = {
x: 400,
y: 100
},
cp2 = {
x: -200,
y: 200
},
p = {
x: 150,
y: 250
};
path.setAttribute(
"d",
`M${p0.x} ${p0.y} C ${cp1.x} ${cp1.y} ${cp2.x} ${cp2.y} ${p.x} ${p.y}`
);
let length = path.getTotalLength();
let lengthCalc = cubicBezierLength(p0, cp1, cp2, p, 1);
let inputs = document.querySelectorAll('.inputs')
inputs.forEach(input=>{
input.addEventListener('input', e=>{
renderPointsatLength(p0, cp1, cp2, p)
});
})
renderPointsatLength(p0, cp1, cp2, p)
function renderPointsatLength(p0, cp1, cp2, p) {
let tDivision = +inpT.value;
spanT.textContent = tDivision
segs.innerHTML = '';
let lengthLookup = getPathLengthLookup([p0, cp1, cp2, p], tDivision);
let {
points,
lengths
} = lengthLookup;
let steps = +inpPoints.value;
spanPoints.textContent = steps;
let ptsN = [];
let ptsC = [];
let t0 = performance.now();
for (let i = 0; i <= steps; i++) {
let pt = path.getPointAtLength((lengthCalc / steps) * i);
ptsN.push(pt);
}
let end0 = +(performance.now() - t0).toFixed(8) + " ms";
perfN.textContent = end0
let t1 = performance.now();
for (let i = 0; i <= steps; i++) {
let totalLength = lengths[lengths.length - 1];
let pt = getPointAtLengthLookup(lengthLookup, (totalLength / steps) * i);
ptsC.push(pt);
}
let end1 = +(performance.now() - t1).toFixed(8) + " ms";
perfC.textContent = end1
ptsN.forEach(pt => {
renderPoint(segs, pt, "black", "1.2%");
})
ptsC.forEach(pt => {
renderPoint(segs, pt, "red", "1.2%");
})
}
})
</script>
