31:T411,html``32:[] 2f:{"title":"Fourier Series - Path Sampling","cells":[{"id":0,"value":"md`# Fourier Series - Path Sampling\n\nWhen computing the [Fourier series](/@mbostock/fourier-series-zoom) of a two-dimensional path, it makes a difference how you sample the points! That’s because the series isn’t simply reconstructing the path: it’s reconstructing a parametric function ${tex`f : t \\mapsto \\langle x,y \\rangle`}. If you change how ${tex`t`} varies along the path, say if the path moves slower or faster in certain sections, you’ll change the resulting Fourier series.\n\nOne way to sample points on a path in SVG is to use [*path*.getPointAtLength](https://developer.mozilla.org/en-US/docs/Web/API/SVGGeometryElement/getPointAtLength) and [*path*.getTotalLength](https://developer.mozilla.org/en-US/docs/Web/API/SVGGeometryElement/getTotalLength). This makes it easy to sample points uniformly along the length of the path. For lack of a better term, we’ll call this *linear* sampling.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"M = 2000 // The number of samples. Try editing!","pinned":true,"hidden":false,"mode":"ojs"},{"id":223,"value":"linearSamples = {\n const L = path.getTotalLength();\n return Array.from({length: M}, (_, i) => {\n const {x, y} = path.getPointAtLength(i / M * L);\n return [x, y];\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":116,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":219,"value":"md`An alternative approach is to consider the piecewise representation of the path: in SVG, and most other vector graphics systems, a two-dimensional path is not a continuous curve but a series of connected segments. The type of segment can vary, but most often a segment is either linear (straight) or cubic Bézier (curved). The control points and tangents of the Bézier segments are shown below.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":236,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":278,"value":"md`Unlike the path as a whole, each segment *is* naturally represented as a parametric function ${tex`f : t \\mapsto \\langle x,y \\rangle`}. Given ${tex`0 \\leq t \\leq 1`}, a linear segment is defined as a function of two points ${tex`\\mathbf{P}_0`} and ${tex`\\mathbf{P}_1`}:\n\n${tex`\\mathbf{B}(t) = (1 - t) \\mathbf{P}_0 + t \\mathbf{P}_1`}\n\nAnd similarly a cubic Bézier segment is defined by four points:\n\n${tex`\\mathbf{B}(t) = (1 - t)^3 \\mathbf{P}_0 + 3 (1 - t)^2 t \\mathbf{P}_1 + 3 (1 - t) t^2 \\mathbf{P}_2 + t^3 \\mathbf{P}_3`}\n\nWhat does it look like if we sample uniformly in ${tex`t`} along each of these piecewise segments? (You can find the code in the appendix; it requires parsing the SVG path string as no browsers currently implement the [SVG Paths specification](https://svgwg.org/specs/paths/#InterfaceSVGPathData). This implementation is based on [Jarosław Foksa’s polyfill](https://github.com/jarek-foksa/path-data-polyfill).)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"pathSampler = new PathSampler(path.getAttribute(\"d\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":230,"value":"parametricSamples = Array.from({length: M}, (_, i) => pathSampler.pointAt(i / M))","pinned":true,"hidden":false,"mode":"ojs"},{"id":99,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":311,"value":"md`As you can see, the points are now more concentrated in the “interesting” squiggly parts with high curvature. The straightish parts, in contrast, have fewer samples. And thus parametric sampling is desirable for Fourier series (at least here) because it biases the approximation towards the important parts of the path at the expense of the unimportant parts.\n\nNeither of these approaches are optimal in terms of producing the most accurate approximation with the fewest number of Fourier series terms. Parametric sampling seems to work well in practice because we tend to use more segments to represent detailed paths, but surely there’s a more general importance sampling heuristic that works well with any path.\n\nThanks to [Stuart Jantzen](https://twitter.com/Biocinematics/status/1143334994175283201) for the portrait of Fourier, and [3Blue1Brown](https://www.youtube.com/watch?v=r6sGWTCMz2k) for the inspirational videos!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":157,"value":"md`---\n\n## Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"image = fetch(\"https://gist.githubusercontent.com/mbostock/a4fd7a68925d4039c22996cc1d4862ce/raw/d813a42956d311d73fee336e1b5aac899c835883/fourier.svg\")\n .then(response => response.text())\n .then(text => (new DOMParser).parseFromString(text, \"image/svg+xml\"))\n .then(svg => svg.documentElement)","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"path = image.querySelector(\"path\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":55,"value":"class PathSampler {\n constructor(source) {\n const data = PathData.parse(source, {normalize: true});\n const d0 = data[0];\n const d1 = data[data.length - 1];\n if (d0.type !== \"M\") throw new Error(\"expected M\");\n if (d1.type !== \"Z\") throw new Error(\"expected Z\");\n const segments = Array.from({length: data.length - 2}, (_, i) => {\n const {type, values} = data[i + 1];\n switch (type) {\n case \"C\": return new C(data[i].values.slice(-2).concat(values));\n case \"L\": return new L(data[i].values.slice(-2).concat(values));\n }\n });\n const start = d0.values.slice(0, 2);\n const end = data[data.length - 2].values.slice(-2);\n if (start[0] !== end[0] || start[1] !== end[1]) {\n segments.push(new L(end.concat(start)));\n }\n this.segments = segments;\n }\n pointAt(t) {\n const n = this.segments.length;\n if (!((t *= n) >= t)) return;\n const i = Math.max(0, Math.min(n - 1, Math.floor(t)));\n return this.segments[i].pointAt(t % 1);\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":182,"value":"class L {\n constructor(values) {\n this.values = values;\n }\n pointAt(t) {\n const [x0, y0, x1, y1] = this.values;\n const a = t;\n const b = 1 - t;\n return [\n a * x0 + b * x1,\n a * y0 + b * y1\n ];\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":86,"value":"class C {\n constructor(values) {\n this.values = values;\n }\n pointAt(t) {\n const [x0, y0, x1, y1, x2, y2, x3, y3] = this.values;\n const a = (1 - t) ** 3;\n const b = 3 * (1 - t) ** 2 * t;\n const c = 3 * (1 - t) * t ** 2;\n const d = t ** 3;\n return [\n a * x0 + b * x1 + c * x2 + d * x3,\n a * y0 + b * y1 + c * y2 + d * y3\n ];\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":41,"value":"PathData = require(\"path-data@0.0.2\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}