From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: help: tessellate pattern problem Date: 13 Oct 1997 20:17:49 GMT In article <343E0C60.573A@rapport.ltd.uk>, Rapport Ltd wrote: >take the following 2 rectangles (A and B, 5*5 and 3*3) and tile them >together thus: > > AAAAA > AAAAA > AAAAABBB > AAAAABBB > AAAAABBB > > >then repeat this pattern thus: > > AAAAA > AAAAA > AAAAABBBAAAAA > AAAAAAAAAABBBAAAAA > AAAAAAAAAABBBAAAAA > AAAAABBBAAAAAAAAAA > AAAAAAAAAABBBAAAAAAAAAA > AAAAAAAAAABBBAAAAABBB > AAAAABBBAAAAAAAAAABBB > AAAAABBBAAAAAAAAAABBB > AAAAABBBAAAAABBB > AAAAABBB > AAAAABBB > >this pattern can then be repeated to cover any given area (I hope I >have explained myself up to this point, the A cells tend to blur into >each other in these ASC pictures, it may be best to draw squares on >paper). > >My question is - given any point in space (X, Y) (integer values only), >what point within the pattern is it at, ie. which type of cell (A or B) >is it in and what are the offsets within that cell? More generally, you have a set X which consists of the square [0,m]x[0,m] in the plane, together with the square [m,m+n]x[0,n]. You cover the plane with copies of this, using the translations R(x,y)=(x+m,y+n) and S(x,y)=(x-n,y+m). Then your question is, given any point (x,y) in the plane, you want to write (x,y) = R^k S^l (a,b) for some (a,b) in X and some integers k and l. Notice that these two translations are perpendicular and move by a distance of r=sqrt(m^2+n^2). So why not just scale by 1/r and rotate so that R and S are unit motions along the axes? Then it's just a question of using the greatest-integer and fractional-part functions. In detail, given (x,y), compute (x', y'), where x' = cos(u)*(x/r) + sin(u)*(y/r) y' = -sin(u)*(x/r) + cos(u)*(y/r) and u is the angle whose tangent is n/m. You're scaling and rotating so that the "inner corner" of X is moved to the point (1,0). No trigonometry is needed here: cos(u) = m/sqrt(m^2+n^2), and sin(u) = n/sqrt(m^2+n^2); thus we have x' = (m*x + n*y)/(m^2+n^2) y' = (-n*x+ m*y)/(m^2+n^2). Then let x'' = frac(x') = x' - int(x'), the fractional part of x''; likewise set y'' = frac(y'). Then the point (a,b), where a = cos(u)*(x''*r) - sin(u)*(y''*r) = m*x'' - n*y'' b = sin(u)*(x''*r) + cos(u)*(y''*r) = n*x'' + m*y'' should be a point in X which is equivalent to (x,y). Well, OK, it might not be actually in X, but it will be in one of three neighbors of X; from there it's easy to make the final calculations. Example: as in your case take m=5, n=3, so r=sqrt(34). Suppose we want to know where the point (x,y)=(2, 134) lies. As above we find x' = 412/34, y' = 664/34 x''= 4/34, y''= 18/34 a = -1, b = 3 which is not in the fundamental set X, but with one application of the translation R we come to the point (4,6), and one application of S^(-1) takes us to (7,1). This now is in the fundamental domain X, so it's the point we wanted. Of course it's a "B" point, so (2, 134) is, too. Observe that, as in this example, if m, n, x, and y are all integers, the whole computation can be done with integer arithmetic. Also note that this procedure is completely general: if your figure X may be used to tile the plane using translations R and S, then use a linear transformation under which R and S are the unit coordinate translations. In the new coordinates, compute fractional parts, then translate back. A minor adjustment may be needed at the end to move from the final point to a point in X. dave