I have noticed even people who claim everything is predestined, and that we can do nothing to change it, look before they cross the road (Stephen Hawking)
Imagine a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge is finding the route which minimizes the total length of the trip. This is the Travelling Salesman Problem (TSP): one of the most profoundly studied questions in computational mathematics. Since you can find a huge amount of articles about the TSP in the Internet, I will not give more details about it here.
In this experiment I apply an heuristic algorithm to solve the TSP to draw a portrait. The idea is pretty simple:
Load a photo
Convert it to black and white
Choose a sample of black points
Solve the TSP to calculate a route among the points
Plot the route
The result is a single line drawing of the image that you loaded. To solve the TSP I used the arbitrary insertion heuristic algorithm (Rosenkrantz et al. 1977), which is quite efficient.
Apriétame bien la mano, que un lucero se me escapa entre los dedos (Coda Flamenca, Extremoduro)
I have the privilege of being teacher at ESTALMAT, a project run by Spanish Royal Academy of Sciences that tries to detect, guide and stimulate in a continuous way, along two courses, the exceptional mathematical talent of students of 12-13 years old. Some weeks ago I gave a class there about the importance of programming. I tried to convince them that learning R or Python is a good investment that always pays off; It will make them enjoy more of mathematics as well as to see things with their own eyes. The main part of my class was a workshop about Voronoi tesselations in R. We started drawing points on a circle and we finished drawing mandalas like these ones. You can find the details of the workshop here (in Spanish). It was a wonderful experience to see the faces of the students while generating their own mandalas.
In that case all mandalas were empty, ready to be printed and coloured as my 7 years old daughter does. In this experiment I colour them. These are the changes I have done to my previous code:
Remove external segments which intersects the boundary of the enclosing
Convert the tesselation into a list of polygons with tile.list function
Use colourlovers package to fill the polygons with beautiful colour palettes
This is an example of the result:
Changing three simple parameters (iter, points and radius) you can obtain completely different images (clicking on any image you can see its full size version):
You can find details of these parameters in my previous post. I cannot resist to place more examples:
Mathematics is a place where you can do things which you can’t do in the real world (Marcus Du Sautoy, mathematician)
From time to time I have a look to some of my previous posts: it’s like seeing them through another’s eyes. One of my first posts was this one, where I draw fractals using the Multiple Reduction Copy Machine (MRCM) algorithm. That time I was not clever enough to write an efficient code able generate deep fractals. Now I am pretty sure I could do it using ggplot and I started to do it when I come across with the idea of mixing this kind of fractal patterns with Voronoi tessellations, that I have explored in some of my previous posts, like this one. Mixing both techniques, the mandalas appeared.
I will not explain in depth the mathematics behind this patterns. I will just give a brief explanation:
I start obtaining n equidistant points in a unit circle centered in (0,0)
I repeat the process with all these points, obtaining again n points around each of them; the radius is scaled by a factor
I discard the previous (parent) n points
I repeat these steps iteratively. If I start with n points and iterate k times, at the end I obtain nk points. After that, I calculate the Voronoi tesselation of them, which I represent with ggplot.
Most of them are made with ggplot2 package. I love R and the sense of wonder of how just one or two lines of code can create beautiful and unexpected patterns.
I recently did this project for DataCamp to show how easy is to do art with R and ggplot. Starting from a extremely simple plot, and following a well guided path, you can end making beautiful images like this one:
Furthermore, you can learn also ggplot2 while you do art.
I have done the project together with Rasmus Bååth, instructor at DataCamp and the perfect mate to work with. He is looking for people to build more projects so if you are interested, here you can find more information. Do not hesitate to ask him for details.
For me, mathematics cultivates a perpetual state of wonder about the nature of mind, the limits of thoughts, and our place in this vast cosmos (Clifford A. Pickover – The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics)
I am a big fan of Clifford Pickover and I find inspiration in his books very often. Thanks to him, I discovered the harmonograph and the Parrondo’s paradox, among many other mathematical treasures. Apart of being a great teacher, he also invented a family of strange attractors wearing his name. Clifford attractors are defined by these equations:
There are infinite attractors, since a, b, c and d are parameters. Given four values (one for each parameter) and a starting point (x0, y0), the previous equation defines the exact location of the point at step n, which is defined just by its location at n-1; an attractor can be thought as the trajectory described by a particle. This plot shows the evolution of a particle starting at (x0, y0)=(0, 0) with parameters a=-1.24458046630025, b=-1.25191834103316, c=-1.81590817030519 and d=-1.90866735205054 along 10 million of steps:
Changing parameters is really entertaining. Drawings have a sandy appearance:
From a technical point of view, the challenge is creating a data frame with all locations, since it must have 10 milion rows and must be populated sequentially. A very fast way to do it is using Rcpp package. To render the plot I use ggplot, which works quite well. Here you have the code to play with Clifford Attractors if you want:
Blue dragonflies dart to and fro
I tie my life to your balloon and let it go
(Warm Foothills, Alt-J)
In my last post I did some drawings based on L-Systems. These drawings are done sequentially. At any step, the state of the drawing can be described by the position (coordinates) and the orientation of the pencil. In that case I only used two kind of operators: drawing a straight line and turning a constant angle. Today I used two more symbols to do stack operations:
“[“ Push the current state (position and orientation) of the pencil onto a pushdown
“]” Pop a state from the stack and make it the current state of the pencil (no line is drawn)
These operators allow to return to a previous state to continue drawing from there. Using them you can draw plants like these:
Each image corresponds to a different axiom, rules, angle and depth. I described these terms in my previous post. If you want to reproduce them you can find the code below (each image corresponds to a different set of axiom, rules, angle and depth parameters). Change colors, add noise to angles, try your own plants … I am sure you will find nice images:
L-Systems were conceived in 1968 by Aristide Lindenmayer, a Hungarian biologist, as a mathematical description of plant growth. Apart from the Wikipedia, there are many places on the Internet where you can read about them. If you are interested, don’t miss The Algorithmic Beauty of Plants, an awesome book by Przemysław Prusinkiewicz that you can obtain here for free.
Roughly speaking, a L-System is a very efficient way to make drawings. In its simplest way consists in two different actions: draw a straigh line and change the angle. This is just what you need, for example, to draw a square: draw a straigh line of any length, turn 90 degrees (without drawing), draw another straigh line of the same length, turn 90 degrees in the same direction, draw, turn and draw again. Denoting F as the action of drawing a line of length d and + as turning 90 degrees right, the whole process to draw a square can be represented as F+F+F+F.
L-Systems are quite simple to program in R. You only need to substitute the rules iteratively into the axiom (I use gsubfn function to do it) and split the resulting chain into parts with str_extract_all, for example. The result is a set of very simple actions (draw or turn) that can be visualized with ggplot and its path geometry. There are four important parameters in L-Systems:
The seed of the drawing, called axiom
The substitutions to be applied iteratively, called rules
How many times to apply substitutions, called depth
Angle of each turning
For example, let’s define the next L-System:
Rule:F → F−F+F+FF−F−F+F
The rule means that every F must be replaced by F−F+F+FF−F−F+F while + means right turning and - left one. After one iteration, the axiom is replaced by F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F and iterating again, the new string is F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F. As you can see, the length of the string grows exponentially. Converting last string into actions, produces this drawing, called Koch Island:
It is funny how different axioms and rules produce very different drawings. I have done a Shiny App to play with L-systems. Although it is quite simple, it has two interesting features I would like to undeline:
Delay reactions with eventReactive to allow to set depth and angle values before refreshing the plot
Build a dynamic UI that reacts to user input depending on the curve choosen
There are twelve curves in the application: Koch Island (and 6 variations), cuadratic snowflake, Sierpinsky triangle, hexagonal Gosper, quadratic Gosper and Dragon curve. These are their plots:
The definition of all these curves (axiom and rules) can be found in the first chapter of the Prusinkiewicz’s book. The magic comes when you modify angles and colors. These are some examples among the infinite number of possibilities that can be created:
I enjoyed a lot doing and playing with the app. You can try it here. If you do a nice drawing, please let me know in Twitter or dropping me an email. This is the code of the App:
Andar, lo que es andar, anduve encima siempre de las nubes (Del tiempo perdido, Robe)
If you give importance to colours, maybe you know already COLOURlovers. As can be read in their website, COLOURlovers is a creative community where people from around the world create and share colors, palettes and patterns, discuss the latest trends and explore colorful articles… All in the spirit of love.
There is a R package called colourlovers which provides access to the COLOURlovers API. It makes very easy to choose nice colours for your graphics. I used clpalettes function to search for the top palettes of the website. Their names are pretty suggestive as well: Giant Goldfish, Thought Provoking, Adrift in Dreams, let them eat cake … Inspired by this post I have done a Shiny app to create colored flowers using that palettes. Seeds are arranged according to the golden angle. One example:
Remember me, remember me, but ah! forget my fate (Dido’s Lament, Henry Purcell)
A Voronoi diagram divides a plane based on a set of original points. Each polygon, or Voronoi cell, contains an original point and all that are closer to that point than any other.
This is a nice example of a Voronoi tesselation. You can find good explanations of Voronoi diagrams and Delaunay triangulations here (in English) or here (in Spanish).
A grayscale image is simply a matrix where darkness of pixel located in coordinates (i, j) is represented by the value of its corresponding element of the matrix: a grayscale image is a dataset. This is a Voronoi diagraman of Frankenstein:
Obtain a random sample of black pixels (previous image corresponds to a sample of 6.000 points)
Computes the Voronoi tesselation
Steps 1 to 3 were done with imager, a very appealing package to proccess and analice images. Step 5 was done with deldir, also a convenient package which computes Delaunay triangulation and the Dirichlet or Voronoi tessellations.
The next grid shows tesselations for sample size from 500 to 12.000 points and step equal to 500:
I gathered all previous images in this gif created with magick, another amazing package of R I discovered recently:
This is the code:
# Download the image
download.file(file, destfile = "frankenstein.jpg", mode = 'wb')
# Read and convert to grayscale
load.image("frankenstein.jpg") %>% grayscale() -> x
# This is just to define frame limits
summarize(xmin=min(x), xmax=max(x), ymin=min(y), ymax=max(y)) %>%
# Filter image to convert it to bw
as.data.frame() -> df
# Function to compute and plot Voronoi tesselation depending on sample size
doPlot = function(n)
sample_n(n, weight=(1-value)) %>%
deldir(rw=rw, sort=TRUE) %>%
.$dirsgs -> data
# This is just to add some alpha to lines depending on its longitude
alpha=findInterval(long, quantile(long, probs = seq(0, 1, length.out = 20)))/21)-> data
# A little bit of ggplot to plot results
geom_segment(aes(x = x1, y = y1, xend = x2, yend = y2), color="black", lwd=1) +
theme(legend.position = "none",
panel.background = element_rect(fill="white"),
axis.ticks = element_blank(),
panel.grid = element_blank(),
axis.title = element_blank(),
axis.text = element_blank())->plot
# I call the previous function and store resulting plot in jpeg format
jpeg(name, width = 600, height = 800, units = "px", quality = 100)
# Once all images are stored I can create gif
for (i in length(images):1)
c(x, frames) -> frames
animation=image_animate(frames, fps = 2)
Go ahead stomp your feet on the floorboards
Clap your hands if that’s really what you came here for
(Heaven, The Milk Carton Kids)
Inspired by curves created by the harmonograph, I have done a Shiny app to generate random images that you can personalize and use as an Exlibris. You can try the App here. For me, an exlibris (also known as bookplates) can be a nice, original and useful present for book-lovers. This is an example:
I always put the code at the end of my posts. Since I always have doubts about how many people are interested in what I do, today will be different. I will share the code with those who ask it to me in any of the following ways: