31:T4b7,md`# Synthesizing Periodic Tilings of the Plane This notebook tries to reproduce the technique for tiling the plane with regular polygons described in the following papers: * A. Medeiros e Sá, L. H. de Figueiredo and J. E. Soto Sánchez, "Synthesizing Periodic Tilings of Regular Polygons," 2018 31st SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), Parana, 2018, pp. 17-24. [doi: 10.1109/SIBGRAPI.2018.00009](http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8614306&isnumber=8614297) * José Ezequiel Soto Sánchez, Asla Medeiros e Sá and Luiz Henrique de Figueiredo "Acquiring periodic tilings of regular polygons from images". The Visual Computer, V35, Number 6, pp 1432-2315 [doi: 10.1007/s00371-019-01665-y](https://doi.org/10.1007/s00371-019-01665-y) The subject of Archimedean Meshes is further discussed in the book [Sobre Malhas Arquimedianas](https://www.editoraolhares.com.br/produto/sobre-malhas-arquimedianas) (in Portuguese) ISBN: 978-85-62114-71-7 by Ricardo Sá and Asla Medeiros e Sá, Editora Olhares, 2017. The tiling database is periodically updated by the authors, who also made available a [reference implementation](http://w3.impa.br/~cheque/tiling). `32:T551,mainDisplay = { let height = ~~(width*9/16); let svgNode = html``; let size = patchMBR.size(); let group = d3.select(svgNode).append("g") .attr("transform", `translate(${width/2},${height/2}) scale(${edgeLength})`); let displacements = []; let [w,h] = [width/edgeLength,height/edgeLength]; for (let i = -50; i < 50; i++) { for (let j = -50; j < 50; j++) { let vec = t1.scale(i).add(t2.scale(j)); if (vec.x + 3*size.x < -w/2) continue; if (vec.x - 3*size.x > w/2) continue; if (vec.y + 3*size.y < -h/2) continue; if (vec.y - 3*size.y > h/2) continue; displacements.push (t1.scale(i).add(t2.scale(j))); } } let palette = paletteTable[colorPalette]; let ncolors = palette.length; group.selectAll("g.patch") .data(displacements).enter() .append("g") .attr("class","patch") .attr("transform",d=>`translate(${d.x},${d.y})`) .style("opacity",1) .selectAll("polygon") .data(faces).enter() .append("polygon") .attr("points", d => d.map(p=>`${p.x},${p.y}`).join(" ")) .style("fill",(d,i) => palette[(i+colorShift)%ncolors]) .style("stroke",edgeColor) .style("stroke-linejoin", "bevel") .style("stroke-width", edgeThickness/edgeLength); return svgNode; }33:[] 2f:{"title":"Synthesizing Periodic Tilings of the Plane","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":68,"value":"md`## Main Interface`","pinned":false,"hidden":false,"mode":"ojs"},{"id":956,"value":"{\n let controls = \n md`_Database:_ ${bindRadioGroup({options:Object.keys(databases)}, viewof databaseName)} \n _Pattern:_ ${bindSelect({options:Object.keys(databases[databaseName])}, viewof pattern)}
\n _Edge length:_ ${bindSliderNumber({min:10,max:100,step:1},viewof edgeLength)} \n _Edge thickness:_ ${bindSliderNumber({min:0,max:20,step:1},viewof edgeThickness)} \n _Edge color:_ ${bindColor({},viewof edgeColor)} \n _Palette:_ ${bindSelect({options:paletteNames}, viewof colorPalette)} \n ${bindCheckbox({},viewof animateTranslation)} auto-shift ${bindCheckbox({},viewof animateRotation)} auto-rotate `;\n d3.select(controls).select(\"button#shiftColors\").on(\"click\", () => viewof colorShift.value += 1);\n return controls\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":548,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1472,"value":"{\n if (animateRotation || animateTranslation) {\n let height = ~~(width*9/16);\n let a = 0;\n let t = 0;\n let da = animateRotation? 0.1 : 0;\n let dt = animateTranslation ? 0.005 : 0;\n while (true) {\n a += da; if (a >= 360) a = 0;\n t += dt; if (t >= 1) t = 0;\n let group = d3.select(\"svg#mainview g\");\n let trans = t1.add(t2).scale(t).scale(edgeLength);\n group.attr(\"transform\", `rotate(${a},${width/2},${height/2})\n translate(${trans.x},${trans.y})\n translate(${width/2},${height/2}) \n scale(${edgeLength})`);\n yield comment('_Function to animate the pattern transform_');\n }\n }\n else {\n return comment('No rotation or translation animation')\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":758,"value":"md`## A graphical summary of the steps to derive the tiling pattern:\n\n1. (*top-left*) Obtain the translation vectors and seeds\n2. (*top-right*) Compute the edges spawning from the seeds in the main tile\n3. (*bottom-left*) Compute the face centers\n4. (*bottom-right*) Compute the patch faces`","pinned":false,"hidden":false,"mode":"ojs"},{"id":174,"value":"{\n let div = html`

`;\n div.append(seedPlot());\n div.append(edgePlot());\n div.append(centersPlot());\n div.append(facesPlot());\n return div\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":763,"value":"md`

\n## Data structures and algorithms:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"comment('*The tiling databases*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"galebach = d3.json(\"https://gist.githubusercontent.com/esperanc/7728941a9fe4c937f0899b5f69c58c8f/raw/f42bd52cff7fb835ca9e08a943fade621942b633/Galebach.json\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":522,"value":"saesa = d3.json(\"https://gist.githubusercontent.com/esperanc/9b3651eb2fbff9bb04de23d594a0a361/raw/a46b20b967726a17d9c4b11edc909a92a57e6e41/SaeSa.json\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":960,"value":"databases = ({\"Galebach\": galebach, \"Sá e Sá\" : saesa})","pinned":true,"hidden":false,"mode":"ojs"},{"id":51,"value":"comment('*The four basic directions*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":53,"value":"w = [Vec(1, 0), // w^0\n Vec(0.8660254037844386, 0.5), // w^1\n Vec(0.5, 0.8660254037844386), // w^2\n Vec(0, 1) // w^3\n ]","pinned":true,"hidden":false,"mode":"ojs"},{"id":540,"value":"comment('*The selected tiling pattern object*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":73,"value":"tiling = databases[databaseName][pattern]","pinned":true,"hidden":false,"mode":"ojs"},{"id":95,"value":"comment('*A function for mapping a vector of the basis into a Cartesian `vector`*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"toVec = T => w[0].scale(T[0]).add(w[1].scale(T[1])).add(w[2].scale(T[2])).add(w[3].scale(T[3])) ","pinned":true,"hidden":false,"mode":"ojs"},{"id":106,"value":"comment('*The translation vectors*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":81,"value":"t1 = toVec(tiling.T1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":83,"value":"t2 = toVec(tiling.T2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":109,"value":"comment('*The seeds *')","pinned":false,"hidden":false,"mode":"ojs"},{"id":90,"value":"seeds = tiling.Seed.map(toVec)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1461,"value":"comment('*Minimum bounding rectangle for the seeds*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":132,"value":"seedsBox = new MBR(...seeds)","pinned":true,"hidden":false,"mode":"ojs"},{"id":489,"value":"comment('*Tile grid displacement vectors*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":491,"value":"tileDisplacements = {\n let displacements = [];\n for (let i of [0,-1,1,2]) {\n for (let j of [0,-1,1,2]) {\n displacements.push (t1.scale(i).add(t2.scale(j)));\n }\n }\n return displacements;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":149,"value":"comment('*Common code for creating a `svg` element and the `g` element (group) for a visualization*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":466,"value":"createSvgAndGroup = function () {\n let svgNode = html``;\n let svg = d3.select(svgNode);\n let center = seedsBox.max.add(seedsBox.min).scale(-0.5);\n let group = svg.append(\"g\")\n .attr(\"transform\", `translate(200,200) scale(${edgeLength}) translate(${center.x},${center.y})`);\n let tile = [Vec(0,0),t1,t1.add(t2),t2].map(p=>`${p.x},${p.y}`).join(\" \");\n group.selectAll(\"polygon.tile\").data(tileDisplacements).enter()\n .append(\"polygon\")\n .attr(\"points\",tile)\n .style(\"fill\", (d,i) => (i==0 ? \"rgb(240,240,240)\" : \"none\"))\n .style(\"stroke\",\"gray\")\n .style(\"stroke-width\",0.5/edgeLength)\n .attr(\"transform\", d => `translate(${d.x},${d.y})`);\n return [svgNode,group];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1452,"value":"comment('*Plot of the seeds and the translation vectors*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"seedPlot = function() {\n let [svgNode,group] = createSvgAndGroup ();\n group.selectAll(\"line\")\n .data([t1,t2]).enter()\n .append(\"line\")\n .attr(\"x1\", 0)\n .attr(\"y1\", 0)\n .attr(\"x2\", d=>d.x)\n .attr(\"y2\", d=>d.y)\n .style(\"stroke\", \"black\")\n .style(\"stroke-width\", 1.5/edgeLength)\n group.selectAll(\"circle\")\n .data(seeds).enter()\n .append(\"circle\")\n .attr(\"cx\", d=>d.x)\n .attr(\"cy\", d=>d.y)\n .attr(\"r\", 0.2)\n .attr(\"fill\", \"gray\")\n return svgNode;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":153,"value":"md`### Computing Edges`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1456,"value":"comment('*Positions of vertices in the main tile and a few neighboring tiles*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"vtx = {\n let vtx = []\n for (let d of tileDisplacements) {\n for (let seed of seeds) {\n vtx.push(seed.add(d))\n }\n }\n return vtx;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":261,"value":"comment('*Edges having one vertex in the main tile*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":155,"value":"edges = {\n let n = seeds.length;\n let m = vtx.length;\n let edges = [];\n for (let i = 0; i < n; i++) {\n let p = seeds[i];\n for (let j = i+1; j < m; j++) {\n let q = vtx[j];\n let d = p.dist(q);\n if (d > 0.99 && d < 1.01) {\n edges.push([p,q])\n }\n }\n }\n return edges;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":202,"value":"comment('*Plot of the tile edges*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":164,"value":"edgePlot = function () {\n let [svgNode,group] = createSvgAndGroup ();\n let n = seeds.length;\n group.selectAll(\"line\")\n .data(edges).enter()\n .append(\"line\")\n .attr(\"x1\", d=>d[0].x)\n .attr(\"y1\", d=>d[0].y)\n .attr(\"x2\", d=>d[1].x)\n .attr(\"y2\", d=>d[1].y)\n .style(\"stroke\", \"black\")\n .style(\"stroke-width\", 1.5/edgeLength)\n \n group.selectAll(\"circle\").data(vtx).enter().append(\"circle\")\n .attr(\"r\", (d,i) => i < n ? 4/edgeLength : 2/edgeLength)\n .attr(\"cx\", d=>d.x)\n .attr(\"cy\", d=>d.y)\n .style(\"fill\",\"gray\")\n .append(\"title\").text(d=>`(${d.x},${d.y})`)\n \n return svgNode;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":209,"value":"md`

\n### Computing faces`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1499,"value":"comment('*Incident edges starting on each seed*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":503,"value":"mutable iedges = []","pinned":true,"hidden":false,"mode":"ojs"},{"id":1504,"value":"comment('*Position of face centers*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"centers = {\n let n = seeds.length;\n let incidentEdges = [];\n let bisector = function (a,b) {\n let midpoint = a.add(b).scale(0.5);\n let dir = b.sub(a);\n return new Ray(midpoint,Vec(-dir.y,dir.x))\n }\n for (let i = 0; i < n; i++) {\n incidentEdges[i] = [];\n let s = seeds[i];\n for (let [p,q] of edges) {\n if (q.dist(s) < 0.001) [p,q] = [q,p];\n if (p.dist(s) < 0.001 && (q.x > p.x || (Math.abs(q.x - p.x)<0.001 && q.y < p.y))) incidentEdges[i].push(q);\n }\n incidentEdges[i].sort((a,b) => a.y-b.y);\n }\n mutable iedges = incidentEdges;\n let centers = [];\n for (let i = 0; i < n; i++) {\n let k = incidentEdges[i].length;\n if (k < 2) continue;\n let s = seeds[i];\n for (let j = 1; j < k; j++) {\n let ray1 = bisector(s,incidentEdges[i][j-1]);\n let ray2 = bisector(s,incidentEdges[i][j]);\n let [t,u] = ray1.intersectRay (ray2);\n let center = ray1.point(t);\n centers.push ({o : center, d:center.dist(s), s:s});\n }\n } \n return centers; \n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":278,"value":"comment('*A plot of the face centers*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":222,"value":"centersPlot = function () {\n let [svgNode,group] = createSvgAndGroup ();\n group.selectAll(\"g.center\")\n .data(centers).enter()\n .append(\"g\")\n .attr(\"class\", \"center\")\n .each(function(d,i) {\n let group = d3.select(this);\n group.append(\"circle\")\n .attr(\"cx\", d=>d.o.x)\n .attr(\"cy\", d=>d.o.y)\n .attr(\"r\", 3/edgeLength)\n .attr(\"fill\", \"gray\")\n group.append(\"circle\")\n .attr(\"cx\", d=>d.o.x)\n .attr(\"cy\", d=>d.o.y)\n .attr(\"r\", d=>d.d)\n .style(\"fill\",\"none\")\n .style(\"stroke\",\"gray\")\n .style(\"stroke-width\", 1/edgeLength)\n .style(\"stroke-dasharray\", \"0.1,0.1\") \n }); \n return svgNode;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":248,"value":"comment('*Faces*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":268,"value":"faces = {\n let faces = [];\n for (let {o,d} of centers) {\n let face = [];\n for (let v of vtx) {\n let vdist = v.dist(o);\n if (vdist > d*0.99 && vdist < d*1.01) {\n let dir = v.sub(o);\n face.push({v:v, angle:Math.atan2(dir.y,dir.x)});\n }\n }\n face.sort((a,b)=>a.angle-b.angle);\n faces.push(face.map(d=>d.v))\n }\n return faces\n}\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":1543,"value":"comment('*Minimum bounding rectangle of a patch*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1546,"value":"patchMBR = {\n let mbr = new MBR();\n for (let f of faces) for (let v of f) mbr.add(v)\n return mbr;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":283,"value":"comment('*Function to plot the faces of a patch*')","pinned":false,"hidden":false,"mode":"ojs"},{"id":275,"value":"facesPlot = function () {\n let [svgNode,group] = createSvgAndGroup ();\n group.selectAll(\"g.patch\")\n .data([Vec(0,0)]/*tileDisplacements*/).enter()\n .append(\"g\")\n .attr(\"class\",\"patch\")\n .attr(\"transform\",d=>`translate(${d.x},${d.y})`)\n .style(\"opacity\",0.8)\n .selectAll(\"polygon\")\n .data(faces).enter()\n .append(\"polygon\")\n .attr(\"points\", d => d.map(p=>`${p.x},${p.y}`).join(\" \"))\n .style(\"fill\",\"lightgray\")\n .style(\"stroke\",\"gray\")\n .style(\"stroke-width\", 1/edgeLength);\n return svgNode;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":567,"value":"md`### Colors`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1521,"value":"comment('Some of the color interpolators and palettes made available by `d3`')","pinned":false,"hidden":false,"mode":"ojs"},{"id":572,"value":"paletteNames = [\"interpolateBrBG\", \"interpolatePRGn\", \"interpolatePiYG\", \"interpolatePuOr\", \"interpolateRdBu\",\n \"interpolateRdGy\", \"interpolateRdYlBu\", \"interpolateRdYlGn\", \"interpolateSpectral\", \n \"interpolateBlues\", \"interpolateGreys\", \"interpolateOranges\", \"interpolateGreens\",\n \"interpolateReds\", \"interpolatePurples\",\"interpolateViridis\",\"interpolateInferno\",\n \"interpolateMagma\",\"interpolatePlasma\",\"interpolateCividis\",\"interpolateWarm\",\n \"interpolateCool\",\"interpolateCubehelixDefault\",\"interpolateBuGn\",\"interpolateBuPu\",\n \"interpolateGnBu\",\"interpolateOrRd\",\"interpolatePuBuGn\",\"interpolatePuBu\",\n \"interpolatePuRd\",\"interpolateRdPu\",\"interpolateYlGnBu\",\"interpolateYlGn\",\n \"interpolateYlOrBr\",\"interpolateYlOrRd\",\n \"interpolateRainbow\", \"interpolateSinebow\",\n \"Category10\",\"Accent\",\"Dark2\",\"Paired\",\"Pastel1\",\"Pastel2\",\"Set1\",\"Set2\",\"Set3\",\"Tableau10\"]\n\n\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1524,"value":"comment('Palettes for the current pattern')","pinned":false,"hidden":false,"mode":"ojs"},{"id":576,"value":"paletteTable = {\n let obj = {};\n for (let name of paletteNames) {\n if (name.slice(0,11) == \"interpolate\") {\n let interpolator = d3[name];\n let palette = [];\n let n = faces.length;\n for (let i = 0; i < n; i++) palette[i] = interpolator((i+0.5)/n);\n obj[name]=palette;\n }\n else {\n obj [name] = d3[`scheme${name}`];\n }\n }\n return obj\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1010,"value":"md`## Interface variables`","pinned":false,"hidden":false,"mode":"ojs"},{"id":921,"value":"viewof edgeLength = new View(30)","pinned":true,"hidden":false,"mode":"ojs"},{"id":932,"value":"viewof edgeThickness = new View(2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":937,"value":"viewof databaseName = new View(\"Sá e Sá\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":944,"value":"viewof pattern = new View(\"HNR\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":946,"value":"viewof edgeColor = new View (\"#222222\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":948,"value":"viewof colorPalette = new View(\"Pastel2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1418,"value":"viewof colorShift = new View(1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1527,"value":"viewof animateTranslation = new View(true)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1529,"value":"viewof animateRotation = new View(true)","pinned":true,"hidden":false,"mode":"ojs"},{"id":986,"value":"{\n if (databases[databaseName][pattern] == undefined) {\n if (databaseName == \"Galebach\") viewof pattern.value = \"t1001\";\n else \n if (databaseName == \"Sá e Sá\") viewof pattern.value = \"HNQT\";\n }\n return comment(\"Checks that the current pattern always exists\")\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":120,"value":"md`

\n## Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":923,"value":"import { bindRadioGroup, bindSliderNumber, bindSelect, bindColor, bindCheckbox, View } from \"@esperanc/inline-inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":77,"value":"import { Vec, Vector, MBR, Ray } from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1433,"value":"import {comment,util_style} from \"@esperanc/notebook-css-utilities\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1436,"value":"util_style","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}