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.