Decomposable Families of Shapes

While the below might not perfectly match the criteria in your question, I think it should give you a decent insight in to the kinds of examples which are very closely related to the one you give as an example. There are simply too many examples to check to see which satisfy your stated conditions so I'll just give you a foothold on where to begin your search, as well as a slight exposition of aperiodic tilings. I apologise if this is too much of a tangent from your specific question.

The example you give is actually a generating substitution for (one of the representations of) the Penrose tiling - specifically the Robinson triangles prototile set - here is a very good video which outlines some of the methods that these tiles can be fit together to tile the plane (as well as the other representations of the Penrose tiling). The specific property you mention is related to the notion of a substitution tiling. The tiling associated to the particular substitution in your example looks something like this after a few dozen iterations.

You'll notice that the portion of the tiling shown here isn't periodic (and in fact it can be shown that there is no translation which maps the tiling of the plane to itself), and yet each local region can be found infinitely often through the plane, and within a bounded distance of each occurance. We call such a tiling aperiodic.

Substitution tilings (a sub-branch of the broader theory of aperiodic tilings) are very well studied and an extremely active area of research at the moment; bringing together areas of mathematics such as combinatorics, decidability theory (logic), dynamical systems, non-commutative geometry, mathematical physics, and my current focus - algebraic topology.

I'll answer your fourth question first as it's the easiest - Yes there are substitution tilings in higher dimensions, and even in non-Eucliden spaces such as hyperbolic space. A good place to start would be the work of Chaim Goodman-Strauss - especially for such wonderful images as 'dodecafoam'.

The next easiest is your third question - yes there are fractal substitution tilesets for the plane. In fact, you can cut out little fractal Koch snowflake-like tabs on one of the edges of any polygonal tileset and glue it on to the corresponding edge of the tile(s) that that edge can appear next to after substituting. In terms of pictures, there are also of course the famous Rauzy Fractals

although I don't think this quite satisfies your conditions (I could be wrong).

For some solid examples in the plane that you might like to start with, there's

• The chair tiling

• Goodman-Strauss' cubic PV tiles

• The Ammann Chair tiling

As well as the half-hex tiling, the sphinx tiling, the table tiling, the Ammann-Beenker tiling, the pinwheel tiling, and many more which you can find in the literature by searching in the areas of aperiodic tilings and substitution tilings.

Consider the following family of 4 similarity classes: squares, 1-by-2 rectangles, 1-by-3 rectangles, and 1-by-4 rectangles. Each polygon in the family can be decomposed into two polygons from the family in at least two different ways:

• squares can be decomposed to two 1-by-2 rectangles either horizontally or vertically.
• 1-by-2 rectangles can be decomposed to two squares vertically, or to two 1-by-4 rectangles horizontally.
• 1-by-3 rectangles can be decomposed vertically to a square and a 1-by-2 rectangle, or vice versa.
• 1-by-4 rectangles can be decomposed vertically to a square and a 1-by-3 rectangle, or vice versa, or two 1-by-2 rectangles.

This set can be extended arbitrarily by adding 1-by-N rectangles for every integer $N\geq 5$. This can also be extended to polyhedra in $R^3$, by making each rectangle a hypercuboid of size 1-by-1-by-N.

Another family, which I describe in the same way I built it (hopefully this will some day develop into an algorithm):

• Take a right-angled isosceles triangle (RAIT). Cut it using the perpendicular bisector to one of its shorter sides. The result is a smaller RAIT, and a right-angled quadrilateral (trapezoid). This can be done in two ways (one for each shorter-side).
• Take the trapezoid. Cut it to two RAITs of different sizes. Cut it in another way, to a square and a RAIT.
• Take the square. Cut it to two RAITs in two ways (one for each diagonal).

In conclusion, we have a family of 3 decomposable shapes: RAIT, trapezoid and square.

So, currently we have a family of 2 decomposable shapes (in the OP), a family of 3 (above) and families of 4 or more (above the above).