{"id":293,"date":"2015-09-04T09:41:45","date_gmt":"2015-09-04T13:41:45","guid":{"rendered":"https:\/\/blogs.mathworks.com\/graphics\/?p=293"},"modified":"2016-08-23T10:40:45","modified_gmt":"2016-08-23T14:40:45","slug":"tiling-quadrilaterals","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/graphics\/2015\/09\/04\/tiling-quadrilaterals\/","title":{"rendered":"Tiling Quadrilaterals"},"content":{"rendered":"

Tiling Quadrilaterals<\/h3>

Last time I was talking about the new pentagon tiling<\/a> which was recently discovered. There are lots of other wonderful things to explore in how polygons tile the plane. One of my favorites involves quadrilaterals. They're much easier to tile than pentagons are. That's because the sum of their internal angles is 360 degrees. In fact, quadrilaterals are so easy to tile that you can make a tiling from any quadrilateral at all! Let's take a look at how that works.<\/p>

First we'll need a random quadrilateral. That's a bit trickier than you might think. We obviously want to start with 4 random points, but what order do we connect the points in? With triangles it's simple, but with quadrilaterals we need to avoid orders that have self intersections like this one:<\/p>

rng default<\/span>\r\nx = randn(1,4);\r\ny = randn(1,4);\r\ncols = get(gca,'ColorOrder'<\/span>);\r\npatch('XData'<\/span>,x,'YData'<\/span>,y,'FaceColor'<\/span>,cols(1,:))\r\n<\/pre>\"\" 
We could use convhull, but that would leave out concave quads, and we're interested in them. We want to eliminate the self intersecting cases without eliminating the concave cases.<\/p>
It turns out that one of the simplest ways to create a random quadrilateral in MATLAB is to create a Delaunay triangulation from the random points, and then keep 2 of the triangles. This is actually a useful technique to know because it extends to larger polygons, as you can see here<\/a>.<\/p>
The implementation of that (minus some coincident point error checking) looks something like this:<\/p>
function<\/span> [x, y] = random_quad()\r\n  % Start with 4 random points<\/span>\r\n  x = randn(1,4);\r\n  y = randn(1,4);\r\n  % Triangulate them<\/span>\r\n  t = delaunayTriangulation(x',y');\r\n  % If we found 3 triangles, throw one away<\/span>\r\n  if<\/span> size(t,1) > 2\r\n    t = triangulation(t.ConnectivityList(1:2,:),x',y');\r\n  end<\/span>\r\n  % Return the points in the order of the boundary<\/span>\r\n  bound = freeBoundary(t);\r\n  bound = bound(:,1);\r\n  x = x(bound);\r\n  y = y(bound);\r\n<\/pre>
Let's draw a bunch of those and see if they look nice and random.<\/p>
cla\r\nfor<\/span> i=1:5\r\n    for<\/span> j=1:4\r\n        [x,y] = random_quad;\r\n        patch('XData'<\/span>,x+i*4,'YData'<\/span>,y+j*4,'FaceColor'<\/span>,rand(1,3))\r\n    end<\/span>\r\nend<\/span>\r\n<\/pre>\"\" 
Those look pretty good, so let's pick one and see how we can tile the plane with it.<\/p>
I found this one that I like the looks of, so we'll use it as for our example. But remember, this algorithm will work with any quadrilateral that doesn't self intersect.<\/p>
rng(1913)\r\n[x,y] = random_quad;\r\n\r\ncla\r\naxis equal<\/span>\r\npatch('XData'<\/span>,x,'YData'<\/span>,y,'FaceColor'<\/span>,cols(1,:))\r\n<\/pre>\"\" 
So how are we going to tile the plane with this? One thing we can see is that if we rotate a copy of it by 180 degrees around the center of one of the edges, then the two quads will line up nicely. We can use the same transform matrices we used last time<\/a>.<\/p>
% Points in the convenient form for transforming<\/span>\r\npts = [x; y; ones(1,4)];\r\n\r\n% Matrix which rotates by 180 degrees<\/span>\r\nrotmat = [-1  0 0; ...<\/span>\r\n           0 -1 0; ...<\/span>\r\n           0  0 1];\r\n\r\n% The center of the first edge<\/span>\r\nc = pts(:,1)\/2 + pts(:,2)\/2;\r\n\r\n% Rotate by 180, and translate into place<\/span>\r\noffset = rotmat*c - c;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\n\r\n% and draw<\/span>\r\npatch('XData'<\/span>,p2(1,:),'YData'<\/span>,p2(2,:),'FaceColor'<\/span>,cols(2,:))\r\ncm = line(c(1),c(2),'Color'<\/span>,'black'<\/span>,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,12);\r\n<\/pre>\"\" 
And we could do the same thing around the second edge:<\/p>
c = pts(:,2)\/2 + pts(:,3)\/2;\r\noffset = rotmat*c - c;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\npatch('XData'<\/span>,p2(1,:),'YData'<\/span>,p2(2,:),'FaceColor'<\/span>,cols(3,:))\r\ndelete(cm)\r\ncm = line(c(1),c(2),'Color'<\/span>,'black'<\/span>,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,12);\r\n<\/pre>\"\" 
... or the third edge:<\/p>
c = pts(:,3)\/2 + pts(:,4)\/2;\r\noffset = rotmat*c - c;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\npatch('XData'<\/span>,p2(1,:),'YData'<\/span>,p2(2,:),'FaceColor'<\/span>,cols(4,:))\r\ndelete(cm)\r\ncm = line(c(1),c(2),'Color'<\/span>,'black'<\/span>,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,12);\r\n<\/pre>\"\" 
... or the fourth edge:<\/p>
c = pts(:,4)\/2 + pts(:,1)\/2;\r\noffset = rotmat*c - c;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\npatch('XData'<\/span>,p2(1,:),'YData'<\/span>,p2(2,:),'FaceColor'<\/span>,cols(5,:))\r\ndelete(cm)\r\ncm = line(c(1),c(2),'Color'<\/span>,'black'<\/span>,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,12);\r\n<\/pre>\"\" 
We notice a few things looking at this picture.<\/p>
All four of those new copies are translations of each other, because they're all 180 degree rotations of the original.<\/p>
And there appear to be gaps between them that look like the original quad.<\/p>
In fact, if we do the same for any of the \"other\" three sides of each of those copies, we'll see that we get a translation of the original (because two rotations by 180 degrees cancel) which does tuck into one of the holes.<\/p>
% Rotate around the first side again<\/span>\r\nc1 = pts(:,1)\/2 + pts(:,2)\/2;\r\noffset = rotmat*c1 - c1;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\n\r\n% And then rotate that around the second side of the result.<\/span>\r\nc2 = p2(:,2)\/2 + p2(:,3)\/2;\r\noffset = rotmat*c2 - c2;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np3 = rotmat*xlatmat*p2;\r\n\r\ndelete(cm)\r\npatch('XData'<\/span>,p3(1,:),'YData'<\/span>,p3(2,:),'FaceColor'<\/span>,cols(6,:))\r\ncm = line([c1(1) c2(1)],[c1(2) c2(2)],'Color'<\/span>,'black'<\/span>,'LineStyle'<\/span>,'none'<\/span>,'Marker'<\/span>,'o'<\/span>,'MarkerSize'<\/span>,12);\r\n<\/pre>\"\" 
This means that fundamental region of this tiling consists of two copies of the original quadrilateral, one of which is rotated by 180 degrees, and which share one side. We can pick any two neighbors, but I'll pick the first two we drew.<\/p>
cla\r\naxis off<\/span>\r\nset(gca,'Position'<\/span>,[0 0 1 1])\r\nxdata = pts(1,:);\r\nydata = pts(2,:);\r\n\r\nc = [(pts(1:2,1) + pts(1:2,2))\/2; 1];\r\noffset = rotmat*c - c;\r\nxlatmat = [1 0 offset(1); ...<\/span>\r\n           0 1 offset(2); ...<\/span>\r\n           0 0         1];\r\np2 = rotmat*xlatmat*pts;\r\nxdata(2,:) = p2(1,:);\r\nydata(2,:) = p2(2,:);\r\n\r\ndark = [.75 .75 .75];\r\nlight = [.875 .875 .875];\r\npatch('XData'<\/span>,xdata','YData'<\/span>,ydata','FaceColor'<\/span>,dark)\r\n<\/pre>\"\" 
And we can use these two translation vectors ...<\/p>
uvec = pts(:,1) - pts(:,3);\r\nvvec = pts(:,2) - pts(:,4);\r\n<\/pre>
... to assemble copies of the fundamental region into a tiling.<\/p>
cla\r\npatch('XData'<\/span>,xdata'+uvec(1),'YData'<\/span>,ydata'+uvec(2),'FaceColor'<\/span>,light,'EdgeColor'<\/span>,dark)\r\npatch('XData'<\/span>,xdata'+vvec(1),'YData'<\/span>,ydata'+vvec(2),'FaceColor'<\/span>,light,'EdgeColor'<\/span>,dark)\r\npatch('XData'<\/span>,xdata','YData'<\/span>,ydata','FaceColor'<\/span>,light)\r\nline(pts(1,1) + [0 uvec(1)],pts(2,1) + [0 uvec(2)],'Color'<\/span>,cols(1,:),'LineWidth'<\/span>,2)\r\nline(pts(1,1) + [0 vvec(1)],pts(2,1) + [0 vvec(2)],'Color'<\/span>,cols(2,:),'LineWidth'<\/span>,2)\r\n<\/pre>\"\" 
And we can repeat as far as we'd like.<\/p>
cla\r\nfor<\/span> i=-7:7\r\n    for<\/span> j=-5:5\r\n        ci = mod(3*j+2*i,5);\r\n        h = patch('XData'<\/span>,xdata' + i*uvec(1) + j*vvec(1),'YData'<\/span>,ydata' + i*uvec(2) + j*vvec(2));\r\n        h.FaceVertexCData = cols(ci+(1:2),:);\r\n        h.FaceColor = 'flat'<\/span>;\r\n    end<\/span>\r\nend<\/span>\r\n<\/pre>\"\" 
And finally, let's zoom in for a closer look.<\/p>
ax = gca;\r\nax.Position = [0 0 1 1];\r\nset(ax.Children,'EdgeColor'<\/span>,'none'<\/span>)\r\nylim([-3.5 3.5])\r\n<\/pre>\"\" 
And here are a couple more which I created with different seeds for the random number generator.<\/p>
\"\" <\/p>
\"\" <\/p>
\"\" <\/p>
Aren't those fun? Wouldn't you like a set of tiles like that for your kitchen floor? They'd wake you up in the morning.<\/p>