9
$\begingroup$

As part of my work, I create tools for artists to make various types of patterns for artistic purposes. I am trying to make a tool to create a Penrose tiling and I would like to use the pentagrid method of generating it, as it seems like the easiest way to allow the user to arbitrarily scale and translate the plane and still generate a nice random aperiodic tiling that easily stretches to infinity in any direction. Whereas using something like inflation or deflation becomes problematic when the user decides to scale the tile size down or translate by a large amount in any direction.

Given that, I've found several references on the how to generate a tiling from a pentagrid, such as these:

They've been incredibly helpful, but I feel like I'm missing a step. I'm able to generate the pentagrid:

A pentagrid

But when I attempt to generate the tiles, I end up with tiles that are separated:

Not quite a Penrose Tiling

I'm working in Swift and I'm generating the vertexes of each tile by doing the following at each intersection point:

var vertexes: [CGPoint] = []
for i in 0..<testPts.count {
    var nextVertex = intersectionPt
    for gridIndex in 0..<numGrids {
        let normal = e [ gridIndex ]
        let k = ceil((testPts [ i ] • normal) - gamma [ gridIndex ])
        nextVertex += k * normal
    }
    vertexes.append(nextVertex)
}

The testPts array contains 4 points - one in each face of the pentagrid that has a vertex at the intersection point. The e array contains the normals for each direction of the pentagrid. The gamma array contains the offsets of each grid in the pentagrid. Values in gamma are between -1.0 and 1.0.

Is this the expected result? Some of the references I've read have made vague statements about needing to move the tiles together (without suggesting how to do that), while others have seemed to indicate that they'll all fall into the correct positions.

If they do need to be moved together, is there a particular algorithm to do that?

If they don't need to be moved together, then what have I missed or misunderstood?

$\endgroup$

3 Answers 3

6
$\begingroup$

The problem in your code is

 var nextVertex = intersectionPt

which should really be

 var nextVertex = [0, 0]

(or at least a constant for all the tiles you generate).

The formula $\sum_{j=0}^4 n_j \mathbf e_j$ for the corner locations produces coordinates in a fixed coordinate system -- it's not relative to the intersection you start out with!

So the gaps you're seeing correspond to the distances between intersection points in the pentagrid, which you're erroneously adding to the tile coordinates.


A different problem that might bother you after you fix that is that the tiles you generate are too large compared to your pentagrid. You seem to be making the spacing between neighboring pentagrind lines equal to side length of the rhombs -- but the average distance between the "ribbons" corresponding to pentagrid lines is clearly longer than that. The tile side length is the width of a ribbon, and there's plenty of space left over between the ribbons!

A Penrose tiling with several roughly vertical ribbons marked
(Image from https://www.ams.org/publicoutreach/feature-column/fcarc-ribbons)

This is not a problem for generating an infinite tiling, but it will make it difficult to predict which part of the pentagrid to look for intersections in, if you want to find all the tiles in a particular area of the coordinate system.

Curiously, none of your references seem to mention this difference in scale explicitly -- those that give actual formulas seem to assume that the lines on the pentagrid are unit spaced and that the rhomb sides are a unit apart. However, those references also don't actually show the complete pentagrid in the same plane as the finished Penrose tiling. Apparently in their view the pentagrid is only there to define which coordinate sets in $\mathbb Z^5$ correspond to corner points in the tiling, but the actual tiles live in a completely different coordinate system.

If you want each tile corner to appear roughly in the vicinity of the region of the pentagrid that corresponds to it, you need to scale one of the coordinate systems to match. Your sources don't give you the scaling factor to use, so let's derive it. We'll keep the tile side lengths as $1$, and figure out how far apart the pentagrid lines must be.

Suppose we're in the region of the pentagrid in your question with 5-coordinate tuple $(0,0,0,0,0)$, and we now move some large distance $D$ due right. What is the five-tuple corresponding to the region we land in, if the grid spacing is $G$?

Well, we move past $\frac DG$ red lines, crossing them at right angles. The orange lines make an angle of $72^\circ$ with the red ones, so the number of them we cross is an integer close to $\frac DG \cos 72^\circ$. The rounding becomes negligible when we let $D$ got to infinity, so just pretend it is $\frac DG\cos 72^\circ$ exactly. Similarly, the green lines make an angle of $144^\circ$ to the red ones, so the number of them we cross is $\frac DG \cos 144^\circ$. (The factor $\cos 144^\circ$ is negative, corresponding to the fact that we cross these lines in the direction of decreasing region coordinates). And so forth with the cyan and blue, with angles of $216^\circ$ and $288^\circ$.

All in all, we end up with the 5-coordinates, up to rounding $$ (n_0,n_1,n_2,n_3,n_4) \approx \bigl(\tfrac DG,\tfrac DG\cos 72^\circ,\tfrac DG\cos 144^\circ,\tfrac DG\cos 216^\circ,\tfrac DG\cos 288^\circ\bigr). $$

The coordinates of the tile corner corresponding to that region is $$ \sum_{j=0}^4 n_j \mathbf e_j = \sum_{j=0}^4 n_j \bigl(\cos(j\cdot 72^\circ), \sin(j\cdot 72^\circ)\bigr). $$ We're just interested in the $x$-coordinate, so plug in the $n_j$s above to get $$ x \approx \frac DG \sum_{j=0}^4 \cos^2(j\cdot 72^\circ) = \frac DG \sum_{j=0}^4 \frac{1 - \cos(j\cdot 144^\circ)}2 = \frac DG \cdot \frac{5-\sum_{j=0}^4 \cos(j\cdot 144^\circ)}2 = \frac DG \cdot \frac52 . $$ (The last equals sign is because the sum of cosines is the change in $x$-coordinate from going all the way around a pentagram with unit sides).

If this $x$ is to grow at the same average rate as $D$, we must set $$ G = \frac52. $$


Beware, however, that even if you scale the grid by this factor, you still won't get closer than the tiles being "roughly in the vicinity" of the grid intersections that represent them. The nice images in the presentations you link to make it look like each rhombus will contain the grid intersection it comes from -- but it's not possible to align the grid such that this is always the case, nor such that every tile corner is inside the grid region that you compute its location from.

The pentagrid contains places where five grid lines almost but not quite meet in a point, like in this region of your pentagrid:

five lines almost meet

In this particular almost-intersection the fit is loose enough that we can see it's not exact -- but if your continue the pentagrid far enough, you will eventually find places where almost-intersections like this take place within arbitrarily small areas. The configuration has 6 internal regions and 10 actual intersections, and each of those intersections generates a full-sized tile in the final tiling. The 10 tiles come together in this pattern:

the part of the tiling arising from a single almost-intersection

whose diameter is somewhat larger than the pentagrid spacing! Clearly not all of the tiles can lie directly above their defining intersection.

(We can see a differently oriented instance of this pattern in your buggy picture. Those tiles have particularly small gaps between them because the intersections that represent them are close together).

$\endgroup$
1
  • $\begingroup$ Wow! Thank you so much for your help on this. Sure enough, you are correct about the error in my code. I'll need a little time to absorb the second part of your answer, but this will come in very handy. $\endgroup$ May 6, 2021 at 0:33
5
$\begingroup$

Well I think I figured it out. The key is to keep track of which intersections of which grid lines are associated with each tile. Choose a starting tile and say that it is aligned. Then take each of the 4 tiles that were generated from the previous and next intersections of the 2 intersecting grid lines and move them towards the current tile until they touch. Then do the same for each tile you just moved, etc., until you've aligned all the tiles. In code it looks something like this (after adding the first tile to the queue):

    while (!queue.isEmpty) {
        // get the front element of the queue
        let startingTile = queue [ 0 ]
        queue.remove(at: 0)

        // find the (up to) 4 tiles that are adjacent to it
        let adjacentTiles = startingTile.unalignedAdjacentTiles()

        // for each tile we found
        for adjacentTile in adjacentTiles {
            // move it to touch this tile
            let offset = startingTile.minimumOffsetTo(adjacentTile)
            adjacentTile.realign(by: offset)

            // mark it as aligned
            adjacentTile.aligned = true

            // add it to the queue
            queue.append(adjacentTile)
        }
    }

Doing that, I get results like this:

A correct Penrose tiling

$\endgroup$
1
$\begingroup$

Somehow I think it's strange that you have to move the tiles. For instance, in this Desmos demonstration, I've generated the tiles for the associated intersections in the pentagrid without having to move them.

https://www.desmos.com/calculator/g4wcmzmn3s

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .