Comment remplir un contour avec des formes tangram prédéfinies?

Question

Je suis intéressé à utiliser des formes comme celles-ci:

Habituellement, un tangram est composé de 7 formes (5 triangles, 1 carré et 1 parallélogramme). Ce que je veux faire est de remplir une forme seulement avec des formes tangram, donc à ce stade, la taille et la répétition des formes ne devrait pas importer.

est ici quelque chose que j'ai essayé manuellement:

Je suis un peu perdu sur la façon d'aborder ce sujet.

En supposant que j'ai un chemin (une liste ordonnée/tableau de points du contour), J'imagine que je devrais essayer de faire une sorte de triangulation.

Existe-t-il une triangulation de Deulanay avec des triangles contraints à 45 degrés triangles rectangles?

Une approche plus « brute » serait d'ajouter un groupe de triangles (45 degrés) et utiliser SAT pour la détection de collision « réparer » les chevauchements, et nous espérons que les lacunes seront évitées.

Puisque le carré et le parallélogramme peuvent aussi être faits de triangles (45 degrés), j'imagine que serait une bonne solution géométrique propre, non?

Comment emballer des triangles (45 degrés) à l'intérieur d'une forme arbitraire?

Toutes les idées sont les bienvenues.

Answer 1

Quelques réflexions au hasard (peut-être qu'ils vous aider à trouver une meilleure solution) si vous utilisez uniquement les formats originaux des formes:

• comme vous le soulignez, toutes les formes du tangram peuvent être fait composé de par exemple le triangle jaune ou rose (d-g-c), essayez donc aussi une approche ascendante comme essayer d'abord de placer autant de triangles jaunes dans votre forme et ensuite les combiner en plus grandes formes si possible. Dans le pire des cas, vous obtiendrez un ensemble de ces plus petits triangles.

• une triangulation de type de non-polygones (tels que la demi-lune dans votre exemple) ne fonctionnera probablement pas très bien ...

• On dirait que vous avez besoin que les formes ne peuvent avoir quelques orientations discrètes. Pour trouver le meilleur ajustement de ces triangles dans la forme donnée, je proposerais la solution approximative suivante: dessiner une grille de triangles (c'est-à-dire une grille carrée avec des lignes diagonales) à travers la forme et prendre ces triangles qui sont entièrement contenus. Cela ne vous donnera probablement pas la couverture optimale, mais vous pouvez ensuite déplacer la grille d'un dixième de la taille de la grille horizontalement et verticalement et voir si vous trouvez quelque chose qui couvre une plus grande partie de la forme originale (ou vous pourrait aller par étapes de 1/2 puis 1/4 etc. de la taille de la grille d'origine dans l'esprit d'une recherche binaire).

Si vous permettez à une échelle arbitraire des formes vous pouvez approcher une forme (raisonnablement lisse?) Avec une précision arbitraire en ajoutant plus en plus petites formes. Par exemple. Si vous avez une image raster, vous pouvez, par exemple, choisissez la taille du triangle jaune de sorte que deux d'entre eux forment un pixel sur l'image et vous pouvez ensuite représenter n'importe quelle image raster.