Last active
March 12, 2020 11:37
-
-
Save hdf/4f37bdd63d9cd00312c07d426f07a1a2 to your computer and use it in GitHub Desktop.
Discrete Fourier transformation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Coding Challenge 130.3: Drawing with Fourier Transform and Epicycles | |
| // Daniel Shiffman | |
| // https://thecodingtrain.com/CodingChallenges/130.1-fourier-transform-drawing.html | |
| // https://thecodingtrain.com/CodingChallenges/130.2-fourier-transform-drawing.html | |
| // https://thecodingtrain.com/CodingChallenges/130.3-fourier-transform-drawing.html | |
| // https://youtu.be/7_vKzcgpfvU | |
| // https://editor.p5js.org/codingtrain/sketches/ldBlISrsQ | |
| class Complex { | |
| constructor(a, b) { | |
| this.re = a; | |
| this.im = b; | |
| } | |
| add(c) { | |
| this.re += c.re; | |
| this.im += c.im; | |
| } | |
| mult(c) { | |
| const re = this.re * c.re - this.im * c.im; | |
| const im = this.re * c.im + this.im * c.re; | |
| return new Complex(re, im); | |
| } | |
| } | |
| function dft(x) { | |
| const X = []; | |
| const N = x.length; | |
| for (let k = 0; k < N; k++) { | |
| let sum = new Complex(0, 0); | |
| for (let n = 0; n < N; n++) { | |
| const phi = (TWO_PI * k * n) / N; | |
| const c = new Complex(cos(phi), -sin(phi)); | |
| sum.add(x[n].mult(c)); | |
| } | |
| sum.re = sum.re / N; | |
| sum.im = sum.im / N; | |
| let freq = k; | |
| let amp = sqrt(sum.re * sum.re + sum.im * sum.im); | |
| let phase = atan2(sum.im, sum.re); | |
| X[k] = { re: sum.re, im: sum.im, freq, amp, phase }; | |
| } | |
| return X; | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?xml version="1.0" encoding="UTF-8" standalone="no"?> | |
| <svg | |
| xmlns:dc="http://purl.org/dc/elements/1.1/" | |
| xmlns:cc="http://creativecommons.org/ns#" | |
| xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" | |
| xmlns:svg="http://www.w3.org/2000/svg" | |
| xmlns="http://www.w3.org/2000/svg" | |
| width="256" | |
| height="256" | |
| viewBox="0 0 16 16" | |
| version="1.1" | |
| aria-hidden="true"> | |
| <path fill-rule="evenodd" d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59.4.07.55-.17.55-.38 0-.19-.01-.82-.01-1.49-2.01.37-2.53-.49-2.69-.94-.09-.23-.48-.94-.82-1.13-.28-.15-.68-.52-.01-.53.63-.01 1.08.58 1.23.82.72 1.21 1.87.87 2.33.66.07-.52.28-.87.51-1.07-1.78-.2-3.64-.89-3.64-3.95 0-.87.31-1.59.82-2.15-.08-.2-.36-1.02.08-2.12 0 0 .67-.21 2.2.82.64-.18 1.32-.27 2-.27.68 0 1.36.09 2 .27 1.53-1.04 2.2-.82 2.2-.82.44 1.1.16 1.92.08 2.12.51.56.82 1.27.82 2.15 0 3.07-1.87 3.75-3.65 3.95.29.25.54.73.54 1.48 0 1.07-.01 1.93-.01 2.2 0 .21.15.46.55.38A8.013 8.013 0 0 0 16 8c0-4.42-3.58-8-8-8z"></path> | |
| </svg> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset="UTF-8" /> | |
| <meta http-equiv="X-UA-Compatible" content="IE=edge" /> | |
| <meta name="viewport" content="width=device-width, initial-scale=1" /> | |
| <title>Discrete Fourier transformation</title> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.8.0/p5.min.js"></script> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.8.0/addons/p5.dom.min.js"></script> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/raphael/2.2.8/raphael.min.js"></script> | |
| <script src="svg2vec.js"></script> | |
| <script src="fourier.js"></script> | |
| <script src="sketch.js"></script> | |
| </head> | |
| <body></body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Coding Challenge 130.3: Drawing with Fourier Transform and Epicycles | |
| // Daniel Shiffman | |
| // https://thecodingtrain.com/CodingChallenges/130.1-fourier-transform-drawing.html | |
| // https://thecodingtrain.com/CodingChallenges/130.2-fourier-transform-drawing.html | |
| // https://thecodingtrain.com/CodingChallenges/130.3-fourier-transform-drawing.html | |
| // https://youtu.be/7_vKzcgpfvU | |
| // https://editor.p5js.org/codingtrain/sketches/ldBlISrsQ | |
| let x = []; | |
| let fourierX; | |
| let time = 0; | |
| let path = []; | |
| let lengths = []; | |
| if (typeof(drawing) == 'undefined') | |
| var drawing = []; | |
| let w = 300; | |
| let h = 300; | |
| window.onhashchange = function() { | |
| x = []; | |
| time = 0; | |
| path = []; | |
| drawing = []; | |
| current_svg_xml = ''; | |
| setup(); | |
| }; | |
| function setup() { | |
| generatePointsFromSvg((window.location.hash ? window.location.hash.substr(1) : 'gh') + '.svg', (r) => { | |
| let scale = (w/r[1] < h/r[2]) ? w / (r[1] + 1) : h / (r[2] + 1); | |
| drawing = r[0].flat().map((e) => {return {x: e.x * scale, y: e.y * scale}}); | |
| lengths = []; // Do not allow large jumps | |
| for (let i = 1; i < drawing.length; i++) | |
| if (Math.sqrt(Math.pow(drawing[i].x - drawing[i-1].x, 2) + Math.pow(drawing[i].y - drawing[i-1].y, 2)) > 10) | |
| lengths.push(i); | |
| /*lengths = r[0].map((e) => e.length).slice(0, -1); | |
| for (let i = 1; i < lengths.length; i++) | |
| lengths[i] += lengths[i-1];*/ | |
| setup(); | |
| }); | |
| createCanvas(w, h); | |
| frameRate(60); | |
| const skip = 1; | |
| for (let i = 0; i < drawing.length; i += skip) { | |
| const c = new Complex(drawing[i].x, drawing[i].y); | |
| x.push(c); | |
| } | |
| fourierX = dft(x); | |
| fourierX.sort((a, b) => b.amp - a.amp); | |
| } | |
| function epicycles(x, y, rotation, fourier) { | |
| for (let i = 0; i < fourier.length; i++) { | |
| let prevx = x; | |
| let prevy = y; | |
| let freq = fourier[i].freq; | |
| let radius = fourier[i].amp; | |
| let phase = fourier[i].phase; | |
| x += radius * cos(freq * time + phase + rotation); | |
| y += radius * sin(freq * time + phase + rotation); | |
| stroke(255, 100); | |
| noFill(); | |
| ellipse(prevx, prevy, radius * 2); | |
| stroke(255); | |
| line(prevx, prevy, x, y); | |
| } | |
| return createVector(x, y); | |
| } | |
| function waves(fourierX) { | |
| /*if (fourierX.length < 1) return; | |
| let fourier = fourierX.slice(0, 10).sort((a, b) => a.freq - b.freq); | |
| let l = fourier.length; | |
| colorMode(HSB, l); | |
| for (let i = 0; i < l; i++) { | |
| beginShape(); | |
| for (let i2 = 0; i2 <= (time / TWO_PI) * width; i2++) { | |
| vertex(i2, height / 4 + fourier[i].amp + fourier[i].amp * sin(i2 / (TWO_PI * 4) + fourier[i].phase)); | |
| stroke(i, l, l); | |
| } | |
| endShape(); | |
| } | |
| colorMode(RGB, 255);*/ | |
| } | |
| function draw() { | |
| background(0); | |
| waves(fourierX); | |
| let v = epicycles(width / 2, height / 2, 0, fourierX); | |
| path.unshift(v); | |
| beginShape(); | |
| noFill(); | |
| for (let i = 0; i < path.length; i++) { | |
| if (lengths.includes(path.length - i)) { | |
| endShape(); | |
| beginShape(); | |
| } | |
| vertex(path[i].x, path[i].y); | |
| } | |
| endShape(); | |
| const dt = TWO_PI / fourierX.length; | |
| time += dt; | |
| if (time > TWO_PI) { | |
| time = 0; | |
| path = []; | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Based on: https://github.com/Shinao/PathToPoints | |
| // To generate text: https://danmarshall.github.io/google-font-to-svg-path/ | |
| // Also consider: https://vecta.io/nano | |
| let current_svg_xml = ''; | |
| function generatePointsFromSvg(file, cb, step_point) { | |
| if (typeof(step_point) == 'undefined') step_point = 0.5; | |
| if (current_svg_xml == '') { | |
| let xhr = new XMLHttpRequest(); | |
| xhr.open('GET', file, true); | |
| xhr.onload = function(e) { | |
| current_svg_xml = this.response; | |
| cb(generatePointsFromSvg(file, cb, step_point)); | |
| }; | |
| xhr.send(); | |
| return; | |
| } | |
| let doc = (new DOMParser()).parseFromString(current_svg_xml, "application/xml"); | |
| let paths = doc.getElementsByTagName('path'); | |
| // Read each paths from svg | |
| let all_points = []; | |
| let bbox_path = doc.children[0].getAttribute('viewBox').split(' '); | |
| let width = parseFloat(bbox_path[2]), height = parseFloat(bbox_path[3]); | |
| for (let i = 0; i < paths.length; ++i) { | |
| let path = paths[i].getAttribute('d').replace(' ', ','); | |
| // get points at regular intervals | |
| let data_points = []; | |
| let c, l = Raphael.getTotalLength(path), step = step_point * Math.pow(Math.floor(Math.log(l) / Math.log(10)), 2); | |
| for (c = 0; c < l; c += step) { | |
| let point = Raphael.getPointAtLength(path, c); | |
| point.x = (point.x - (width / 2)); | |
| point.y = (point.y - (height / 2)); | |
| delete point.alpha; | |
| data_points.push(point); | |
| } | |
| all_points.push(data_points); | |
| } | |
| return [all_points, width, height]; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://hdfvis.surge.sh/P5/
https://gist.run/?id=4f37bdd63d9cd00312c07d426f07a1a2