How can I fill an outline with predefined tangram shapes ?

Question

I am interested in using shapes like these:

Usually a tangram is made of 7 shapes(5 triangles, 1 square and 1 parallelogram).

What I want to do is fill a shape only with tangram shapes, so at this point, the size and repetition of shapes shouldn't matter.

Here's something I manually tried:

I am a bit lost on how to approach this.

Assuming I have a path (an ordered list/array of points of the outline), I imagine I should try to do some sort of triangulation.

Is there such a thing as Deulanay triangulation with triangles constrained to 45 degrees right angled triangles ?

A more 'brute' approach would be to add a bunch of triangles(45 degrees) and use SAT for collision detection to 'fix' overlaps, and hopefully gaps will be avoided.

Since the square and parallelogram can be made of triangles(45 degrees) too, I imagine there would be a nice clean geometric solution, right ?

How do I pack triangles(45 degrees) inside an arbitrary shape ?

Any ideas are welcome.

Answer 1

A few random thoughts (maybe they help you find a better solution) if you're using only the original sizes of the shapes:

• as you point out, all shapes in the tangram can be made composed of e.g. the yellow or pink triangle (d-g-c), so try also thinking of a bottom-up approach such as first trying to place as many yellow triangles into your shape and then combine them into larger shapes if possible. In the worst case, you'll end up with a set of these smallest triangles.

• any kind triangulation of non-polygons (such as the half-moon in your example) probably does not work very well...

• It looks like you require that the shapes can only have a few discrete orientations. To find the best fit of these triangles into the given shape, I'd propose the following approximate solution: draw a grid of triangles (i.e. a square grid with diagonal lines) across the shape and take those triangles which are fully contained. This most likely will not give you the optimal coverage but then you could repeatedly shift the grid by a tenth of the grid size in horizontal and vertical direction and see whether you'll find something which covers a larger fraction of the original shape (or you could go in steps of 1/2 then 1/4 etc. of the original grid size in the spirit of a binary search).

If you allow any arbitrary scaling of the shapes you could approximate any (reasonably smooth ?) shape to arbitrary precision by adding smaller and smaller shapes. E.g. if you have a raster image, you can e.g. choose the size of the yellow triangle such that two of them make a pixel on the image and then you can represent any such raster image.