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.

[anapurna]

salut

la stategie est de trouver les points remarquables

donc les arrêtes ,changement de direction sur le contour de ta silhouette

ensuite tu trace de droite qui passe par ces point remarquable
un fois ces droites tracé tu efface toute celle qui se trouve a l’extérieur de la silhouette
il te reste donc plus que des segment de droite qui définisse divers forme au sein de cette silhouette
tu n'a plus qu'a comparer tes formes avec les les formes définis au sein de ton tracé

[pseudocode]

salut

la stategie est de trouver les points remarquables

donc les arrêtes ,changement de direction sur le contour de ta silhouette

ensuite tu trace de droite qui passe par ces point remarquable
un fois ces droites tracé tu efface toute celle qui se trouve a l’extérieur de la silhouette
il te reste donc plus que des segment de droite qui définisse divers forme au sein de cette silhouette
tu n'a plus qu'a comparer test formes avec les les forme définis au sein de ton tracé

C'est malheureusement pas si simple.
Exemple avec la figure de base du Tangram: le carré.



la silhouette est un grand carré => 4 points d'intérêts et 4 cotés.
Pas évident de faire un découpage interne qui amène à la solution.

(Resoudre un tangram est un problème NP-Hard).

[anapurna]

salut

pour ton exemple il existe plus d'une solution

il faut donc affiner notre première solution par une triangulation
ou la taille des triangles correspond à la taille du plus petit triangle mis à notre disposition

[Âne-ais]

Merci pour vos réponses, je vais faire comme énoncé par anapurna.
Mais petite question comment trouver les points colorés en rouges?

[tbc92]

Tu as les points jaunes. C'est l'étape 1.

- Les points rouges, tu peux les déterminer en prolongeant les 2 traits verticaux. Mais ce ne serait pas une bonne méthode. Ici, on sait qu'il faut effectivement prolonger les 2 traits verticaux, parce qu'on connaît par avance la solution, mais si nos 3 formes étaient 3 trapèzes au lieu de 2 triangles et un carré, alors l'emplacement des points rouges serait différent.

En fait, il faut probablement prendre les 3 formes connues, en commençant pas la plus grande (le grand triangle). Et il faut chercher à placer cette forme quelque part. Cette forme, elle a un côté qui est très long et qui est en diagonale ( à 45% par rapport aux 2 axes). Si on fait tourner cette pièce de 90°, la longueur en question reste en diagonale. Et dans notre forme noire, une diagonale aussi longue, elle est forcément sur la gauche du dessin. Du coup, on a placé notre grand triangle. Et on a notre 1er point rouge...
Et on continue, en essayant de placer le carré, ou le 2ème triangle, dans l'espace restant.

Ceci dit, parmi les points jaunes, on peut peut-être faire 2 groupes. Les angles entrants (les 4 qui forment l'enveloppe convexe), et les angles sortants (les 2 autres angles, qui délimitent la limite haute du carré). Peut-être que cette distinction peut aider dans la suite du traitement.

[Âne-ais]

Merci beaucoup pour votre aide, j'ai une autre question portant plutôt sur un aspect pratique de la réalisation du programme me conseilleriez vous de créer mes pièces de départ avec laquelle de ses méthodes (ou aucune):

Créer un tableau, exemple avec un carré noir

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
blanc,noir = 0,1
for x in range(5,29):
    ymax = round(min(29+(x-4),29+(28-x)))
    for y in range(29,ymax):
        tab[x,y] = noir

On l'affiche et cela donne ceci :








Ou commencer avec des formes créées comme cela :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
fill([0,60,30,0],[0,0,30,0],'r')
axis('equal')
axis(visible='off') # a revoir
plt.axis
show()

et donc obtenir un triangle plus lisse :






Merci beaucoup encore

[pseudocode]

L'angle saillant (=inférieur à 180°) d'une silhouette est nécessairement décomposable en un ou plusieurs angles saillants correspondant aux pièces.



=> le "sommet+bord adjacent" d'un angle saillant d'une silhouette correspond au "sommet+bord adjacent" d'une des pièces.
C'est un très bon point de départ pour décomposer un tangram.

[anapurna]

salut

Tu as les points jaunes. C'est l'étape 1.

- Les points rouges, tu peux les déterminer en prolongeant les 2 traits verticaux. Mais ce ne serait pas une bonne méthode. Ici, on sait qu'il faut effectivement prolonger les 2 traits verticaux, parce qu'on connaît par avance la solution, mais si nos 3 formes étaient 3 trapèzes au lieu de 2 triangles et un carré, alors l'emplacement des points rouges serait différent.

En fait, il faut probablement prendre les 3 formes connues, en commençant pas la plus grande (le grand triangle). Et il faut chercher à placer cette forme quelque part. Cette forme, elle a un côté qui est très long et qui est en diagonale ( à 45% par rapport aux 2 axes). Si on fait tourner cette pièce de 90°, la longueur en question reste en diagonale. Et dans notre forme noire, une diagonale aussi longue, elle est forcément sur la gauche du dessin. Du coup, on a placé notre grand triangle. Et on a notre 1er point rouge...
Et on continue, en essayant de placer le carré, ou le 2ème triangle, dans l'espace restant.

Ceci dit, parmi les points jaunes, on peut peut-être faire 2 groupes. Les angles entrants (les 4 qui forment l'enveloppe convexe), et les angles sortants (les 2 autres angles, qui délimitent la limite haute du carré). Peut-être que cette distinction peut aider dans la suite du traitement.

bin si c'est la bonne méthode du fait même qu'il doit faire une triangulation de chaque éléments
ensuite il faut effectivement commencer par prendre les plus grandes formes afin de les placer dans l'ordre
pour connaitre la plus grande il faut calculer l'air de chaque figure disponible.

nous savons que pour le tangram le plus petit triangle est composant de toutes les autres pieces donc
la triangulation nous permettra de determiner les position possible a realiser

[Âne-ais]

Merci pour vos réponses, donc si j'ai bien compris, je cherche à prolonger les arrêtes (ou traits des bords) puis je teste la plus grande pièce? Et du coup que me conseillez-vous pour réaliser mes pièces entre les deux techniques que j'ai énoncées plus bas?

Merci beaucoup