31:T67a,{ const height = 700; let fourierX; let fourierY; const x = []; const y = []; let time = 0; let path = []; const ctx = newContext({ width, height }); let loop = true; const ec = d3.color("white").copy({ opacity: 0.9 }); // epicycles color const pc = d3.color("white").copy({ opacity: 0.3 }); // path color function setup() { const skip = 6; for (let i = 0; i < drawing.length; i += skip) { x.push(drawing[i].x); y.push(drawing[i].y); } fourierX = dft(x); fourierY = dft(y); fourierX.sort((a, b) => b.amp - a.amp); fourierY.sort((a, b) => b.amp - a.amp); } function draw() { const vx = epiCycles({ x: width / 2 + 100, y: 100, rotation: 0, fourier: fourierX, time, ctx }); const vy = epiCycles({ x: 200, y: height / 2 + 75, rotation: Math.PI / 2, fourier: fourierY, time, ctx }); const v = { x: vx.x, y: vy.y }; path.unshift(v); // Draw a line between the current x epicycle to the path ctx.line({ x: vx.x, y: vx.y, x2: v.x, y2: v.y, strokeStyle: ec }); // Draw a line between the current y epicycle to the path ctx.line({ x: vy.x, y: vy.y, x2: v.x, y2: v.y, strokeStyle: ec }); // Draw the state of the path for this iteration ctx.get().strokeStyle = pc; ctx.path(path); const dt = (Math.PI * 2) / fourierY.length; time += dt; if (time > Math.PI * 2) { time = 0; path = []; } } setup(); while (loop) { ctx.clear(); draw(); yield ctx.canvas; } }32:T62a,md` #### How the algorithm works We use the set of ${tex`x,y`} points (x and y arrays) that define the path we want to approximate and compute the Discrete Fourier Series on the x values and the y values (fourierX, fourierY). Each entry on the fourierX/Y arrays contains the terms of the series. On each animation loop (every 16 ms or 60 times per second), we first call epiCycles() on fourierX and fourierY. That will do two things: Visualize the epiCycles by computing the radius and locations of each of the epiCycles and also return a vector (x,y) which contains the cartesian coordinate given the current input value (time). We just compute the series and sum up the values. And then we compute the (x,y) values using trigonometry. And remember, the function that approximates our path has an input domain of ${tex`[0, 2\pi]`}. We use vx(x,y) and vy(x,y) to compute the current point of the path we are trying to approximate (we call it v in the code): ${tex`v = (vx.x, vy.y)`}. We add that point or vector to the array named path. This array contains all the points of the path we approximate as we compute them. We can now draw the two lines that connect the epicycles for x and y to the current path point. The next step is to draw the current state of the path. Then we compute the next moment in time. Remember, the input domain of time is ${tex`[0, \pi]`}. The increments are the ${tex`length(series)`} computed in the code as the size of one of the fourier arrays. Finally, if we reach a full turn (${tex`2\pi`}), we reset time to zero and clear the path. `33:T401,function newContext({ width, height }) { const ctx = DOM.context2d(width, height); function line({ x, y, x2, y2, strokeStyle = "white" }) { ctx.beginPath(); ctx.strokeStyle = strokeStyle; ctx.moveTo(x, y); ctx.lineTo(x2, y2); ctx.stroke(); } function path(points) { if (points.length < 1) return; ctx.beginPath(); //ctx.moveTo(0, points[0]); points.forEach(p => ctx.lineTo(p.x, p.y)); //ctx.fill(); //ctx.closePath(); ctx.stroke(); } function clear() { ctx.fillStyle = "black"; ctx.fillRect(0, 0, width, height); } function circle({ x, y, r, fill = "black", strokeStyle = "white", lineWidth = 1 }) { ctx.beginPath(); ctx.arc(x, y, r, Math.PI * 2, false); ctx.strokeStyle = strokeStyle; ctx.lineWidth = lineWidth; if (fill) { ctx.fillStyle = fill; ctx.fill(); } ctx.stroke(); } return { get: () => ctx, line, circle, clear, path, canvas: ctx.canvas }; }34:[] 2f:{"title":"Fourier Series (part2): Alien 👾 machines","cells":[{"id":117,"value":"md`# Fourier Series (part2): Alien 👾 machines\n\n${html`\n

\n\nThis is part 2 (see part 1) on my series about the Fourier transform. More details below.\n\n\n

\n`}\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1053,"value":"md`\nIn [Part 1](https://observablehq.com/@drio/visualizing-the-fourier-series) we used a series of sinusoids to approximate a square wave. In this notebook we take a step further and we compute the [Discrete Fourier Series](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) on a svg path. The result is a same-length (as the number of points in the input path) equally space samples. We apply the DFT to the x and y values separately and we visualize those as [epicycles](https://en.wikipedia.org/wiki/Deferent_and_epicycle#Epicycles) connecting their state to the path we are aproximating. \n\nAs usual, I stand on the shoulders of giants. Thank you to Dan from the [Coding Train]([giants](https://www.youtube.com/watch?v=MY4luNgGfms&t=1336s).\n\nI haven't had my epifany on this topic yet but I am making progress. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":793,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":783,"value":"md`\nThe visualization of the fourier series is called [epicycle](https://en.wikipedia.org/wiki/Deferent_and_epicycle#Epicycles). \nHere is the code that implements those. \n\nThis function performs two things. First, it runs the necessary code to render the epicycle given the input. Second, it generates the carthesian coordinates (x,y) given the value of time. \n\nThe input parameters are:\n\n- x, y: Where to draw the epiCycles.\n- rotation: how to rotate the epicycles (we have two epicycle machines: one for the x and another one for the y values).\n- fourier: the fourier values results\n- time: the current time.\n- ctx: the canvas context\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":784,"value":"function epiCycles({ x, y, rotation, fourier, time, ctx }) {\n const ec = d3.color(\"white\").copy({ opacity: 0.5 }); // epicycles color\n\n for (let i = 0; i < fourier.length; i++) {\n let prevx = x;\n let prevy = y;\n\n let freq = fourier[i].freq;\n let radius = fourier[i].amp;\n let phase = fourier[i].phase;\n x += radius * Math.cos(freq * time + phase + rotation);\n y += radius * Math.sin(freq * time + phase + rotation);\n\n ctx.circle({\n ctx,\n r: radius,\n x: prevx,\n y: prevy,\n fill: null,\n strokeStyle: ec\n });\n ctx.line({\n x: prevx,\n y: prevy,\n x2: x,\n y2: y,\n strokeStyle: ec\n });\n ctx.circle({\n ctx,\n r: 1,\n x,\n y,\n fill: \"tomato\"\n });\n }\n\n return { x, y };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":770,"value":"md`\nThe *Discrete Fourier Transform* equation looks like this:\n![](https://wikimedia.org/api/rest_v1/media/math/render/svg/18b0e4c82f095e3789e51ad8c2c6685306b5662b)\n\nAnd this is one possible implementation:\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":763,"value":"/* Code from Daneil Shiffman from the Coding train */\nfunction dft(x) {\n const TWO_PI = Math.PI * 2;\n const X = []; // the computed dft on x\n const N = x.length;\n for (let k = 0; k < N; k++) {\n // index the input values (x)\n let re = 0;\n let im = 0;\n for (let n = 0; n < N; n++) {\n // Inner loop again over the values (x)\n const phi = (TWO_PI * k * n) / N;\n re += x[n] * Math.cos(phi);\n im -= x[n] * Math.sin(phi);\n }\n re = re / N;\n im = im / N;\n \n let freq = k;\n let amp = Math.sqrt(re * re + im * im);\n let phase = Math.atan2(im, re);\n X[k] = { re, im, freq, amp, phase };\n }\n return X;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":392,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":989,"value":"//drawing = await FileAttachment(\"codingtrain.json\").json()\ndrawing = P.map((p) => ({ x: p[0] / 2, y: p[1] / 2 }))","pinned":false,"hidden":false,"mode":"ojs"},{"id":977,"value":"import { P } from \"@mbostock/fourier-series-zoom\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}