2e:null 2f:["$","title",null,{"children":"Bézier Segment Arclength | Jacob Rus | Observable"}] 34:T8ff,plot = { viewof update_points; const p = viewof curve_bez.value; const svgheight = 400; const svgwidth = Math.min(600, width); const svg = d3.select(DOM.svg(svgwidth, svgheight)) .attr('style', `background-color: ${colors.palegray};`); const stretch = svg.append("g") .attr("fill", "none") .attr("stroke", colors.red) .selectAll("path") .data([[p[0], p[1]], [p[2], p[3]]]) .enter().append("path") .attr("d", d => `M${d[0][0]},${d[0][1]} L${d[1][0]},${d[1][1]}`); const bezier = svg.append("path") .attr("fill", "none") .attr("stroke-width", "1.5px") .attr("stroke", colors.blue); const controlpoint = svg.append("g") .attr("cursor", "move") .attr("pointer-events", "all") .attr("stroke", "transparent") .attr("stroke-width", 30) .selectAll("circle") .data(p) .enter().append("circle") .attr("r", (d, i) => (i === 1 || i === 2) ? 5 : 6) .attr("fill", (d, i) => (i === 1 || i === 2) ? colors.red : colors.black) .call(d3.drag() .subject(([x, y]) => ({x, y})) .on("drag", dragged)); const point = svg.append("g") .selectAll("circle") .data([0, 1]) .enter().append("circle") .attr("r", 4) .attr("fill", (d, i) => (i === 1) ? colors.green : colors.purple); function dragged(d) { d[0] = clamp(d3.event.x, 0, svgwidth); d[1] = clamp(d3.event.y, 0, svgheight); viewof curve_bez.value = viewof curve_bez.value; // Dispatches an input event! } function update() { controlpoint.attr("cx", d => d[0]).attr("cy", d => d[1]); stretch.attr("d", d => `M${d[0][0]},${d[0][1]} L${d[1][0]},${d[1][1]}`); bezier.attr("d", `M${p[0][0]},${p[0][1]} C${p[1][0]},${p[1][1]},${p[2][0]},${p[2][1]},${p[3][0]},${p[3][1]}`); point.attr("cx", d => viewof curve_points.value[d][0]).attr("cy", d => viewof curve_points.value[d][1]); } update(); // Listen for input events until the cell is disposed. viewof curve_bez.addEventListener("input", update); viewof curve_points.addEventListener("input", update); return Generators.disposable(svg.node(), () => { viewof curve_bez.removeEventListener("input", update); viewof curve_points.removeEventListener("input", update); }); return svg.node(); }35:T997,arclength_plot = { viewof update_points; const svgheight = 400; const svgwidth = Math.min(width, 600); const margin = {top:10, bottom: 10, left: 10, right: 10} const svg = d3.select(DOM.svg(svgwidth, svgheight)); const ymax = arclengthdata[arclengthdata.length-1][1]; const y = d3.scaleLinear().domain([0, ymax]).range([svgheight-margin.top, margin.bottom]) const x = d3.scaleLinear().domain([0, 1]).range([margin.left, svgwidth-margin.right]) const linear_reference = svg.append("path") .datum([[0,0], [1, ymax]]) .attr("fill", "none") .attr("stroke", colors.gray) .attr("stroke-width", 1) .attr("stroke-dasharray", "10 5") .attr("d", d3.line().x(d => x(d[0])).y(d => y(d[1]))); const curve = svg.append("path") .datum(arclengthdata) .attr("fill", "none") .attr("stroke", colors.red) .attr("stroke-width", 1.5) .attr("d", d3.line().x(d => x(d[0])).y(d => y(d[1]))); const point_segments = svg.append("g") .selectAll("path") .data([0, 1]) .enter().append("path") .attr("fill", "none") .attr("stroke", (d, i) => (i === 1) ? colors.green : colors.purple) .attr("stroke-width", 1.5) .attr("stroke-dasharray", "5 5"); const point = svg.append("g") .selectAll("circle") .data([0, 1]) .enter().append("circle") .attr("r", 4) .attr("fill", (d, i) => (i === 1) ? colors.green : colors.purple); function update() { point .attr("cx", d => x(viewof arclength_plot_points.value[d][0])) .attr("cy", d => y(viewof arclength_plot_points.value[d][1])); point_segments .attr("d", (d, i) => { const pts = viewof arclength_plot_points.value; const p0x = pts[0][0]; const p0y = pts[1][1]; return `M${x(p0x)},${y(p0y)} L${x(pts[d][0])},${y(pts[d][1])}` }); } update(); // Listen for input events until the cell is disposed. viewof arclength_plot_points.addEventListener("input", update); return Generators.disposable( html`

Parameter value vs. arclength.
Total arclength: ${ymax.toFixed(1)} pixels

${svg.node()}

`, () => {viewof arclength_plot_points.removeEventListener("input", update);}); return }36:T667,md` [Bézier curves][bezier] are one of the most common tools used in computer graphics for drawing arbitrary curves. A Bézier curve is a parametric curve which is defined by a polynomial, typically a cubic polynomial. (For more about Bézier curves in general see [Mike “Pomax” Kamermans][pomax]’s extensive [primer][].) A cubic Bézier curve has a simple user interface, made of two endpoints and two intermediate control points which determine the curve’s tangents at the endpoints. The curve moves relatively predictably in response to movements of the control points. The curve is defined as an [affine combination of the control points][ramshaw], which means it is invariant under affine transformations such as scaling, rotation, stretching, or skew. It is very simple to compute, because evaluating polynomials only requires a few addition and multiplication operations. Because of these advantages, as well as widespread availability of existing implementations, Bézier curves are used ubiquitously. However, some apparently simple applications still turn out to be surprisingly mathematically complicated. One of these is calculating the total [arclength][] of a Bézier curve. Another is traversing a Bézier curve at a constant speed, for example to move a camera in a computer game, or to draw a dotted line with evenly spaced dots. [bezier]: https://en.wikipedia.org/wiki/Bézier_curve [pomax]: https://twitter.com/TheRealPomax [primer]: https://pomax.github.io/bezierinfo [ramshaw]: http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-169.html [arclength]: https://en.wikipedia.org/wiki/Arc_length `37:T531,dotted_lines = { const p = viewof curve_bez.value; const svgheight = 244; const svgwidth = 640; const svg = d3.select(DOM.svg(svgwidth, svgheight)); const xbounds = bounding_box(curve_cheb[0]); const ybounds = bounding_box(curve_cheb[1]); const maxbound = Math.max(ybounds[1] - ybounds[0], xbounds[1] - xbounds[0]) const y = d3.scaleLinear() .domain([.5 * (ybounds[0] + ybounds[1] - maxbound), .5 * (ybounds[0] + ybounds[1] + maxbound)]) .range([2, 242]); const x = d3.scaleLinear() .domain([.5 * (xbounds[0] + xbounds[1] - maxbound), .5 * (xbounds[0] + xbounds[1] + maxbound)]) .range([50, 290]); const k = 20; const parameter_uniform = svg.append("g") .selectAll("circle") .data(d3.range(-k,k+1).map(d => d/k)) .enter().append("circle") .attr("fill", "#a046d2").attr("r", 2.5) .attr("cx", d => x(chebeval(curve_cheb[0], d))) .attr("cy", d => y(chebeval(curve_cheb[1], d))); const arclength_uniform = svg.append("g") .selectAll("circle") .data(d3.range(-k,k+1).map( d => 2 * chebeval(inversearclength_coeffs, d/k) - 1)) .enter().append("circle") .attr("fill", "#039d53").attr("r", 2.5) .attr("cx", d => 300 + x(chebeval(curve_cheb[0], d))) .attr("cy", d => y(chebeval(curve_cheb[1], d))); return svg.node(); }38:T68e,bernstein_vs_chebyshev = { const svgheight = 200; const svgwidth = 320; const margin = {top:10, bottom: 10, left: 10, right: 10} const pts = chebpts(129); const bsvg = d3.select(DOM.svg(svgwidth, svgheight)); const csvg = d3.select(DOM.svg(svgwidth, svgheight)); const by = d3.scaleLinear().domain([0, 1]).range([svgheight-margin.top, margin.bottom]) const bx = d3.scaleLinear().domain([-1, 1]).range([margin.left, svgwidth-margin.right]) const cy = d3.scaleLinear().domain([-1, 1]).range([svgheight-margin.top, margin.bottom]) const cx = d3.scaleLinear().domain([-1, 1]).range([margin.left, svgwidth-margin.right]) const bline = d3.line().x(d => bx(d[0])).y(d => by(d[1])); const cline = d3.line().x(d => cx(d[0])).y(d => cy(d[1])); const cdata = [[1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1]]; const bdata = [[10,-15,6,-1], [6,-3,-6,3], [6,3,-6,-3], [10,15,6,1]]; const bcurve = bsvg.append("g") .attr("fill", "none").attr("stroke-width", 1.5) .selectAll("path") .data(bdata) .enter().append("path") .attr("d", d => bline(pts.map(p => [p, 1/32 * chebeval(d, p)]))) .attr("stroke", (d, i) => d3.schemeCategory10[i]); const ccurve = csvg.append("g") .attr("fill", "none").attr("stroke-width", 1.5) .selectAll("path") .data(cdata) .enter().append("path") .attr("d", d => cline(pts.map(p => [p, chebeval(d, p)]))) .attr("stroke", (d, i) => d3.schemeCategory10[i]); return html`

${bsvg.node()}
Bernstein basis

${csvg.node()}
Chebyshev basis

` }39:T459,md` The [\`bez3_to_cheb\`](#bez3_to_cheb) function uses matrix multiplication to convert a cubic Bézier curve with control points ${$`(b_0, b_1, b_2, b_3)`} (usually considered to be a parametric curve with parameter ${$`t \in [0, 1]`}) into coefficients ${$`(c_0, c_1, c_2, c_3)`} of Chebyshev-basis polynomials (for ${$`x`} and ${$`y`}) over the domain ${$`[-1, 1]`}. ${$$` \begin{pmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{pmatrix} = \frac{1}{32} \begin{pmatrix} 10 & 6 & 6 & 10 \\ -15 & -3 & 3 & 15 \\ 6 & -6 & -6 & 6 \\ -1 & 3 & -3 & 1 \\ \end{pmatrix} \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix} `} The Bézier curve control point coordinates ${$`(b_0, b_1, b_2, b_3)`} are coefficients of the associated polynomial in [Bernstein basis][bern]. We could combine the steps of converting to Chebyshev basis and differentiating into a single matrix and save some arithmetic (since we only ever use the derivatives), but this is such a trivial fraction of the total calculation in this notebook that it’s not worth the trouble. [bern]: http://mae.engr.ucdavis.edu/~farouki/bernstein.pdf `3a:[] 32:{"id":"e11adde37f958474","slug":"bezier-segment-arclength","title":"Bézier Segment Arclength","thumbnail":"4855c3f123b6e732a9312f28aeeeb7bd4076f6ff1d81cc2d4c877c229f7b9bc1","access_level":"public","create_time":"$D2018-05-08T08:50:56.007Z","update_time":"$D2021-01-23T23:11:46.221Z","view_time":null,"first_public_time":"$D2018-05-08T09:46:22.084Z","has_unpublished_edits":null,"fork":{"id":"b0a7c91b138bbbdb","slug":"bezier-segment","title":"Bézier Segment","owner":{"id":"9b8a8e177a49059a","login":"jrus","name":"Jacob Rus"}},"stars":12,"starred":false,"owner":{"type":"team","id":"9b8a8e177a49059a","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":"starter_2024"},"version":1539,"publish_version":1539,"role":null,"authored":false,"authors":[{"type":"individual","id":"ddd7235babc79ce0","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":null}],"members":[{"type":"individual","id":"ddd7235babc79ce0","login":"jrus","name":"Jacob Rus","avatar_url":"https://avatars-next.observableusercontent.com/c33dbeed76527c50e64208b0e005e0b6e54a3bef2a14ea6a823f1c7de4867662","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"ce36252cf4ce1a72","slug":"bezier-curves","title":"Bézier curves","owner":{"id":"9b8a8e177a49059a","login":"jrus","name":"Jacob Rus"}},"type":"notebook","body":{"title":"Bézier Segment Arclength","cells":[{"id":0,"value":"Title = md`\n# Bézier Segment Arclength\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1201,"value":"md`\n(Drag the black ${draw_bullet(colors.black)} and red ${draw_bullet(colors.red)}\ncontrol points in the plot above. While the animation is running, the green\npoint ${draw_bullet(colors.green)} moves with uniform speed with respect to\narclength, while the purple point ${draw_bullet(colors.purple)} moves with\nuniform speed with respect to the parameter.)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"viewof speed = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1011,"value":"{\n const text = [\"Start Animation\", \"Stop Animation\"]\n let animate = true;\n const button = html``\n button.addEventListener('click', () => { animate = !animate; button.value = text[+animate]; })\n yield button\n while (true) {\n if (animate) viewof param.value = (viewof param.value + 1 + (speed)) % 1;\n yield button\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1113,"value":"md`\n* * *\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":754,"value":"Introduction = md`## Introduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1135,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1294,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1300,"value":"md`\nThere is no simple closed-form expression for the arclength of a cubic Bézier\ncurve, and so we must turn to approximation techniques. In this notebook,\nwe use a degree ${npts-1} [polynomial in Chebyshev basis to approximate][chebfun] the\narclength as a function of the parameter. This is a high enough degree to ensure\nthat the results are accurate to a tiny fraction of a pixel, but accuracy depends\non which specific curve we choose, and for full floating point accuracy we could\nsplit the curve into smaller pieces or use a polynomial of higher degree.\n\nWe can use [Newton’s method][newton] on our approximation to find the\ninverse, i.e. find which parameter value to use to obtain a curve segment\nof the desired arclength. If we like we can then make another high-degree\npolynomial approximation to our inverse function.\n\n [chebfun]: http://www.chebfun.org\n [newton]: https://en.wikipedia.org/wiki/Newton%27s_method\n\n* * *\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":922,"value":"Code = md `## Code and Explanation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":936,"value":"md`\nFirst define a [\\`View\\`][view] of a list of control point coordinates, named [\\`curve_bez\\`](#curve_bez),\nto represent our Bézier curve drawn in the plot at the top of the page:\n\n [view]: https://beta.observablehq.com/@mbostock/synchronized-views#View\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"viewof curve_bez = new View([[177,316],[494,361],[346,66],[243,251]])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":719,"value":"md`\nWe switch representations and from here onward use the [Chebyshev polynomial][cheb]\nbasis for our arithmetic, because it is efficient and convenient to work with.\nThe [\\`curve_cheb\\`](#curve_cheb) cell has two arrays of coefficients for cubic polynomials\n${$`x(t)`} and ${$`y(t)`}. For more about this conversion, see below\nfunction [see below](#bernstein_vs_chebyshev).\n\n(Quick aside: Chebyshev polynomials are defined relative to a domain of\n${$`[-1, 1]`}, while the parameter for a Bézier curve is typically considered\nto be ${$`t \\in [0, 1]`}, so there is occasional minor bookkeeping in the following\ncode to map between the intervals ${$`[0, 1]`} and ${$`[-1, 1]`}, as necessary.)\n\n [cheb]: https://en.wikipedia.org/wiki/Chebyshev_polynomials\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":983,"value":"curve_cheb = bez3_to_cheb(curve_bez)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1255,"value":"md`Use a power of 2 for the degree of our polynomial approximations:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":985,"value":"npts = 0x81 // n = 2^k + 1","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":987,"value":"md`\nThe derivative of arclength with respect to the parameter can be found by taking the\nderivative in the ${$`x`} and ${$`y`} directions separately, and then using the Pythagorean\nTheorem:\n\n${$$`\\begin{aligned}\ns^\\prime(t)^2 &= x^\\prime(t)^2 + y^\\prime(t)^2 \\\\\ns^\\prime(t) &= \\sqrt{x^\\prime(t)^2 + y^\\prime(t)^2}\n\\end{aligned}`}\n\nThe \\`darclength\\` cell contains the coefficients\nin Chebyshev basis of a degree ${npts - 1} polynomial approximation to the derivative of\narclength of our Bézier curve with respect to the parameter.\n\nTo find this approximation, we first evaluate the derivatives ${$`x^\\prime(t)`} and ${$`y^\\prime(t)`}\nat ${npts} appropriately-spaced points, sum their squares, and take a square root,\nand then use a [discrete cosine transform][dct] ([\\`vals2coeffs\\`](/@jrus/cheb#vals2coeffs))\nto obtain the coefficients.\n\n [dct]: https://en.wikipedia.org/wiki/Discrete_cosine_transform\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"darclength = {\n const [x, y] = curve_cheb;\n const pts = chebpts(npts);\n const Dx = diff(x), Dy = diff(y);\n return vals2coeffs(pts.map(p => {\n const Dxp = chebeval(Dx, p), Dyp = chebeval(Dy, p);\n return Math.sqrt(Dxp*Dxp + Dyp*Dyp);\n }));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":729,"value":"md`\nThen we can integrate using [\\`cumsum\\`](/@jrus/cheb#cumsum) to get the arclength\nfrom the starting point to the target point as a function of the parameter:\n\n${$$`s(t) = \\int_0^t{\\sqrt{x^\\prime(u)^2 + y^\\prime(u)^2}\\,\\mathrm{d}u}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":458,"value":"arclength = {\n const arclength = cumsum(darclength);\n arclength.splice(-1); // Keep using power-of-2 degree polynomial.\n return arclength;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1405,"value":"md`Use [\\`sum\\`](/@jrus/cheb#sum) for a definite integral.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":687,"value":"total_arclength = sum(darclength)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":564,"value":"md`\nTo invert our polynomial approximation, we just use Newton’s method. It\ntypically only takes a few evaluations to converge to a reasonable tolerance.\nIn some cases the first couple iterations of Newton’s method take us outside\nthe interval over which the curve is well-defined, so in those cases fall\nback to [bisection][].\n\nFor some discussion of using a combination of Newton’s method and bisection to invert arclength of parametric curves, see David Eberly (2007), [“Moving Along a Curve with Specified Speed”][eberly].\n\n [bisection]: https://en.wikipedia.org/wiki/Bisection_method\n [eberly]: https://www.geometrictools.com/Documentation/MovingAlongCurveSpecifiedSpeed.pdf\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":455,"value":"inversearclength = function inversearclength (s0) {\n const eps = 1e-8;\n if (s0 <= 0) return 0;\n if (s0 >= total_arclength) return 1;\n\n let bounds = [-1, 1];\n let t = 2 * s0 / total_arclength - 1; // For initial guess, assume a straight line.\n let s = chebeval(arclength, t) - s0; // distance along curve from target to guess\n let ds = chebeval(darclength, t);\n bounds[+(s > 0)] = t; // Establish initial interval.\n \n for (let i = 0; i < 20 && Math.abs(s) > eps; i++) {\n t = t - s / ds;\n if (t <= bounds[0] || t >= bounds[1]) // If out of bounds, bisect.\n t = (bounds[0] + bounds[1])*.5;\n s = chebeval(arclength, t) - s0;\n ds = chebeval(darclength, t);\n bounds[+(s > 0)] = t;\n }\n \n return (t + 1) * .5; // Use convention of t in [0, 1].\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":853,"value":"md`\nWe can invert at a number of points and approximate the inverse function as \nanother polynomial. If we need to invert many points, this is less computationally\nexpensive than inverting each point separately using Newton’s method.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":567,"value":"inversearclength_coeffs = {\n const vals = chebpts(npts).map(\n p => inversearclength(.5 * (p + 1) * total_arclength));\n return vals2coeffs(vals);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1259,"value":"md`\nIf we like we could even compose this function with the original Bézier curve\nto obtain a parametric polynomial which traces the original curve at a fixed\nspeed.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1332,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":798,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"bez3_to_cheb = function bez3_to_cheb([b0, b1, b2, b3]) {\n const denom = 1/32;\n const [b00, b01] = b0, [b10, b11] = b1, [b20, b21] = b2, [b30, b31] = b3;\n return [[\n ( 10*b00 + 6*b10 + 6*b20 + 10*b30) * denom,\n (-15*b00 - 3*b10 + 3*b20 + 15*b30) * denom,\n ( 6*b00 - 6*b10 - 6*b20 + 6*b30) * denom,\n ( -b00 + 3*b10 - 3*b20 + b30) * denom\n ], [\n ( 10*b01 + 6*b11 + 6*b21 + 10*b31) * denom,\n (-15*b01 - 3*b11 + 3*b21 + 15*b31) * denom,\n ( 6*b01 - 6*b11 - 6*b21 + 6*b31) * denom,\n ( -b01 + 3*b11 - 3*b21 + b31) * denom\n ]];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":902,"value":"md`* * *`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":927,"value":"Implementation_Details = md`## Implementation Details`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":827,"value":"md`\nImport a handful of tools for working with polynomials in Chebyshev basis.\nSee the [\\`@jrus/cheb\\`](/@jrus/cheb) notebook for more about Chebyshev polynomials:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"import {evaluate as chebeval, diff, cumsum, sum, coeffs2vals, vals2coeffs, chebpts} from \"@jrus/cheb\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":889,"value":"md`\nDefine [\\`$\\`](#$) and [\\`$$\\`](#$$) templates for LaTeX, which reference the stylesheet\nin the [\\`Title\\`](#Title) cell which shrinks the math fonts to match the text fonts\n(this explicit reference prevents issues with vertical alignment). The names\n\\`$\\` and \\`$$\\` are also more convenient than \\`tex\\` and \\`tex.block\\`:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1475,"value":"import {math_css, $, $$} with {$css as $css} from \"@jrus/misc\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1481,"value":"$$css = html`${math_css}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":883,"value":"md`Import [D3](https://d3js.org) for plotting:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":898,"value":"md`\nImport [Mike Bostock](/@mbostock/)’s [\\`View\\`](/@mbostock/synchronized-views#View) class, useful for making\ninteractive plots which share data with the rest of the notebook:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"import {View} from \"@mbostock/synchronized-views\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1228,"value":"colors = ({\n \"blue\": \"#08e\",\n \"red\": \"#d03\",\n \"green\": \"#039d53\", \n \"purple\": \"#9046d2\",\n \"gray\": \"#c6c6c6\",\n \"black\": \"#000\",\n \"palegray\": \"#fafafc\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1409,"value":"md`\nThe [\\`draw_bullet\\`](#draw_bullet) function draws ${draw_bullet(colors.blue)}\nlittle ${draw_bullet(colors.green)} colored ${draw_bullet(colors.black)} dots \n${draw_bullet(colors.purple)} inline with our text.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1239,"value":"draw_bullet = function draw_bullet(color) {\n const svg = d3.select(DOM.svg(10, 10));\n svg.append(\"circle\")\n .attr(\"fill\", color).attr(\"r\", 4)\n .attr(\"cx\", 5).attr(\"cy\", 5);\n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"md`Here’s a list of pairs ${$`(t, s(t))`} for use drawing the plot at the top of the notebook:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"arclengthdata = {\n const vals = coeffs2vals(arclength);\n return chebpts(arclength.length).map(\n (p,i) => [(p+1)*.5, vals[i]]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":996,"value":"md`These views are used in the plots at the top of the notebook:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":997,"value":"viewof curve_points = new View([null, null])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1048,"value":"viewof param = new View(0.5)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":999,"value":"viewof arclength_plot_points = new View([null, null])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1001,"value":"viewof update_points = {\n const\n t1 = param,\n t1_ = t1 * 2 - 1,\n t2 = chebeval(inversearclength_coeffs, t1_),\n t2_ = t2 * 2 - 1;\n viewof arclength_plot_points.value = [\n [t1, chebeval(arclength, t1_)],\n [t2, chebeval(arclength, t2_)]]\n viewof curve_points.value = [\n [chebeval(curve_cheb[0], t1_), chebeval(curve_cheb[1], t1_)],\n [chebeval(curve_cheb[0], t2_), chebeval(curve_cheb[1], t2_)]];\n return {\n \"Bezier Plot\": viewof curve_points.value,\n \"Arclength Plot\": viewof arclength_plot_points.value};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1268,"value":"clamp = function clamp(x, min, max) {\n return (x < min) ? min : (x > max) ? max : x;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1272,"value":"md`Find the minimum and maximum over ${$`[-1, 1]`} of a cubic polynomial in Chebyshev basis:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1266,"value":"bounding_box = function bounding_box(cubic_cheb) {\n const x = cubic_cheb, Dx = diff(x);\n const extrema = [chebeval(x, -1), chebeval(x, 1)];\n \n // Use quadratic formula to find roots of Dx and Dy in [-1, 1].\n // Combine with endpoints, then take min/max.\n const a = - Dx[1] - Math.sqrt(Dx[1]*Dx[1] - 8*Dx[2]*(Dx[0]-Dx[2]));\n if (!isNaN(a)) {\n extrema.push(\n chebeval(x, clamp(a / (4 * Dx[2]), -1, 1)),\n chebeval(x, clamp(2 * (Dx[0]-Dx[2]) / a, -1, 1)));\n }\n return [Math.min(...extrema), Math.max(...extrema)];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 33:"$32:body"