30:T45c,It looks like we could draw any closed shape if we have sufficient circles and organise them correctly. Specifically, we need to choose - The size of each circle (_radius_) - The speed of orbit of each circle (_frequency_) - The start point within each circular orbit (_phase_ angle) - The number of circles (determining how much detail we can capture in the shape we are tracing out) But how do find out these magic circle properties that give us a particular shape when rotated around each other? The answer, it turns out, has been known for a couple of hundred years, thanks to [Joseph Fourier](https://en.wikipedia.org/wiki/Joseph_Fourier). For any given set of coordinates we can calculate a [discrete Fourier transform](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) which tells us the radius, frequency and phase of each circular orbit. The calculation is rather simple considering the magic achieved, but it's well worth understanding [how the transform works](https://youtu.be/r6sGWTCMz2k) as it is remarkably elegant, based on [Euler's formula](https://en.wikipedia.org/wiki/Euler's_formula):31:T40e,function drawMap() { const geo = new GeoJSON().polygon(gbOutline); return Plot.plot({ style: "background:oklch(48% 0.2 220deg); box-shadow: inset 0 0 8em 8em oklch(40% 0.2 30deg /10%);", width: 1000, height: 1000, inset: 80, color: partyPalette, projection: { type: "reflect-y", domain: geo.boundingRect() }, marks: [ Plot.geo(geo.featureCollection, { strokeWidth: 20, stroke: "oklch(68% 0.1 220deg)", strokeDasharray: [1, 18] }), Plot.geo(geo.featureCollection, { strokeWidth: 3, fill: "oklch(95% 0.05 90deg)" }), Plot.dot(results, { x: "cx", y: "cy", r: 5, fill: "first", stroke: "black", strokeWidth: 0.5 }), Plot.text(["Election Results\n2024"], { frameAnchor: "top-right", dx: -100, dy: 320, fontSize: 50, fontFamily: "Raleway Dots", fontWeight: 900, fill: "white" }), Plot.frame() ] }); }32:T465,## Further Watching I've used Fourier transforms for years, but I found this circle exercise the one that made the most intuitive sense of Fourier series generation. Thanks goes in large part to some highly gifted explainers, in particular: - [Grant Sanderson (3Blue1Brown)](https://youtu.be/r6sGWTCMz2k?si=TgDGqaqbXyQNnRGv) who uses visual explanation to unpick the mathematics behind Fourier series. - [Dan Shiffman](https://youtu.be/MY4luNgGfms?si=ZxwqM3xtu_dpDTah) who explains the process from a coding perspective. It is interesting to contrast their approaches. Grant's animations and explanations are so slick and calm, making what might have been perceived as complex and esoteric as natural and intuitive. Dan's videos are frenetic, exposing the mistakes we all make when coding, but that ultimately lead to satisfying results. Both work remarkably well, taking us somewhere we haven't been before. And as an example of a nicely presented interactive summary of the process, it's hard to do better than Jez Swanson's [interactive introduction to Fourier transforms](https://www.jezzamon.com/fourier/index.html).33:[{"id":"b73212e2e289e40b7d19a5b601bf8917a1cf9463882a5920c58522f3e84d8931497b773cf742f4f58d8887740fdfbbcc1d3f0d6ce059ea62badf14445ccb2dc0","href":"https://static.observableusercontent.com/files/b73212e2e289e40b7d19a5b601bf8917a1cf9463882a5920c58522f3e84d8931497b773cf742f4f58d8887740fdfbbcc1d3f0d6ce059ea62badf14445ccb2dc0","name":"gbMainland.json","type":"application/json","lastModified":1732450686176.52,"size":7588},{"id":"c34649260b0f460ed69f61715c7b15d4590fae12a4b200f2e935c00cabdba675d66822caa65061f47ce722a97f27ccfda40eb9ed65d287b925e5e3c4e24173b8","href":"https://static.observableusercontent.com/files/c34649260b0f460ed69f61715c7b15d4590fae12a4b200f2e935c00cabdba675d66822caa65061f47ce722a97f27ccfda40eb9ed65d287b925e5e3c4e24173b8","name":"electionResultsMainland@2.csv","type":"text/csv","lastModified":1732466177037.112,"size":46455}] 2e:{"title":"30 Day Map Challenge: 24. Only Circles","cells":[{"id":0,"value":"# 30 Day Map Challenge: 24. Only Circles","pinned":false,"hidden":false,"mode":"md"},{"id":483,"value":"Is it possible to draw a useful map of Britain with only circles?","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"We all know what a circle looks like. Curvy, simple, no sharp corners, no straight bits. Here are two of them:","pinned":false,"hidden":false,"mode":"md"},{"id":22,"value":"showShape(80, {\n r2: -80 / 2,\n t: 0,\n w: 170,\n h: 170,\n showPath: false,\n showPen: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"What if we move the inner circle around the outer one?","pinned":false,"hidden":false,"mode":"md"},{"id":46,"value":"showShape(80, {\n r2: -80 / 2,\n t: t,\n w: 170,\n h: 170,\n showPath: false,\n showPen: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"viewof t = Scrubber(\n d3.range(0, 501).map((d) => d / 500),\n { autoplay: false, delay: 10 }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"## Tracing paths with circles\n\nWhat trace is a point on that inner circle leaving as it moves around the outer one?","pinned":false,"hidden":false,"mode":"md"},{"id":74,"value":"showShape(80, { r2: -80 / 2, t: t, w: 170, h: 170, pathClr: \"grey\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"We have 'only circles' drawing straight lines!\n\nNot only straight lines, but a variety of shapes depending on the relative size of the circles. In the example above the inner circle had exactly half the radius of the outer one. Shown below are paths traced by circles one third, one quarter and one sixth the radius of the larger one:","pinned":false,"hidden":false,"mode":"md"},{"id":79,"value":"

\n${showShape(80, { r2: -80 / 3, t: t, w: 170, h: 170, pathClr:\"grey\" })} \n${showShape(80, { r2: -80 / 4, t: t, w: 170, h: 170, pathClr:\"grey\" })} \n${showShape(80, { r2: -80 / 6, t: t, w: 170, h: 170, pathClr:\"grey\" })} \n

","pinned":false,"hidden":false,"mode":"html"},{"id":90,"value":"[Epicycles](https://en.wikipedia.org/wiki/Deferent_and_epicycle) like these have long been known to be able to trace out more complex shapes from simpler circular orbits. I explored this idea in my excursion into [rolling pathways](https://observablehq.com/@jwolondon/rolling-pathways).\n\nBut for a given shape we might want to draw, can we calculate the relative size of those circles required to trace out a pathway following our intended shape? \n\nSuppose we want to draw a square more accurately than the middle shape above. With a small repositioning of the smaller circle, we could, certainly improve things:","pinned":false,"hidden":false,"mode":"md"},{"id":439,"value":"drawFS(squareFS, { w: 320, h: 320, t: time, numCircles: 2 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":267,"value":"viewof time = Inputs.range([0, 2 * Math.PI], {\n label: \"time\",\n step: (2 * Math.PI) / squareFS.length,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"But, it's still rather rounded. Making the inner circle smaller won't help because the path will tend towards the shape of the large circle. Making it bigger won't help either because we will end up with concave shapes like those above.\n\nBut what if we add another circle orbiting the smaller one? And then another circle orbiting _that_ circle, and so on?","pinned":false,"hidden":false,"mode":"md"},{"id":456,"value":"drawFS(squareFS, { w: 640, h: 640, t: time, numCircles: dftView.nCircles })","pinned":false,"hidden":false,"mode":"ojs"},{"id":496,"value":"viewof dftView = Inputs.form({\n nCircles: Inputs.radio([1, 2, 4, 6, squareFS.length], {\n label: \"Number of circles\",\n value: 2\n }),\n time: Inputs.bind(\n Inputs.range([0, 2 * Math.PI], { label: \"time\" }),\n viewof time\n )\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":476,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":116,"value":"function dft(cs) {\n const fcs = [];\n for (let k = 0; k < cs.length; k++) {\n let sum = new Complex(0, 0);\n for (let n = 0; n < cs.length; n++) {\n const phi = (Math.PI * 2 * k * n) / cs.length;\n sum = sum.add(cs[n].mult(new Complex(Math.cos(phi), -Math.sin(phi))));\n }\n const c = sum.div(cs.length);\n fcs.push({ re: c.re, im: c.im, freq: k, amp: c.mag(), phase: c.angle() });\n }\n return fcs;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":505,"value":"Here's the same process applied to a more complex shape. Try rotating the 'time' slider with first 4 circles, then 6, then 12 etc. in sequence.","pinned":false,"hidden":false,"mode":"md"},{"id":513,"value":"drawFS(mainlandFS, {\n w: 400,\n h: 620,\n t: dftView2.time,\n numCircles: dftView2.nCircles,\n margin: 0.2,\n flipY: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":517,"value":"viewof dftView2 = Inputs.form({\n time: Inputs.range([0, 2 * Math.PI], {\n label: \"time\",\n step: (2 * Math.PI) / mainlandFS.length,\n value: 0\n }),\n nCircles: Inputs.radio([4, 6, 12, 24, 48, 96, mainlandFS.length], {\n label: \"Number of circles\",\n value: 4\n })\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":587,"value":"Not only is this arbitrary complexity derivable from only circles, it is easy to compute. And if we limit the number of circles used (or technically, the number of sorted Fourier coefficients), we can produce some nice rounded generalisations of shapes:","pinned":false,"hidden":false,"mode":"md"},{"id":603,"value":"

\n${drawFS(mainlandFS, {\n w: 180,\n h: 280,\n numCircles: 4,\n flipY: true,\n showConstruction: false\n})} \n ${drawFS(mainlandFS, {\n w: 180,\n h: 280,\n numCircles: 6,\n flipY: true,\n showConstruction: false\n})} \n\n ${drawFS(mainlandFS, {\n w: 180,\n h: 280,\n numCircles: 10,\n flipY: true,\n showConstruction: false\n})} \n\n ${drawFS(mainlandFS, {\n w: 180,\n h: 280,\n numCircles: 16,\n flipY: true,\n showConstruction: false\n})} \n\n ${drawFS(mainlandFS, {\n w: 180,\n h: 280,\n numCircles: 64,\n flipY: true,\n showConstruction: false\n})} \n

","pinned":false,"hidden":false,"mode":"html"},{"id":112,"value":"## Circle spacing","pinned":false,"hidden":false,"mode":"md"},{"id":671,"value":"So to bring us round full-circle, we can answer the question at the top of this page: Yes we can draw a map of Britain with 'only circles'.\n\nBut to be more useful, we'd probably want to draw something inside that coastline. As an illustration we can map the results of the [2024 UK General Election](https://observablehq.com/@jwolondon/uk-election-2024-results).","pinned":false,"hidden":false,"mode":"md"},{"id":703,"value":"results = FileAttachment(\"electionResultsMainland@2.csv\").csv({ typed: true })","pinned":false,"hidden":false,"mode":"ojs"},{"id":963,"value":"In keeping with the 'only circles' theme, we can represent each constituency in mainland Britain as a circle and colour it as a dot. But, as ever, we have a problem if we simply locate each circle at its geographic position because constituencies are packed close together in urban areas and spaced far apart in large rural areas. So here I used the [Adaptive Voronoi Tesselation approach I used on day 4](https://observablehq.com/@jwolondon/tdmc2024_day04) to space constituency centroids out within the containing boundary generated above with a '20 circle' level of generalisation. \n\nIn brief, it spaces out constituency centroids by first generating [voronoi regions](https://d3js.org/d3-delaunay/voronoi) from them; clipping the regions to be within the circle-generated coastline above; moving the points to the centroids of those clipped regions; and repeating until desired spacing is achieved – a process known as [Lloyd's relaxation](https://observablehq.com/@mbostock/lloyds-algorithm).","pinned":false,"hidden":false,"mode":"md"},{"id":673,"value":"gbOutline = getPath(coordsToFS(mainlandCoords), 20)","pinned":false,"hidden":false,"mode":"ojs"},{"id":824,"value":"function calcRelaxedCentroids(pts, container, options = {}) {\n const { n = 10, omega = 0.5, key = \"PCON24CD\" } = options;\n return toRelaxedRegions(pts, {\n n: n,\n omega: 1,\n container: [container]\n })\n .filter((d) => d.region.length > 0)\n .map((d) => {\n const [cx, cy] = d3.polygonCentroid(d.region[0]);\n return { cx, cy, key: d.properties[key] };\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":973,"value":"The result is a compromise between a full constituency-weighted cartogram and a conventional geographic map (there is a degree of spacing regularity, but Scottish centroids are still more spaced out than London).\n\nTo complete the circular theme, I symbolised the rounded coastline with a circle border (using a thick stroke width and closely spaced dashes), a font made up only of circles, and clipped circle background. Only circles!","pinned":false,"hidden":false,"mode":"md"},{"id":681,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":922,"value":"

\n ${drawMap()}\n

","pinned":false,"hidden":false,"mode":"html"},{"id":1002,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md"},{"id":642,"value":"_For animation slider and controls:_","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"import { Scrubber } from \"@mbostock/scrubber\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":644,"value":"_An earlier [excursion into rolling pathways](https://observablehq.com/@jwolondon/rolling-pathways) used to generate the first few animations on this page:_","pinned":false,"hidden":false,"mode":"md"},{"id":19,"value":"import { showShape } from \"@jwolondon/rolling-pathways\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":646,"value":"_For my stateful renderer, which is a little easier to use for animations and circle drawing than Plot:_","pinned":false,"hidden":false,"mode":"md"},{"id":257,"value":"import { Renderer } from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"_Handle complex numbers, useful for the DFT:_","pinned":false,"hidden":false,"mode":"md"},{"id":114,"value":"class Complex {\n constructor(re, im) {\n this.re = re;\n this.im = im;\n }\n\n add({ re, im }) {\n return new Complex(this.re + re, this.im + im);\n }\n\n mult({ re, im }) {\n return new Complex(\n this.re * re - this.im * im,\n this.re * im + this.im * re\n );\n }\n\n div(x) {\n return new Complex(this.re / x, this.im / x);\n }\n\n mag() {\n return Math.hypot(this.re, this.im);\n }\n\n angle() {\n return Math.atan2(this.im, this.re);\n }\n\n toString() {\n return `${this.re} + ${this.im}i`;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":232,"value":"_Convert an array of coordinates representing a closed path into a sorted Fourier series (largest amplitude first):_","pinned":false,"hidden":false,"mode":"md"},{"id":228,"value":"function coordsToFS(coords) {\n const fs = dft(coords.map((d) => new Complex(d[0], d[1]))).sort(\n (a, b) => b.amp - a.amp\n );\n return fs;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":667,"value":"_Extract the path coordinates from a given number of Fourier coefficients:_","pinned":false,"hidden":false,"mode":"md"},{"id":327,"value":"function getPath(fourierSeries, nTerms = -1) {\n const fs = nTerms > 0 ? fourierSeries.slice(0, nTerms) : fourierSeries;\n const path = [];\n const tau = 2 * Math.PI;\n\n for (let t = 0; t <= tau; t += tau / fourierSeries.length) {\n let [x, y] = [0, 0];\n fs.forEach((f) => {\n x += f.amp * Math.cos(f.freq * t + f.phase);\n y += f.amp * Math.sin(f.freq * t + f.phase);\n });\n path.push([x, y]);\n }\n return path;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":493,"value":"_Draw an animated set of DFT epicycles:_","pinned":false,"hidden":false,"mode":"md"},{"id":242,"value":"function drawEpicycles(fourierSeries, nTerms, t, renderer) {\n let [x, y] = [0, 0];\n const fs =\n nTerms > 0 && nTerms < fourierSeries.length\n ? fourierSeries.slice(0, nTerms)\n : fourierSeries;\n\n renderer.push().stroke(\"grey\").strokeWidth(1).fill();\n fs.forEach((f) => {\n renderer.ellipse(x, y, f.amp);\n x += f.amp * Math.cos(f.freq * t + f.phase);\n y += f.amp * Math.sin(f.freq * t + f.phase);\n });\n renderer.pop();\n return [x, y];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":433,"value":"function drawFS(fs, options = {}) {\n const {\n w = 400,\n h = 400,\n t = 0,\n numCircles = -1,\n margin = 0.15,\n penSize = 4,\n flipY = false,\n showConstruction = true\n } = options;\n\n const path = getPath(fs, numCircles);\n const [xMin, xMax] = d3.extent(path, (d) => d[0]);\n const [yMin, yMax] = d3.extent(path, (d) => d[1]);\n const renderer = new Renderer(w, h).fit(\n [\n [xMin, yMin],\n [xMax, yMax]\n ],\n margin * w\n );\n\n if (flipY) {\n renderer.flipY();\n }\n\n // Draw the resulting path highlighting the point at a given time.\n renderer.push().stroke(\"firebrick\").fill().strokeWidth(2).polygon(path);\n\n if (showConstruction) {\n // Size of pen indicator in data units\n const penR =\n renderer.screenToData([penSize, 0])[0] - renderer.screenToData([0, 0])[0];\n const v = drawEpicycles(fs, numCircles, t, renderer);\n renderer\n .stroke()\n .fill(\"firebrick\")\n .ellipse(...v, penR);\n }\n\n return renderer.pop().render();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":653,"value":"_Square perimeter coordinates and their Fourier coefficients:_","pinned":false,"hidden":false,"mode":"md"},{"id":286,"value":"function genSquare(side, stepSize) {\n const halfSide = side / 2;\n const perimeter = 4 * side;\n\n return Array.from({ length: Math.ceil(perimeter / stepSize) }, (_, i) => {\n const distance = (i * stepSize) % perimeter;\n if (distance < side) {\n return [-halfSide, halfSide - distance]; // Left\n } else if (distance < 2 * side) {\n return [-halfSide + (distance - side), -halfSide]; // Bottom\n } else if (distance < 3 * side) {\n return [halfSide, -halfSide + (distance - 2 * side)]; // Right\n } else {\n return [halfSide - (distance - 3 * side), halfSide]; // Top\n }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":135,"value":"squareFS = coordsToFS(genSquare(400, 10))","pinned":false,"hidden":false,"mode":"ojs"},{"id":650,"value":"_Coastal coordinates and their Fourier coefficients:_","pinned":false,"hidden":false,"mode":"md"},{"id":507,"value":"mainlandCoords = topojson.feature(\n await d3.json(await FileAttachment(\"gbMainland.json\").url()),\n \"gbMainland\"\n).features[0].geometry.coordinates[0]","pinned":false,"hidden":false,"mode":"ojs"},{"id":523,"value":"mainlandFS = coordsToFS(mainlandCoords)","pinned":false,"hidden":false,"mode":"ojs"},{"id":686,"value":"_For converting coordinates into GeoJSON features:_","pinned":false,"hidden":false,"mode":"md"},{"id":688,"value":"import { GeoJSON } from \"@jwolondon/geojson-generator\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":982,"value":"_For election result colours:_","pinned":false,"hidden":false,"mode":"md"},{"id":858,"value":"partyClrs = new Map([\n [\"Con\", \"rgb(59,120,214)\"],\n [\"Lab\", \"rgb(209,45,65)\"],\n [\"LD\", \"rgb(238,170,65)\"],\n [\"Grn\", \"rgb(75,166,99)\"],\n [\"Ref\", \"rgb(88,210,211)\"],\n [\"SNP\", \"rgb(251,243,155)\"],\n [\"PC\", \"rgb(37,90,84)\"],\n [\"WP\", \"rgb(230,160,180)\"],\n [\"DUP\", \"rgb(198,112,83)\"],\n [\"SF\", \"rgb(63,102,96)\"],\n [\"All\", \"rgb(239,205,82)\"],\n [\"SDLP\", \"rgb(84,166,64)\"],\n [\"UUP\", \"rgb(97,163,232)\"],\n [\"TUV\", \"rgb(88,191,201)\"],\n [\"Ant\", \"rgb(71,83,47)\"],\n [\"PBP\", \"rgb(214,56,84)\"],\n [\"Ind\", \"rgb(140,0,100)\"],\n [\"other\", \"rgb(180,180,180)\"],\n [\"Speaker\", \"rgb(220,220,220)\"]\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":861,"value":"partyPalette = ({\n domain: [...partyClrs].map(([d, r]) => d),\n range: [...partyClrs].map(([d, r]) => r)\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":988,"value":"_For AVT generation:_","pinned":false,"hidden":false,"mode":"md"},{"id":717,"value":"import { toRelaxedRegions } from \"@jwolondon/tdmc2024_day04\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":990,"value":"_Dotty font:_","pinned":false,"hidden":false,"mode":"md"},{"id":868,"value":"","pinned":false,"hidden":false,"mode":"html"}],"files":"$W33","stdlib":"1","titling":"auto"}