{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Designing the JuliaCon 2019 T-shirt"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Cormullion and David P. Sanders"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We offered to design some graphics for the JuliaCon 2019 T-shirt. Several ideas were proposed, and were received variously with “meh” or “cool”, and there was much enjoyable bike-shedding. Eventually, a design derived from the [Penrose tiling](https://en.wikipedia.org/wiki/Penrose_tiling) was developed, using Julia code."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this notebook we explain some of the steps in arriving at the final design."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The basic drawing was made using [Luxor.jl](https://github.com/JuliaGraphics/Luxor.jl), and the algorithms for resolving the colouring used [LightGraphs]( https://github.com/scheinerman/SimpleGraphs.jl)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Penrose tilings"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A Penrose tiling is a tiling (covering) of the plane using two particular tile types."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The surprising thing is that the tiling turns out to be *quasiperiodic*: it never repeats itself, but does “almost repeat itself”."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A common method to produce Penrose tilings is the method of **inflation–deflation**: we start with a given set of tiles and recursively replace each tile with a certain combination of smaller tiles."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this implementation, we build everything out of triangles, represented by the following `struct`. Here, `A`, `B` and `C` are the 3 points in the triangle, `Point` is a type from `Luxor` representing the coordinates of a point in 2D, and `flag` is a Boolean variable representing the “type” of triangle."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"using Luxor\n",
"using LightGraphs\n",
"using Random\n",
"\n",
"struct PenroseTriangle\n",
" flag::Bool\n",
" A::Point\n",
" B::Point\n",
" C::Point\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We start by generating $n$ triangles in a circle with center $c$ and radius $r$. The `polar` function generates a vector with given radius and angle"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"initialize (generic function with 3 methods)"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function initialize(center::Point, r=100, n=10)\n",
" penrosetriangles = PenroseTriangle[]\n",
" A = center\n",
" for i in 1:n\n",
" ϕ = (i - 1) * (2π / n)\n",
" C = A + polar(r, ϕ)\n",
"\n",
" ϕ = (i) * (2π / n)\n",
" B = A + polar(r, ϕ)\n",
"\n",
" if i % 2 == 1\n",
" triangle = PenroseTriangle(true, B, A, C)\n",
" else\n",
" triangle = PenroseTriangle(true, C, A, B)\n",
" end\n",
" push!(penrosetriangles, triangle)\n",
" end\n",
" return penrosetriangles\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's draw these triangles. For now we can just apply a polygon-drawing function `poly()` to the triangles. (And we're currently working in global scope, which you'll want to be aware of!)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"@svg begin\n",
" for triangle in initialize(O, 150)\n",
" randomhue()\n",
" poly([triangle.A, triangle.B, triangle.C], close=true, :stroke)\n",
" end\n",
"end 500 300 \"figure1\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we subdivide recursively using the following function:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"subdivide (generic function with 1 method)"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function subdivide(penrosetriangles::Vector{PenroseTriangle})\n",
" result = PenroseTriangle[]\n",
" for triangle in penrosetriangles\n",
" A, B, C = triangle.A, triangle.B, triangle.C\n",
"\n",
" if triangle.flag\n",
" Q = A + (B - A) / MathConstants.golden\n",
" R = B + (C - B) / MathConstants.golden\n",
" push!(result, PenroseTriangle(false, R, Q, B))\n",
" push!(result, PenroseTriangle(true, Q, A, R))\n",
" push!(result, PenroseTriangle(true, C, A, R))\n",
" else\n",
" P = C + (A - C) / MathConstants.golden\n",
" push!(result, PenroseTriangle(false, B, P, A))\n",
" push!(result, PenroseTriangle(true, P, C, B))\n",
" end\n",
" end\n",
" return result\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see the result of a single subdivision. We can use `foldl()` to run `subdivide()` a number of times."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"@svg begin\n",
" penrosetriangles = foldl((x, y) -> subdivide(x), 1:1, init=initialize(O, 150))\n",
" setlinecap(\"butt\")\n",
" setlinejoin(\"bevel\")\n",
" setline(2)\n",
" for triangle in penrosetriangles\n",
" p = [triangle.A, triangle.B, triangle.C]\n",
" ispolyclockwise(p) && reverse!(p)\n",
" poly(p, close=true, :stroke)\n",
" end\n",
" # draw 2 more levels\n",
" penrosetriangles = foldl((x, y) -> subdivide(x), 1:2, init=initialize(O, 150))\n",
" setopacity(0.5)\n",
"\n",
" for triangle in penrosetriangles\n",
" randomhue()\n",
" p = [triangle.A, triangle.B, triangle.C]\n",
" ispolyclockwise(p) && reverse!(p)\n",
" poly(p, close=true, :fill)\n",
" end\n",
"end 500 300 \"figure2\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The more levels you recurse to, the richer and more complex the pattern:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"@svg begin\n",
" setlinecap(\"butt\")\n",
" setlinejoin(\"bevel\")\n",
" setline(1)\n",
" # draw first level\n",
" penrosetriangles = foldl((x, y) -> subdivide(x), 1:1, init=initialize(O, 150))\n",
"\n",
" for triangle in penrosetriangles\n",
" poly([triangle.A, triangle.B, triangle.C], close=true, :stroke)\n",
" end\n",
" # draw 4 more levels\n",
" setopacity(0.5)\n",
" penrosetriangles = foldl((x, y) -> subdivide(x), 1:4, init=initialize(O, 150))\n",
"\n",
" for triangle in penrosetriangles\n",
" randomhue()\n",
" poly([triangle.A, triangle.B, triangle.C], close=true, :fill)\n",
" end\n",
"end 500 300 \"figure3\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This provides the basis for our Penrose-inspired design."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Colouring the triangles"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A Penrose tiling can be thought of as a planar map, and the [Four-colour Theorem](https://en.wikipedia.org/wiki/Four_color_theorem) says that any map of the plane can be coloured using at most 4 colours. Here, a map colouring is one in which neighbouring \"countries\" are coloured by different colours if they are joined by an edge (not just a point)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Since there are 4 colours in the Julia logo, we decided to find the perfect colouring of our Penrose tiling using the Julia colours!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Mapping to a graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To do so, we think of the collection of triangles as a **graph** or **network**, i.e. a collection of vertices joined by edges. We need to find the **adjacency matrix** of the graph, i.e. a matrix $A_{ij}$ which contains $1$ if nodes $i$ and $j$ are connected, and $0$ if they are not connected."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The problem is that the inflation–deflation method that we are using to construct the triangles gives us no information about which triangles are neighbours (at least, we are not aware of how to directly extract this information from the construction)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hence, the first thing to do is to extract the adjacency matrix, for which we just use brute force: given two triangles, we calculate the distances between each of their vertices. If exactly two of these distances are (approximately) zero, then those two vertices coincide, and hence the two triangles share an edge:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"incidence_matrix (generic function with 1 method)"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function incidence_matrix(ptriangles::Vector{PenroseTriangle})\n",
" n = length(ptriangles)\n",
" g = SimpleGraph(n)\n",
"\n",
" for i in 1:n\n",
" for j in i+1:n\n",
" ti = ptriangles[i]\n",
" tj = ptriangles[j]\n",
"\n",
" points_i = [ti.A, ti.B, ti.C]\n",
" points_j = [tj.A, tj.B, tj.C]\n",
"\n",
" coincidental = 0\n",
" tol = 1e-2\n",
"\n",
" for k in 1:3, l in 1:3\n",
" if distance(points_i[k], points_j[l]) < tol\n",
" coincidental += 1\n",
" end\n",
" end\n",
"\n",
" if coincidental == 2 # share edge\n",
" add_edge!(g, i, j)\n",
" end\n",
" end\n",
" end\n",
" return g\n",
"end"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Use this to create an incidence matrix for our triangles, and we'll draw the graph over the triangles, to show what's going on."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"function drawgraph()\n",
" penrosetriangles = foldl((x, y) -> subdivide(x), 1:3, init=initialize(O, 150))\n",
"\n",
" @svg begin\n",
" setlinecap(\"butt\")\n",
" setlinejoin(\"bevel\")\n",
" setline(1)\n",
" @layer begin\n",
" setopacity(0.9)\n",
" # Julia colors are built-in to Luxor\n",
" juliacolors = [Luxor.julia_green, Luxor.julia_red,Luxor.julia_purple, Luxor.julia_blue]\n",
" # remove the middle ones:\n",
" outertriangles = PenroseTriangle[]\n",
" for t in penrosetriangles\n",
" t1 = [t.A, t.B, t.C]\n",
" pc1 = polycentroid(t1)\n",
" if distance(pc1, O) > 40\n",
" push!(outertriangles, t)\n",
" end\n",
" end\n",
"\n",
" @show length(outertriangles)\n",
" # draw them with random colors\n",
" for (k, t) in enumerate(outertriangles)\n",
" sethue(juliacolors[rand(1:end)]...)\n",
" t1 = [t.A, t.B, t.C]\n",
" if !ispolyclockwise(t1)\n",
" reverse!(t1)\n",
" end\n",
" poly(offsetpoly(t1, -1), :fill)\n",
" end\n",
" end\n",
" # create graph\n",
" g = incidence_matrix(outertriangles)\n",
" # draw graph over triangles\n",
" for edge in edges(g)\n",
" e, f = src(edge), dst(edge)\n",
"\n",
" st = outertriangles[e]\n",
" ft = outertriangles[f]\n",
"\n",
" stflag = st.flag\n",
"\n",
" t1 = [st.A, st.B, st.C]\n",
" t2 = [ft.A, ft.B, ft.C]\n",
"\n",
" pc1 = polycentroid([st.A, st.B, st.C])\n",
" pc2 = polycentroid([ft.A, ft.B, ft.C])\n",
"\n",
" if !isapprox(pc1, pc2)\n",
" sethue(\"white\")\n",
" circle(pc1, 1.5, :fill)\n",
" circle(pc2, 1.75, :fill)\n",
" sethue(\"black\")\n",
" arrow(between(pc1, pc2, 0.075), between(pc1, pc2, 0.925), arrowheadlength=5,\n",
" arrowheadangle=π/6, linewidth=1)\n",
" end\n",
" end\n",
" end 420 500 \"fig4-network\"\n",
"end\n",
"\n",
"drawgraph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Colouring the graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we want to find a **graph colouring** with the property that adjacent nodes do not share the same colour. This is accomplished by the following lines:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```\n",
"colorsequence = Random.shuffle!(collect(1:length(outertriangles)))\n",
"colouring = LightGraphs.perm_greedy_color(g, colorsequence)\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `perm_greedy_color()` function in LightGraphs uses a “greedy heuristic” to color the graph using the given order."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here’s a function to draw the triangles with the “correct” map coloring:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"function drawgreedy()\n",
" PenroseTriangles = foldl((x, y) -> subdivide(x), 1:3, init=initialize(O, 150))\n",
"\n",
" outertriangles = PenroseTriangle[]\n",
" for t in PenroseTriangles\n",
" t1 = [t.A, t.B, t.C]\n",
" pc1 = polycentroid(t1)\n",
" if distance(pc1, O) > 40\n",
" push!(outertriangles, t)\n",
" end\n",
" end\n",
"\n",
" g = incidence_matrix(outertriangles)\n",
"\n",
" colorsequence = Random.shuffle!(collect(1:length(outertriangles)))\n",
" colouring = LightGraphs.perm_greedy_color(g, colorsequence)\n",
"\n",
" @svg begin\n",
" juliacolors = [Luxor.julia_green, Luxor.julia_red,Luxor.julia_purple, Luxor.julia_blue]\n",
" for (k, t) in enumerate(outertriangles)\n",
" sethue(juliacolors[colouring.colors[k]]...)\n",
" t1 = [t.A, t.B, t.C]\n",
" if !ispolyclockwise(t1)\n",
" reverse!(t1)\n",
" end\n",
" poly(offsetpoly(t1, -1), :fill)\n",
" end\n",
" end 500 300 \"fig5-greedy\"\n",
"end\n",
"\n",
"drawgreedy()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It turns out that for the Penrose tiling, there are rather few nodes that use the fourth colour."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To make the result visually more interesting, we randomly choose approximately a quarter of the nodes to have the 4th colour, provided that none of its neighbours have that colour:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"function tweak()\n",
" PenroseTriangles = foldl((x, y) -> subdivide(x), 1:3, init=initialize(O, 150))\n",
" outertriangles = PenroseTriangle[]\n",
" for t in PenroseTriangles\n",
" t1 = [t.A, t.B, t.C]\n",
" pc1 = polycentroid(t1)\n",
" if distance(pc1, O) > 40\n",
" push!(outertriangles, t)\n",
" end\n",
" end\n",
" g = incidence_matrix(outertriangles)\n",
"\n",
" colorsequence = Random.shuffle!(collect(1:length(outertriangles)))\n",
" colouring = LightGraphs.perm_greedy_color(g, colorsequence)\n",
" n = length(colouring.colors)\n",
"\n",
" for i in 1:n ÷ 4\n",
" which = rand(1:n)\n",
" if 4 ∉ [colouring.colors[x] for x in neighbors(g, which)]\n",
" colouring.colors[which] = 4\n",
" end\n",
" end\n",
" # map(x -> sum(colouring.colors .== x ), 1:4)\n",
" @svg begin\n",
" juliacolors = [Luxor.julia_green, Luxor.julia_red,Luxor.julia_purple, Luxor.julia_blue]\n",
" for (k, t) in enumerate(outertriangles)\n",
" sethue(juliacolors[colouring.colors[k]]...)\n",
" t1 = [t.A, t.B, t.C]\n",
" if !ispolyclockwise(t1)\n",
" reverse!(t1)\n",
" end\n",
" poly(offsetpoly(t1, -1), :fill)\n",
" end\n",
" end 500 300 \"fig6-tweak\"\n",
"end\n",
"\n",
"tweak()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
]
}
],
"metadata": {
"@webio": {
"lastCommId": null,
"lastKernelId": null
},
"kernelspec": {
"display_name": "Julia 1.1.0",
"language": "julia",
"name": "julia-1.1"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.1.0"
}
},
"nbformat": 4,
"nbformat_minor": 3
}