Discussion :

[zikri]

Bonjour futur(e) sauveur ,
je suis un étudiant et je dois faire un projet en langage C. Ceci doit, donner en sortie, les triangulations d'un polygone convexe. Par exemple, si, en entrée, on donne un hexagone ABCDEF , le programme doit renvoyer toutes les triangulations comme suit:
AC AD AE , BD BE BF, CE CF CA, DF DA DB, EA EB EC, FB FC FD.

la solution , la plus simple selon moi, serait de relier tous les sommets qui ne sont pas adjacents.

J'ai fait ce bout de programme. l'idée principale est de prendre le mot et le concaténer à lui même par ex, ABCDEFABCDEF. Ensuite de copier tout dans un tableau en entier par le code ASCII pour les manier.

Résultat:

il marche jusqu'à l'avant-dernier caractère du mot initial. Je crois qu'il y a un problème d'allocation de mémoire vu que je passe de char en int.

Merci de me corriger.

Au plaisir de lire vos commentaires.

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include<string.h>
#include<stdlib.h>
 
int main()
{
char mot[50]; // un tableau d'au plus 50 caractères.
char mot2[25];
int L;
int tab[2*L];
 
printf("Donner un mot\n");
scanf("%s",mot);
 
L=strlen(mot);
 
strcpy(mot2,mot); // dupliquer le mot et concaténer les deux copies 
strcat(mot,mot2);
 
printf("%s\n",mot);
 
 
for (int i=0;i<=2*L-1;i++){  // l'idée d'utilisation du tableau en entier avec les codes ASCII des caractères est la facilité de manipuler 
	tab [i]= mot[i];         //ce type de tableau par rapport à celui de caractères.
}
 
for (int i=0;i<=2*L-1;i++){ // pour juste voir si le tableau en entier contient les codes ASCII de caractères
   printf("%d\t",tab [i]); 
}
 
 
for (int i=0;i<=L-1;i++){
int N=i+2;  // la première itération commence à deux rangs plus loin que le nombre pointé par i.
int M= L-2+i;  // la dernière dépend de la longueur du mot donné et de la valeur de i.
for(int j=N; j<=M;j++){
printf ("\n");
printf ("%c", tab [i]); // forcer le tableau à afficher le résultat en caractères.
printf ("%c", tab[j]);
printf ("\n");
      }
}
 
    return 0;
}

[Obsidian]

Bonjour et bienvenue,

Pourrais-tu nous préciser ce que l'on entend ici par « triangulations » ? Parce que l'exemple que tu nous donnes semble ne correspondre à rien. S'il s'agit de partitionner un polygone quelconque vers un ensemble de triangles, alors tu peux très bien considérer deux, voire trois sommets adjacents. Par exemple : A→B→C→A. Tu tracerais alors une corde à l'intérieur de ton polygone pour en découper un morceau, comme dans un morceau de fromage.

En outre, « AC AD AE », ne forment pas un triangle mais, à la place, trois segments de droite disposés en étoile et se rencontrant au point A.

[zikri]

Bonjour,
Les segments AC AC AD partagent l'hexagone en des triangles d'où le terme "triangulation".
Donc, pour être plus clair, il me faut écrire un programme qui, pour chaque polygone donné, est capable de déterminer TOUS les segments qui subdivisent le polygone en des triangles.

Merci☺️☺️

[Obsidian]

Bonjour,
Les segments AC AC AD partagent l'hexagone en des triangles d'où le terme "triangulation".

Justement pas : « AC AD AE » ne forment pas un triangle : ils forment une étoile à trois branches. Si tu pars du même sommet (« A ») et que tu rayonnes vers trois autres sommets de façon indépendante, tu ne forme pas un polygone fermé.

Donc, pour être plus clair, il me faut écrire un programme qui, pour chaque polygone donné, est capable de déterminer TOUS les segments qui subdivisent le polygone en des triangles.

D'accord mais plus précisément, faut-il déterminer tous les triangles qui puissent être tracés à partir de trois sommets quelconques, auquel cas c'est relativement facile (problème d'arrangements et de combinaisons, en mathématiques) ou faut-il « partitionner » ton polygone, c'est-à-dire le découper en une somme de sous-triangles qui ne se chevauchent jamais mais qui, une fois tous réunis, reconstituent le polygone originale ?

Tu as bien précisé par ailleurs que le polygone est convexe, donc il n'y a pas à se soucier de savoir si un tracé entre deux sommets sort ou non du périmètre.

[zikri]

Grâce aux segments AC,AD et AE, l'hexagone ABCDEF est subdivisé en plusieurs triangles: ABC, ACD,ADE et AEF.
Dans l'exemple précédent, on est parti du sommet A, il faut faire la même chose pour tous les autres sommets du polygone.
Mon programme marche, mais je pense que l'erreur s'est glissé quand j'ai concatené les deux chaînes de caractères.
Merci😀😀😀

[Obsidian]

Donc, on se dirige bien vers une partition de ton polygone.

Pour en être complètement sûr, as-tu le droit de croiser les segments tirés entre deux sommets initiaux, comme ceci ?

Ici, les segments sont FB, FC, BD et CE. Dans cette figure, ton hexagone est bien découpé en une somme de triangles, et rien d'autre, qui réunis reforment bien ta figure initiale, mais le sommet central n'appartient pas au polygone original.

[zikri]

Oui, il est bien question de partitionner le polygone et on n'a pas le droit de croiser les segments.
Pour un sommet donné, on doit déterminer tous les segments qui émanent de lui et qui partitionnent le polygone. Et on procède de la même manière pour chaque sommet du polygone.

[Obsidian]

Oui, il est bien question de partitionner le polygone et on n'a pas le droit de croiser les segments. Pour un sommet donné, on doit déterminer tous les segments qui émanent de lui et qui partitionnent le polygone. Et on procède de la même manière pour chaque sommet du polygone.

Oui mais, malheureusement, cela ne suffira pas : si tu ne fais que rayonner depuis un sommet donné en traçant tous les segments qui ne sont pas confondus avec les côtés du polygone (donc ceux vers ses voisins immédiats), tu vas manquer un certain nombre de combinaisons, comme celles qui forment une frontière en N dans un hexagone. Dans la figure ci-dessus, si tu enlèves BE ou CF, ton hexagone est toujours partitionné en triangles mais quelque soit le sommet choisi, il y aura toujours au moins un segment qui ne l'atteindra pas.

À la place, il faut (à mon avis) adopter une approche récursive style BSP simplifié : pour chaque sommet de ta figure, tu divises celle-ci en un triangle + le reste du polygone et tu rappelles récursivement ta routine avec ce « reste ». La condition d'arrêt étant le fait d'appeler la routine avec un ensemble de trois sommets (ou moins, mais cela ne doit jamais arriver), auquel cas il n'y a qu'une seule combinaison possible. Et pour « couper un coin » de ta figure qui ait forcément la forme d'un triangle à partir d'un sommet donné, tu n'as pas le choix : il faut impliquer ses deux voisins immédiats (qui eux restent dans la course). Du coup, le principe est simple : pour chaque sommet de ta figure, tu rappelles ta routine avec un ensemble PRIVÉ du sommet en question.

Et normalement, ça marche tout seul. Par contre, tu vas avoir des doublons.

[zikri]

Bonjour,
L'idée de la récursivité n'est pas mal, je vais essayer de m'y mettre dessus.
Cependant, vous dites "Du coup, le principe est simple : pour chaque sommet de ta figure, tu rappelles ta routine avec un ensemble PRIVÉ du sommet en question." Mais chaque sommet doit être sollicité (n-3) fois pour un polygone de n sommets.
Donc pourquoi appeler une fonction récursive qui exclurait le sommet au premier appel.

Merci de m'éclaircir ce point.

[Obsidian]

Donc pourquoi appeler une fonction récursive qui exclurait le sommet au premier appel.
Merci de m'éclaircir ce point.

Pas au premier appel mais à chaque appel.

L'idée est de partir d'un polygone ABCDEF (dans le cas de l'hexagone) et de traiter ses sommets un par un, en commençant par « A », donc. Si l'on veut tracer un triangle à partir de A et qui partitionne le polygone en seulement deux parties (le triangle + le reste), on est obligé de le tracer en A, B et F. « A » fait partie du triangle, mais BF forme une frontière commune entre le triangle et le polygone restant, donc ici un pentagone. Donc seul « A » se retrouve exclu de ce polygone restant, et on ré-entre dans la procédure avec BCDEF.

[zikri]

Bonjour, je comprends votre logique mais pourquoi exclure le sommet A, il faut plutôt enlever le sommet B comme la figure ci-dessous et le programme doit donner,
en sortie, les segments AC, AD et AE. On reprend pour le sommet B et on procède de la même manière avec BD BE BF en sortie.
Je vais me pencher sur la récursivité et vous aurez de mes nouvelles très bientôt

[Obsidian]

Bonjour, je comprends votre logique mais pourquoi exclure le sommet A, il faut plutôt enlever le sommet B comme la figure ci-dessous et le programme doit donner,
en sortie, les segments AC, AD et AE.

En regardant bien la figure, on s'aperçoit que l'on a ôté successivement le sommet B, puis le C, puis D. Quitte à ôter des sommets, autant commencer par le A (ce qui résulterait en une coupée tracée entre F et B).

Mais surtout, il faut en fait traiter toutes les possibilités, c'est-à-dire, pour l'hexagone original, appeler six fois la routine en le privant à chaque fois d'un sommet à tour de rôle, soit « tous les sommets sauf A » (donc BCDEF), puis « tous les sommets sauf B » (donc ACDEF), puis « tous les sommets sauf C » (donc ABDEF) et ainsi de suite. Et comme tu appelles ta routine récursivement (et pas itérativement), pour chacun de ces six sommets traités, le « sous-pentagone » qui en résulte subit le même traitement en ré-entrant cinq fois dans la routine en le privant à chaque fois de l'un de ses cinq sommets.

[Obsidian]

Bien, comme le sujet m'intéressait aussi, je me suis collé à la tâche et j'ai fini par écrire mon propre programme, qui génère un fichier SVG décrivant toutes les combinaisons possibles. Je les mets en pièce jointe. Ils peuvent en principe être directement imprimés (au moins sur du format A4).

L'algo que l'on a décrit est en quelque sorte « ultra-exhaustif » dans le sens où il va te donner beaucoup de pseudo-doublons : par exemple, si on veut partitionner un carré, il n'y a que deux possibilités : tracer l'une ou l'autre des diagonales. Et si on élimine les figures mathématiquement semblables, alors il n'y en plus qu'une : si l'on prend la première combinaison et qu'on la fait pivoter de 90°, elle devient exactement identique à l'autre.

Mais l'algorithme, lui, va tenter d'ôter successivement les quatre sommets et, donc, générera quatre combinaisons, soit deux fois deux combinaisons identiques. C'est important si les sommets ont une signification.

Voici donc, ci-joint, les fichiers pour le carré, le pentagone, l'hexagone et l'heptagone. Attention également aux explosions combinatoires :

Carré (4 côtés) : 4 combinaisons
Pentagone (5 côtés) : 20 combinaisons
Hexagone (6 côtés) : 120 combinaisons
Heptagone (7 côtés) : 841 combinaisons
Nonagone (9 côtés) : 60481 combinaisons !

Au delà, ça devient vraiment trop long à calculer même si je peux très bien lui demander de partitionner un polygone à 26 côtés.

Donc, dans le cas de l'hexagone, l'algorithme trouve 120 combinaisons mais il n'y en a en fait que 4 semblables entre elles.

[zikri]

Bonjour ,

Grâce à votre suggestion sur la récursivité, j'ai finalement écrit un programme avec celle-ci qui MARCHE

Merci pour tout.

[Obsidian]

Super, mais n'oublie pas le bouton en bas de page.