Taken from the Tessellation entry of Wikipedia on 9/20/2016:
No general rule has been found for determining if a given shape can
tile the plane or not, which means there are many unsolved problems
concerning tessellations. For example, the types of convex
pentagon that can tile the plane remains an unsolved problem.
You code a generate & test type algorithm that applied various rotations, flips & translation to attempt to find a tessellation for a given polygon, but a failure to find a tessellation for the polygon wouldn't necessarily guarantee that one didn't exist.
Depending on what your overall goal is, you might appreciate knowing that it is possible to start with a known tessellating shape & algorithmically generate a new tessellating shape.
Given your restriction of using only translations, you can brute force the problem as follows:
- Enumerate your vertices in some order.
- Test the result of moving each vertex to every other unchecked vertex.
- If the result does not overlap, label the move (see note 1) & save the result to a list called safe-moves.
- Examine all the combinations of entries (see note 2) from the safe-move as follows:
- If the current move overlaps any previous move, it can't tessellate, so try the next combination (see note #3).
- If none of the moves from the combination overlap, check to see if there is any unfilled space around the original shape.
- If there is no unfilled space, you have a legal tessellation!
- If there is empty space, try the next combination.
Notes:
- Label the moves as pairs 'alphabetically'; i.e. if you had a square labeled clockwise from the upper left corner, & moved vertex 1 to vertex 3 (translated the shape south), it would give the safe move called (1,3)(2,4). Thus, you wouldn't need to later try to move vertex 2 to vertex 4 since it is already recorded in this move. Also, you know the reverse mapping of 3 to 1 is safe & could also add it to the list now. If you add reverse safe mode as you go, then you only need to check mapping a given vertex to higher number vertices as mappings to lower number will already have been accounted for.
- If you have n # of vertices,I think you can you won't ever need a combination of more than 2n moves, but I haven't managed to prove that.
- For example if you start with this shape:
The move combination (2,5)(2,6) gives the following result which overlaps & must be rejected:
The legal move combination for that shape happens to be: (1,2)(5,4)(6,3), (1,4), (1,5)(2,4), (2,1)(3,6)(4,5), (2,5), (4,1), (4,2)(5,1), (5,2)