Discussion :

[Âne-ais]

Bonjour, j'ai commencé depuis peu à programmer sur python et je dois faire un programme de plusieurs centaines de lignes sur ce thème :

J'ai trois pièces, un carré, un petit triangle et gros triangle dont on connait les dimensions. Et j'ai une image noire formée de ces éléments et à l'aide d'un programme je dois retrouver les emplacements des 3 pièces comme montré ci-dessous. Python doit montrer l'image en couleur à la fin



Je peux tourner les pièces uniquement de 90°

Comme on connait les dimensions des pièces je les ai créées sous forme de tableau. Je pensais utiliser des tableaux, mais je ne sais pas quelle stratégie adoptée. Il faut que le programme soit efficace. Je pensais utiliser les angles ou les contours de la forme noir pour déterminer ou est chaque pièce, mais je n'y arrive pas.

Je vous remercie par avance.

[pseudocode]

Bonjour,

Le problème posé s'appelle résoudre un tangram. Vous trouverez plein d'informations sur le web, y compris des algorithmes et du code (i.e. "tangram solver" en anglais).

Généralement, il y a deux types d'approche:
* partir des pièces et essayer tous les assemblages possibles jusqu'à trouver la silhouette.
* partir de la silhouette et essayer tous les découpages possibles jusqu'à trouver les pièces.

Vos contraintes étant très restrictives (3 pièces dont une grande, rotation à 90° uniquement), je suggère la première approche.

[tbc92]

Ici on a 2 problèmes consécutifs ;
- 1er problème : (P1) à partir d'une image en format PNG ou assimilé, et sachant que la forme noire est de type polygone, trouver rapidement les n sommets de ce polygone.
- 2ème problème (P2) : connaissant un polygone, et connaissant les 3 formes constituantes de ce polygone, résoudre le problème du Tangram.
Pour chacun de ces 2 problèmes, il doit y avoir des solutions connues. (je ne les connais pas).

En temps de traitement, le 1er problème me paraît BEAUCOUP plus coûteux que le 2ème.
Et ici le 1er problème doit certainement pouvoir être simplifié par le fait qu'on connaît les 3 formes triangle-triangle-carré. Idéalement, il faudrait donc résoudre les 2 problèmes en même temps. (problème P3)

Quel est ton objectif : résoudre les problèmes P1 et P2 successivement, ou résoudre le problème P3 ?

[Âne-ais]

Bonsoir, merci beaucoup pour vos réponses et votre aide.

Mon objectif est de résoudre le problème de manière la moins coûteuse possible. Je pense que votre problème P3 serait celui qui répond le mieux à cet objectif.

Il est précisé à la fin de mon sujet qu'il est mieux de trouver une approche qui fonctionnerait aussi pour une forme plus complexe. Je pense que cette phrase a été ajoutée pour éviter que nous fassions la première méthode proposée par pseudocode (je vous remercie au passage) qui est : "partir des pièces et essayer tous les assemblages possibles jusqu'à trouver la silhouette".

Je trouve bien le fait de partir de la silhouette mais je ne vois pas comment faire.

[pseudocode]

Je trouve bien le fait de partir de la silhouette mais je ne vois pas comment faire.

Le procédé s'appelle la dissection géométrique et tu trouveras tout un tas de littérature sur le web, y compris des applications sur les tangram (i.e. "Geometric Dissection Puzzles").

L'idée c'est de découper la forme en petits éléments: soit par "tiling" (=maillage régulier), soit par triangulation (des coups de ciseaux).
Une fois le découpage effectué, on tente de reconstituer la forme d'une pièce en sélectionnant certains petits éléments.

[Âne-ais]

Merci beaucoup pour cette information, j'ai trouvé de nombreuses choses mais je n'ai pas trouvé de renseignement sur la démarche/stratégie à adopter pour résoudre mon problème.