Most of you probably know Vi Hart, but for completeness, I will now introduce her. This human, commonly represented by a happy triangle, self-identifies as a mathemusician and spends most of her time producing math videos. The majority of her videos contain a lot of doodling, and she has even made a playlist entirely devoted to it. Here is the fourth video in that playlist, which I recommend to watch before reading further:
Wait, she suggested writing a program, didn’t she? It sounded like a challenge to me, so I started to think which of her algorithms I could implement. The ones at the beginning seemed too boring, while the ones at the end were far too difficult for me. Finally, after some thinking, I decided to choose the following algorithm:
- Choose two arbitrary shapes, called the Image and the Tile, respectively.
- Scale the Tile up or down so that it neatly fits within the Image and confirm that larger copies of the Tile don’t fit. Rotation of the Tile is disallowed. Skewing disallowed.
- Draw the scaled Tile in the Image. Say that all pixels you changed are not part of the Image any more.
- See step 2.
This is a beautiful algoritm, and of course I spoiled it a bit with my implementation, which has some strange limitations. In particular, the Image and the Tile should be of the same size and they should be saved as BMP files for indetermined reason*.
* When I write “for indetermined reason”, it should be read as “because of me being lazy”.
Still, I am satisfied with my program, and especially with its speed. I initially wanted to do some sort of a binary search, but then understood it was a bad idea. Indeed, the fact that some copy of the Tile doesn’t fit by no means implies that a larger copy won’t fit (hint: think what happens when both the Image and the Tile are U-shaped). As a result, I had to do a bog-standard brute force. However, the program generates vitals (Vi Hart’s fractals) at good pace.
Anyway, I can predict that you are already quite bored by the text and want to see some images. Here they are:
Obviously, nothing interesting will happen if the Image and the Tile are equal triangles with the same orientation. But if you rotate the Tile 180 degrees, you get something familiar:
2816 smiling faces are looking at you from the arrow:
And since the idea belongs to Vi Hart, let’s multiply her logo:
You will definitely blame me for being unable to produce good input pictures and therefore not showing you all power of the program. But I can do nothing with my bad drawing skills, so you will have to make more beautiful things yourself. That program is much more user-friendly than my other creations, you only need to know that the backgrounds of the Image and the Tile should be perfectly white (and if they aren’t, you will immediately see this in the preview).
There is only one minor problem: I don’t know how I can upload and share files so that they stay shared over time. Yandex.Disk’s permalinks broke down recently (fortunately, now they work again), and I have no proof that other services are more reliable. To cut the long story short, I decided to upload the file to two different sites: link 1, link 2.
Anyway, goodbye for now. With the probability of 75% the next post will present a cryptographic challenge, and with the probability of 95% it will not be about probability.