2
\$\begingroup\$

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

An example:

enter image description here

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Pikalek
    Sep 20, 2016 at 17:17

1 Answer 1

2
\$\begingroup\$

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.
  3. For example if you start with this shape:

enter image description here

The move combination (2,5)(2,6) gives the following result which overlaps & must be rejected:

enter image description here

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)

\$\endgroup\$
9
  • 1
    \$\begingroup\$ This refers to the general case, where arbitrary shapes can be rotated or maybe flipped. When there's only translation of polygons, the possibility space is far more constrained, and a special-case solution may be available. \$\endgroup\$
    – DMGregory
    Sep 20, 2016 at 15:43
  • \$\begingroup\$ That's true, I missed the translation only restriction. I'll edit & update if I can pin the problem down further using that constraint. \$\endgroup\$
    – Pikalek
    Sep 20, 2016 at 15:50
  • 2
    \$\begingroup\$ A sketch: the transformation of one shape to its tesselated copy will map one of the shape's vertices (somewhere) to the position of another vertex. From this we can infer the period parallelogram of the tiling, and check whether copies of the shape clipped & wrapped by this parallelogram will fill it completely without overlapping each other. So, worst case we check each O(n^2) possible mappings of the shape's vertices onto each other looking for one that defines a valid tiling. There may be optimisations that do better. \$\endgroup\$
    – DMGregory
    Sep 20, 2016 at 15:56
  • \$\begingroup\$ Thanks a lot, awesome answer - I'm just trying to get my head around it, quite hard in words. Could you elaborate on 'Test the result of moving each vertex to every other unchecked vertex.'? The test after this being if the shape is overlapping? \$\endgroup\$
    – dolyth
    Sep 20, 2016 at 17:01
  • 1
    \$\begingroup\$ Added an illustration to help clear things up - should have done that to begin with. \$\endgroup\$
    – Pikalek
    Sep 20, 2016 at 18:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .