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