# Checking if shapes will tessellate

I'm trying to figure out where to start with getting code together to check if a shape tessellates.

An example:

Consider that the shapes cannot be rotated, just as-is. A 'compound' shape (as seen in the pic - second and third shapes) will have a series of co-ordinates that make them up.

Where could I begin to getting the computer to figure out if they can tessellate?

I'm using c# & unity. Thanks in advance.

• If you don't get anything efficient enough here after a week or so, you might try the math SE with the tessellation tag or CS SE with the computation geometry tag. Sep 20, 2016 at 17:17

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:

1. 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.
2. 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.