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  <rapport@rapport.ltd.uk> 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