Sorry if this is a repeat. It seems like something that should be well known, but I have never found a really good way to write computer code to solve this problem, despite having ad hoc solutions for specific cases I'm interested in.
An example of the general problem is this. Take these two linear transformations $f$ and $g$: $$(x, y) \xrightarrow{f} (-y, x-y)$$ $$(x, y) \xrightarrow{g} (8-y, 4+x-y)$$ with fixed points $(0,0)$ and $(4,4)$ respectively. Two points $(x_1, y_1)$ and $(x_2, y_2)$ are considered equivalent (thus in the same part of the tessellation) if you can get $(x_2, y_2)$ from $(x_1, y_1)$ by applying some combination of $f$ and $g$ in series.
These transformations are easily seen to be isomorphic to $120^{\circ}$ rotations, but map integers to integers (I have used this for embedding hexagonal grids in rectangular grids stored as 2D arrays).
The equivalence classes defined above partition the plane into squares and $45^{\circ}$-$135^{\circ}$ parallelograms. In fact, the square $0 \leq x \leq 4$, $0 \leq y \leq 4$ contains a representative point for each equivalence class (there's a redundant representative in the closed intervals; it can be removed for integers, but I'm not sure about real numbers).
The problem is given any $x$, $y$ find its equivalent point satisfying $0 \leq x \leq 4$, $0 \leq y \leq 4$.
I can solve this and similar problems by converting these to matrixes and observing for instance that by composing them in different combinations, I get pure translations such as $(x+8,y+4)$ or $(x+4,y+8)$. Given this, I can map values back into a range where they can be rotated into the square bounded by inequalities.
My question is what's the simplest algorithm that solves this in general? I have made some starts into mapping integer pairs into equivalence classes using graph search, but it just gets a lot more complicated than I would like.
Is there a simpler way to take a set of transformations like the above and derive a formula, e.g. using modular arithmetic and a few conditional checks that could solve the problem of placing a general point into its equivalence class?
Note that I am only interested in linear transformations, and I also realize that there are not all that many tessellations possible (e.g. I think it is limited to wallpaper groups with an additional scaling factor).
My question is just how to get from an arbitrary set of transformations to a more usable description of the tessellation such as could be used in software.