Quilt block permutations
How to see ALL the possibilities?
I had the idea that I wanted to be able to print out, or display, ALL possible combinations of a particular set of shapes arranged in a block suitable for quilting.
Initially I looked at random orientations, but soon realised that symmetry was important to be aesthetically pleasing. So I then decided to study the different types of symmetry and print/display ALL symmetrical combinations. How practical is this going to be, though? It depends on the numbers involved. In the table below I list the numbers of permutations. In words, the total number of permutations is the number of shapes to the power of the number of items in a block.
Number of shapes in a block (numInBlock) | |||
numShapes | 2×2 = 4 | 3×3 = 9 | 4×4 = 16 |
2 | 16 | 512 | 65,536 |
4 | 256 | 262,144 | 4,294,967,296 |
6 | 1,296 | 10,077,696 | 2.821e12 |
8 | 4,096 | 134,217,728 | 2.815e14 |
10 | 10,000 | 1,000,000,000 | 1.000e16 |
12 | 20,736 | 5,159,780,352 | 1.849e17 |
14 | 38,416 | 2.066e10 | 2.177e18 |
In processing code:
numPermutations = pow(numShapes, numInBlock);
Looking at the table you can see that very rapidly, as you increase the number of shapes and size of a block, the number of permutations approaches infinity, for all practical purposes, and the idea of printing one block per page in a book is out of the question, even printing 12 to a page wouldn’t really work, and who would have the time to look through such a book or have use of it?
The numbers in the table above are for random combinations of shape, but what if you restrict to particular symmetries? At first I was wondering how you could produce random shapes and then test if they had symmetry and reject if they didn’t, but I realised that was over complicating things, the way to do it was to build in the symmetry from the start.
Translate, Rotate, Mirror, Inverse
The 3 symmetries I have investigated are Translate (T), Rotate (R) and Mirror (M). I am thinking about quilt patterns where the shapes are made up of two contrasting colours/tones, so I’m also interested in the symmetries through inversion of a shape, ie where black becomes white and white becomes black. I can explain this better in diagram form.
In the image below there are 6 possible shapes shown in the column on the right. These are deliberately listed in inverse pairs, as that helps with the coding later. So shape 0 is the inverse of shape 1, shape 2 is the inverse of shape 3 and shape 4 is the inverse of shape 5, and shape 6 is the inverse of shape 7. I’ve started the numbering at 0 to fit in with processing code, both for cases using the switch() function and for arrays. You may also notice in this example that shapes 0 to 4 are actually the same shape rotated. Also shapes 4 and 6 are the same but rotated HALF_PI, similarly 5 and 7.
Any 4 of these shapes are selected to make a block of 2 x 2. From the table above, with 8 shapes, there are 4,096 permutations for a block of 2 x 2. The particular combination of the 2×2 block for this diagram is shown at the top right of the image. I have used an array for my code and the numbers underneath each block are the row of the array followed by the 4 shape case numbers in that row of the array, listed left to right, top to bottom.
Of the 12 (4 x 3) blocks of 4 x 4 cases, the first row of 4 blocks are all Translation symmetry, the second row are all Rotational symmetry, and the final row are all Mirror symmetry. Then the variations of those symmetries are using the inverse shapes in a diagonal and then left to right and top to bottom.
In this particular example it would appear on first inspection that all of the blocks in the columns are the same, but do look more closely. That is just an effect without looking at the lines in the centre of each shape, and this example was just chosen to emphasise the inverse element.
Permutations
Coming back to the number of permutations, this method would produce all of the symmetrical permutations for a block of 4×4 = 16. The number of permutations would be 4,096 x 12 = 49,152. Compare that to 2.815e14 = 281,500,000,000,000 random permutations for 4×4 block using 8 shapes.
If there were 4 of these diagrams to a page that would be a book of 1,024 pages. That is still a lot of pages and a very dull book. You could think of putting more and more diagrams per page but that would then make each block very small and hard to see.
So I thought about making videos. I’ve set up the code to produce an array of all of the permutations of a 2×2 block with a given number of shape cases. Then to produce the diagram with the 12 symmetry options, one for each frame in the draw() section scrolling through each row of the array in sequence. For the very large numbers I have the starting row from the array selected at random then carry in sequence (and then start at the beginning when get to the end of the array).
Here is an example video using 6 shape cases.
How long will a video be?
There is an issue with the video of what frame rate to use for it to be possible to see each set for a reasonable amount of time to take it in, and the overall length of the video. In the table below I have shown how long a video will be for some of the lower number of frames from the previous table.
Frames per second | |||
Num of frames | 4 | 1 | 0.5 |
16 | 4 sec | 16 sec | 32 sec |
256 | 1 min 4 secs | 4 mins 16 secs | 8.5 mins |
512 | 2 mins 8 secs | 8.5 mins | 17 mins |
1,296 | 5.4 mins | 21.6 mins | 43.2 mins |
4,096 | 17.07 mins | 1 hr 8.3 mins | 2 hrs 16.6 mins |
10,000 | 41.67 mins | 2 hrs 46.67 mins | 5 hours 33.34 mins |
20,736 | 1 hr 26.4 mins | 5 hours 45.6 mins | |
38,416 | 2 hrs 40 mins | ||
65,536 | 4 hrs 33 mins | ||
262,144 | 18.2 hours |
A speed of 4 frames per second is too fast to actually look at each frame. 1 second or 2 seconds you can just about do it but not really remember what you have seen. But the idea of a video for me is you can pause it at any combinations that catch your eye. I think any video longer than an hour is not really a useful item.
There is a method in processing for saving an image of every frame and then turning that into a video, but that seems to me it would use up a lot of storage space and be quite time consuming to do. Instead I used screen capture software. The software I have for screen capture will only save in .wmv format and I wanted to add a title and credits and convert to .mp4 format, so I did that in Microsoft Movie Maker. From start to complete video took a few hours but while the video is rendering, which is the lengthiest part, you can just leave it running and do other things.
Since videos are 50 or 60 frames per second, I speeded things up by running the sketch with a faster frame rate (5ps) while recording, then in the editing I slowed it down to see the individual images. It speeded up the production process but I think it has made the video a bit jerky.
I transferred the video on to my android tablet and found that quite a satisfying way to look at since I could pause the video, move back and forth to different sections by moving the scroll bar and see whichever frame I wanted for as long as I want.
Next steps
In the process of making and looking at this video and several others, I have realised that in some cases the rotational symmetry and mirror symmetry options are the same, and in others the translational inverse options and the mirror symmetry options are the same. So that has started me thinking about how to model this and to therefore reduce the number over all by not repeating any shapes that are the same. It is hard to work out how to do it though.
Gallery
These are few of the other shape combinations and colours I have experimented with, just sample frames.
where is the actual code?
I haven’t put the code for this anywhere online. It’s just on my laptop. Obviously there is different code for the different examples. It’s a while since I did any of this. These are just my notes and thoughts as a record for myself, but shared in case the thinking process helps anyone else. Are you learning Processing?
yes