{"id":403,"date":"2016-01-29T08:37:29","date_gmt":"2016-01-29T13:37:29","guid":{"rendered":"https:\/\/blogs.mathworks.com\/graphics\/?p=403"},"modified":"2016-02-04T09:09:28","modified_gmt":"2016-02-04T14:09:28","slug":"tiling-hexagons-and-other-permutohedra","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/graphics\/2016\/01\/29\/tiling-hexagons-and-other-permutohedra\/","title":{"rendered":"Tiling Hexagons and Other Permutohedra"},"content":{"rendered":"

In earlier posts we've looked at tiling quadrilaterals<\/a> and pentagons<\/a>. So what about hexagons? I'm sure you've seen tilings of regular hexagons. They're popular in floor tiles and game tiles. Even bees know about this one. But there's one interesting feature of this tiling that you might not be familiar with. To see this feature, we need to start in a very different place.<\/p>

We're going to start by making all of the permutations of the sequence [1 2 3]. As you probably know, for n items, there are n! permutations. So there are 6 different ways we can arrange these 3 numbers.<\/p>

n = 3;\r\nnp = factorial(n);\r\npts = perms(1:n)\r\n<\/pre>
\r\npts =\r\n\r\n     3     2     1\r\n     3     1     2\r\n     2     3     1\r\n     2     1     3\r\n     1     2     3\r\n     1     3     2\r\n\r\n<\/pre>
Now we have an array with 6 rows and 3 columns. Since we have 3 columns, I'm just going to go ahead and use them as coordinates in 3D space. That gives me 6 points that I can draw with the stem3 function<\/a>.<\/p>
stem3(pts(:,1),pts(:,2),pts(:,3),'filled'<\/span>)\r\n<\/pre>\"\" 
These points are all arranged on the edges of a box that goes from 1 to 3 along each axis.<\/p>
lx = [1 3 3 1 1 nan 1 3 3 1 1 nan 1 1 nan 3 3 nan 3 3 nan 1 1 nan];\r\nly = [1 1 3 3 1 nan 1 1 3 3 1 nan 1 1 nan 1 1 nan 3 3 nan 3 3 nan];\r\nlz = [1 1 1 1 1 nan 3 3 3 3 3 nan 1 3 nan 1 3 nan 1 3 nan 1 3 nan];\r\nline(lx,ly,lz,'Color'<\/span>,[.75 .75 .75])\r\nxlim([0.5 3.5])\r\nylim([0.5 3.5])\r\nzlim([0.5 3.5])\r\n<\/pre>\"\" 
Let's add some labels so we can see what we've got.<\/p>
xlabel X<\/span>\r\nylabel Y<\/span>\r\nzlabel Z<\/span>\r\nnodelabels = cellstr(arrayfun(@(x)sprintf('%d'<\/span>,x),pts));\r\nfor<\/span> i=1:np\r\n    text(pts(i,1),pts(i,2),pts(i,3)+.1,nodelabels{i,1}, ...<\/span>\r\n        'HorizontalAlignment'<\/span>,'center'<\/span>, ...<\/span>\r\n        'VerticalAlignment'<\/span>,'baseline'<\/span>, ...<\/span>\r\n        'FontSize'<\/span>,16);\r\nend<\/span>\r\n<\/pre>\"\" 
Now I want to connect each pair of points that are on the same face of the cube. One way to do that is like this:<\/p>
edges = [];\r\nfor<\/span> i=1:np\r\n    for<\/span> j=(i+1):np\r\n        diff = pts(j,:) - pts(i,:);\r\n        if<\/span> isscalar(find(diff==-1)) && isscalar(find(diff==1)) && (n-2)==length(find(diff==0))\r\n            edges(end+1,:) = [i j];\r\n        end<\/span>\r\n    end<\/span>\r\nend<\/span>\r\ng = graph(edges(:,1),edges(:,2));\r\no = dfsearch(g,1);\r\nf = [o; 1];\r\nline(pts(f,1),pts(f,2),pts(f,3))\r\nf = o';\r\n<\/pre>\"\" 
You can probably already see that these form a hexagon. Let's emphasize that by creating a patch from them, and rotating around to get a better view.<\/p>
cla\r\ncols = lines(7);\r\npatch('Faces'<\/span>,f,'Vertices'<\/span>,pts,'FaceColor'<\/span>,cols(1,:))\r\nview([120 30])\r\n<\/pre>\"\" 
And if we stacked an infinite number of boxes and intersected them all with that same plane, we would get a number of different hexagons, tiled in the familiar pattern.<\/p>
cla\r\nvec1 = pts(f(5),:) - pts(f(3),:);\r\nvec2 = pts(f(5),:) - pts(f(1),:);\r\np = gobjects(0);\r\nfor<\/span> i=-4:4\r\n    for<\/span> j=-4:4\r\n        cindex = 1+mod(2*mod(i,2) + 1*mod(j,2),7);\r\n        tmp_pts = pts + repmat(i*vec1,[np 1]) + repmat(j*vec2,[np 1]);\r\n        p(end+1) = patch('Faces'<\/span>,f,'Vertices'<\/span>,tmp_pts,'FaceColor'<\/span>,cols(cindex,:));\r\n    end<\/span>\r\nend<\/span>\r\nxlim([-2 6])\r\nylim([-2 6])\r\nzlim([-2 6])\r\n<\/pre>\"\" 
And because all of these patches line in a plane, we can project them into 2D using a pair of basis vectors which are tangent to the plane.<\/p>
uvec = [1, 0, 0];\r\nvvec = [0, sqrt(2)\/2, -sqrt(2)\/2];\r\n\r\nfor<\/span> i=1:numel(p)\r\n    v3 = p(i).Vertices;\r\n    x = sum(v3 .* repmat(uvec,[np 1]),2);\r\n    y = sum(v3 .* repmat(vvec,[np 1]),2);\r\n    p(i).Vertices = [x, y, zeros(np,1)];\r\nend<\/span>\r\n<\/pre>\"\" 
And now we have the familiar 2D tiling of regular hexagons.<\/p>
view(2)\r\naxis off<\/span>\r\n<\/pre>\"\" 
That's kind of an odd way to think about hexagonal tilings, isn't it? But it's actually useful because of one surprising fact. And that is that this trick works in any dimension!<\/p>
If we did this in 2D, we'd get a line connecting the points [1 2] and [2 1]. What if we did it in 4D? Let's give it a try, and see what we get.<\/p>
This time we'll get an array that is 24x4 because 4! is 24.<\/p>
n = 4;\r\nnp = factorial(n);\r\npts = perms(1:n)\r\n<\/pre>
\r\npts =\r\n\r\n     4     3     2     1\r\n     4     3     1     2\r\n     4     2     3     1\r\n     4     2     1     3\r\n     4     1     2     3\r\n     4     1     3     2\r\n     3     4     2     1\r\n     3     4     1     2\r\n     3     2     4     1\r\n     3     2     1     4\r\n     3     1     2     4\r\n     3     1     4     2\r\n     2     3     4     1\r\n     2     3     1     4\r\n     2     4     3     1\r\n     2     4     1     3\r\n     2     1     4     3\r\n     2     1     3     4\r\n     1     3     2     4\r\n     1     3     4     2\r\n     1     2     3     4\r\n     1     2     4     3\r\n     1     4     2     3\r\n     1     4     3     2\r\n\r\n<\/pre>
If we use each row as a point, we have 4 dimensions. This makes things a bit more abstract. Let's start by drawing the points and their connections as an undirected graph.<\/p>
nodelabels = cellstr(arrayfun(@(x)sprintf('%d'<\/span>,x),pts));\r\nedges = [];\r\nfor<\/span> i=1:np\r\n    for<\/span> j=(i+1):np\r\n        diff = pts(j,:) - pts(i,:);\r\n        if<\/span> isscalar(find(diff==-1)) && isscalar(find(diff==1)) && (n-2)==length(find(diff==0))\r\n            edges(end+1,:) = [i j];\r\n        end<\/span>\r\n    end<\/span>\r\nend<\/span>\r\ng = graph(edges(:,1),edges(:,2),[],nodelabels);\r\nplot(g)\r\n<\/pre>\"\" 
We can see that there appears to be a polyhedron hiding in there.<\/p>
What if we project this shape down into 3 dimensions? To do this, we'll need three 4D vectors which are normal to each other, and normal to the hyperplane. I happen to have a set right here.<\/p>
u = [sqrt(2)\/2, -sqrt(2)\/2, 0, 0];\r\nv = [sqrt(6)\/6, sqrt(6)\/6, -sqrt(2\/3), 0];\r\nw = [sqrt(12)\/12, sqrt(12)\/12, sqrt(12)\/12, -sqrt(3)\/2];\r\n<\/pre>
Now we can use the same technique I used to project that plane of hexagons down from 3D to 2D.<\/p>
x = sum(pts .* repmat(u,[np 1]),2);\r\ny = sum(pts .* repmat(v,[np 1]),2);\r\nz = sum(pts .* repmat(w,[np 1]),2);\r\nscatter3(x,y,z,'filled'<\/span>);\r\naxis equal<\/span>\r\n<\/pre>\"\" 
And then we can get the faces of the shape by using convhull.<\/p>
faces = convhull(x,y,z);\r\n\r\nhold on<\/span>\r\ntrisurf(faces,x,y,z,'FaceColor'<\/span>,cols(3,:),'EdgeColor'<\/span>,'none'<\/span>)\r\naxis vis3d<\/span>\r\ncamlight right<\/span>\r\n<\/pre>\"\" 
And we can recognize this as a truncated octahedron.<\/p>
And just as we saw in the 2D case, these octahedra will tile 3D space with no gaps.<\/p>
\"\" <\/p>
This tiling is known as the bitruncated cubic honeycomb<\/a>.<\/p>
And as I said, you can do this same thing in any dimension to generate a set of objects which tile the next dimension down. For example, if you do this with n=5, you'll get a 4D shape called the great prismatodecachoron<\/a>. This family of shapes go by the curious name of permutohedron<\/a>. Aren't they an interesting family?<\/p>