Discussion :

[MOH BEN]

Bonjour tout le monde . svp , j'ai une question :
C'est quoi la difference entre un polygone aplati et un polygone non aplati ( il y a une indication dans mon exo qui dit que un polygone non aplati s’il n’existe pas parmi ses arêtes deux qui sont identiques) mais j'ai pas comprit c'est quoi ca veut dire . Vous pouvez m'expliquer avec des exemples . Et merci beaucoup

[Flodelarab]

Bonjour



ABCD est un quadrilatère non aplati.
A'BCD est un quadrilatère aplati.
Selon vos définitions.

[wiwaxia]

Bonjour,

Bonjour tout le monde . svp , j'ai une question :
C'est quoi la différence entre un polygone aplati et un polygone non aplati ( il y a une indication dans mon exo qui dit que un polygone non aplati s’il n’existe pas parmi ses arêtes deux qui sont identiques) mais j'ai pas compris c'est quoi ça veut dire . Vous pouvez m'expliquer avec des exemples . Et merci beaucoup

N'y aurait-il pas au départ un problème de traduction ? Le texte d'origine est-il rédigé en anglais ?
Le mieux serait de citer les passages auxquels tu te réfères.

[MOH BEN]

Merci beaucoup beaucoup beaucoup .

N'y aurait-il pas au départ un problème de traduction ? Le texte d'origine est-il rédigé en anglais ?
Le mieux serait de citer les passages auxquels tu te réfères.

Voici le texte d'origine :
Soit un polygone non aplati dont les coordonnées de ses sommées sont toutes entières et toutes ses arêtes sont horizontales ou verticales.
Le polygone sur plan est défini par un point initial et une trajectoire (chaine de caractères) constituée d’une suite des quatre caractères suivants : − g : avancer d’une unité à gauche − d : avancer d’une unité à droite − h : avancer d’une unité vers le haut − b : avancer d’une unité vers le bas .
1. Ecrire une fonction estApplati qui détermine si un polygone est non aplati. Un polygone est non aplati, s’il n’existe pas parmi ses arêtes deux qui sont identiques.

[wiwaxia]

... Soit un polygone non aplati dont les coordonnées de ses sommées sont toutes entières et toutes ses arêtes sont horizontales ou verticales.
Le polygone sur plan est défini par un point initial et une trajectoire (chaine de caractères) constituée d’une suite des quatre caractères suivants : − g : avancer d’une unité à gauche − d : avancer d’une unité à droite − h : avancer d’une unité vers le haut − b : avancer d’une unité vers le bas .
1. Ecrire une fonction estApplati qui détermine si un polygone est non aplati. Un polygone est non aplati, s’il n’existe pas parmi ses arêtes deux qui sont identiques.

C'est quand même plus clair !
Le polygone étudié est une ligne brisée fermée ne comportant que des angles droits (ou plats).

Le parcours ainsi défini revenant à son point de départ, on dénombre sur un tour des nombres égaux de déplacements en sens opposés; d'oùpar conséquent:

Ng = Nd (pour les déplacements horizontaux) et Nh = Nb (pout des déplacements verticaux) .

Comme seuls comptent pour le repérage des sommets les changements de direction à angle droit, toute arête correspond à une séquence de symboles identiques; ainsi

# <xhhhy> (avec h ≠ x et y) représente une arête verticale (ascendante) de longueur 3 ,
# <xdy> (avec d ≠ x et y) représente une arête horizontale (orientée vers la droite) de longueur 1 .

Il va donc falloir repérer et mesurer toutes les séquences présentes, afin que la vérification soit possible.

MatLab présente sans doute des outils spécifiques pour le maniement des chaînes de caractères.

Exemple:le parcours fermé (ABCDEFA) est décrit par la chaîne:

'bddbbbdddddhhhhggggggg'.

On a ici: Nb = Nh = 4 , Nd = Ng = 7 ; il s'agit des dimensions du rectangle circonscrit au polygone.

Il suffit, après avoir établi un histogramme des distances de largeur totale Dmax = Max(Nh, Nd), de s'assurer que chacune des valeurs ne dépasse pas l'unité.

[Flodelarab]

On recopie la première lettre à la fin. Et le triangle est aplati si on trouve l'une des séquence suivante :

• BH
• HB
• DG
• GD

Un simple filtre avec une expression régulière fait le job.

Code :

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

1
2
3
4
5
6
7
8
$ awk -F '' '{OFS=FS;$(NF+1)=$1;} /hb|bh|dg|gd/{print "Polygone aplati";exit;} {for (i=1;i<NF;i++) tab[$i]++; if ((tab["b"]!=tab["h"])||(tab["d"]!=tab["g"])) print "Polygone non fermé"; else print "Polygone valide";}' <<< "bddbbbdddddhhhhggggggg"
Polygone valide
$ awk -F '' '{OFS=FS;$(NF+1)=$1;} /hb|bh|dg|gd/{print "Polygone aplati";exit;} {for (i=1;i<NF;i++) tab[$i]++; if ((tab["b"]!=tab["h"])||(tab["d"]!=tab["g"])) print "Polygone non fermé"; else print "Polygone valide";}' <<< "bddbbbdddddhhhhgggggggd"
Polygone aplati
$ awk -F '' '{OFS=FS;$(NF+1)=$1;} /hb|bh|dg|gd/{print "Polygone aplati";exit;} {for (i=1;i<NF;i++) tab[$i]++; if ((tab["b"]!=tab["h"])||(tab["d"]!=tab["g"])) print "Polygone non fermé"; else print "Polygone valide";}' <<< "bddbbbdddddhhhhgggggggh"
Polygone aplati
$ awk -F '' '{OFS=FS;$(NF+1)=$1;} /hb|bh|dg|gd/{print "Polygone aplati";exit;} {for (i=1;i<NF;i++) tab[$i]++; if ((tab["b"]!=tab["h"])||(tab["d"]!=tab["g"])) print "Polygone non fermé"; else print "Polygone valide";}' <<< "bddbbbdddddhhhhgggggggb"
Polygone non fermé

[wiwaxia]

Il y a eu dès le départ confusion entre deux propriétés différentes, que l'on demande de vérifier par une démarche appropriée:

... il y a une indication dans mon exo qui dit que un polygone non aplati s’il n’existe pas parmi ses arêtes deux qui sont identiques ...

... d'où les deux séries de réponses que la demande a suscitées.

La remarque précédente est juste, mais la réponse n'est peut pas très évidente pour un débutant.

Partons de l'exemple suivant:

DDDDDDDDDGGGBBBBBBBHHDDDDGGGGHHHHHGGGGGG

il contient une séquence symétrique: DDDDDDDDDGGGBBBBBBBHHDDDDGGGGHHHHHGGGGGG
que l'on peut progressivement supprimer, ce qui donne: DDDDDDDDDGGGBBBBBBBHHHHHHHGGGGGG ;
là encore une autre séquence: DDDDDDDDDGGGBBBBBBBHHHHHHHGGGGGG
que l'on peut supprimer a son tour, ce qui conduit à: DDDDDDDDDGGGGGGGGG ,
troisième séquence symétrique qui disparaît entièrement.

Il ne reste plus rien: on a bien affaire au départ, comme dans tous les cas intermédiaires, à un polygone "aplati".

[Flodelarab]

D'abord, je ne sais pas trop de quel droit tu simplifies. J'avais un prof de math qui t'aurait répondu "je vais simplifier ta note par 2".

Ensuite, à la réflexion, la recherche de polygone aplati est beaucoup plus compliquée que nos propositions. Et peut même devenir casse-pieds. 3 exemples :

• bdhgbdhg
• hgbddbghggbdhd
• dddbgbgbgbdddhghghgh

D'après la définition, ils sont aplatis. Et nulle simplification n'est envisageable.

[anapurna]

salut


la symétrie sur un même axe a un point pivot donnée ne devrais pas être possible par construction

ton exemple DDDDDGGGG est impossible au pire tu peut avoir DDDDDHGGGG ou DDDDDBGGGG
la même chose sur l'autre axe.
Tu as forcément un déplacement sur l'autre axe entre les deux

ceci dit ... j'aurais remplacé les lettre par une valeur (par exemple G= 3 et D=-3 H=1 et B=-1 )
si la somme des divers déplacement = 0 ont a donc un polygone fermé

en approfondissant le résonnement il faut que la somme des 3 et des -3 soit égale a zéro (ce qui veut dire aussi que le nombre de déplacement,
est identique dans les deux sens)
ce qui par conséquence, si les deux conditions sont respectées nous donnera donc
la somme des 1 et des -1 égale a zéro

les angles possible sont effectivement :

BD ou DB
HD ou DH
HG ou GH
BH ou HB

en remplacent les éléments la somme des éléments sélectionné devrais elles aussi être égale a zéro

[Flodelarab]

par exemple G= 3 et D=-3 H=1 et B=-1

Étrange modèle. 3 "bas" égalent 1 "droite". 3 "haut" égalent 1 "gauche".

ont a donc un polygone fermé

On n'a pas de problème pour fermer le polygone. On a un problème pour reconnaître les polygones aplatis.

ton exemple DDDDDGGGG est impossible

g: avancer d’une unité à gauche

On n'avance que d'une seule unité ! C'est cette arête-là qui ne doit pas être reproduite.

Sans faire la liste explicite des arêtes unitaires (indépendamment du sens de parcours), je ne vois pas de solution simple.

[anapurna]

salut

tu ne peut pas par construction avoir DDDGGG si non cela veut simplement dire que tu revient sur tes pas
et donc que tu as deux ligne confondu
au même titre que tu ne peut pas avoir HHHBBB
et pour faire encore plus simple DG et HB ne sont pas autorisé

par exemple G= 3 et D=-3 H=1 et B=-1

Étrange modèle. 3 "bas" égalent 1 "droite". 3 "haut" égalent 1 "gauche".

la traduction de se que je dis me parait un peu tronqué
je remplace les HBDG par des valeurs numérique signées
je prend 1 et 3 afin de différentier les déplacement horizontaux des verticaux
la sommation de tout les éléments devraient arriver a 0

reprenons l'exemple du début

b d d b b b d d d d d h h h h g g g g g g g
-1 -3 -3 -1 -1 -1 -3 -3 -3 -3 -3 1 1 1 1 3 3 3 3 3 3 3

ce qui donne comme déplacement selon un axe
(-3-3)+(-3 -3 -3 -3 -3) +(3 3 3 3 3 3 3) = 0
et selon l'autre axe
-1+(-1 -1 -1)+(1 1 1 1) = 0
ce qui vérifie
-1 -3 -3 -1 -1 -1 -3 -3 -3 -3 -3 1 1 1 1 3 3 3 3 3 3 3 = 0

pour les cassures
(-1 -3) ,(-3 -1) , (-1 -3) ,(-3 1) ,(1 3)
je cherche encore ce que l'on peut faire avec
sauf a dire que les cassures sont autoriser
celles qui ne le sont pas autoriser :
(-3 3) (3 -3) et (-1 1) et (1 -1)

mes deux cents

[wiwaxia]

... Ensuite, à la réflexion, la recherche de polygone aplati est beaucoup plus compliquée que nos propositions. Et peut même devenir casse-pieds. 3 exemples :

• bdhgbdhg
• hgbddbghggbdhd
• dddbgbgbgbdddhghghgh

D'après la définition, ils sont aplatis. Et nulle simplification n'est envisageable.

Un polygone aplati est confinable dans un domaine d'aire nulle; ce n'est pas le cas de ceux que tu proposes, qui présentent une aire algébrique différente de l'aire de la surface couverte (en valeur absolue):
# pour le premier: A₁ = 2*1 = 2 ; A_c = 1 ;
# pour le second: A₂ = 1 - 1 + 1 = 1 ; A_c = 3 ;

# pour le troisième: A₂ = -4 + 4 = 0 ; A_c = 8 .

(B) et (H) ne se côtoient jamais, de même que (D) et (G): il n'y a donc aucune simplification.

[wiwaxia]

D'abord, je ne sais pas trop de quel droit tu simplifies. J'avais un prof de math qui t'aurait répondu "je vais simplifier ta note par 2". ...

Tout couple (DG) ou (HB), correspondant à un simple aller-retour, peut être supprimé puisque l'aire de la surface enlacée est nulle.

Je n'ai fait qu'accélérer ta méthode, avec peut-être beaucoup de désinvolture tant il me paraissait évident que le processus aboutit à l'implosion de la chaîne de caractères, dans le cas d'un polygone aplati.

On peut reprendre la séquence inversée des exemples cités:
< DDDDDDDDDGGGGGGGGG > provient de

< DDDDDDDDDGGGBBBBBBBHHHHHHHGGGGGG >, qui lui-même provient de

< DDDDDDDDDGGGBBBBBBBHHDDDDGGGGHHHHHGGGGGG >

[Flodelarab]

Ahhh. Je comprends mieux. Vous snobez la définition initiale. Un polygone aplati est un polygone d'aire nulle. Et pour que l'aire soit nulle, on n'est obligé de repartir en arrière. Donc la regex suffit.

Bravo pour les dessins

[wiwaxia]

... Vous snobez la définition initiale ...

En fait, elle n'a pas été donnée et je ne voyais pas de quoi il s'agissait. Je l'ai découverte à la lecture de ton message #6.

... Un polygone aplati est un polygone d'aire nulle ...

Non, la définition est plus restrictive: l'aire de la surface couverte par le polygone est nulle - disons plus clairement qu'aucun point du plan n'est enlacé par une partie du contour polygonal.
Je n'ai rien trouvé sur la Toile.

Le dernier exemple que tu as cité (dddbgbgbgbdddhghghgh) n'est pas un polygone aplati, bien que son aire algébrique soit nulle: il y a deux boucles semblables, mais parcourues en sens opposés.

[anapurna]

salut

je reprend ta definition que j'avais pas vu avant

... Soit un polygone non aplati dont les coordonnées de ses sommées sont toutes entières et toutes ses arêtes sont horizontales ou verticales.
Le polygone sur plan est défini par un point initial et une trajectoire (chaîne de caractères) constituée d’une suite des quatre caractères suivants : − g : avancer d’une unité à gauche − d : avancer d’une unité à droite − h : avancer d’une unité vers le haut − b : avancer d’une unité vers le bas .
1. Ecrire une fonction estApplati qui détermine si un polygone est non aplati.
Un polygone est non aplati, s’il n’existe pas parmi ses arêtes deux qui sont identiques.

ce qui a mon sens pourrait se traduit par
NA = Not(EXIST(POLYGONE, 'dg' or 'gd' or 'bh' or 'hb')) and ((Nb(POLYGONE,g)=Nb(POLYGONE,d)) and (Nb(POLYGONE,b)=Nb(POLYGONE,h)))
and (AirePoly(POLYGONE) <> null )

avec AirePoly = i+ (b/2) -1 (théorème de pick)


j'ai oublié quelque chose dans la définition ?

[wiwaxia]

... j'ai oublié quelque chose dans la définition ?

Non, mais nous sommes en présence d'une définition ambiguë:

... Un polygone est non aplati, s’il n’existe pas parmi ses arêtes deux qui sont identiques.

Cela signifie-t-il deux arêtes de même longueur, parallèles et de sens opposés ou plus strictement deux arêtes confondues ?
La particularité des polygones étudiés est de présenter des sommets séparés de leurs voisins immédiats par une distance égale à l'unité, et pour beaucoup d'entre eux des angles plats (180°), lorsqu'ils ne sont pas égaux à ±90° ou ±360°.

Exemple: le triangle (ABC) vérifiant AC = AB + BC est manifestement aplati, et rien ne lui interdit de vérifier

AB = 2 ≠ BC = 3 .

Il pourra être décrit par la séquence: DDDDDGGGGG
correspondant aux parcours successifs: <AC>, <CB> et <BA> ,
et dont la simplification conduit encore à la chaîne vide.

Il n'est pas possible de pénétrer à l'intérieur d'un polygone aplati, parce qu'on ne franchit jamais une seule arête, mais deux (ou plus généralement un nombre pair).

[MOH BEN]

Bonjour tout le monde , j'espere que vous aller bien . Voici l'exo complet concernant la polygone aplati . J'ai répondu aux questions en algorithmique mais pas au Matlab car je l'ai trouver un peu difficile . Vous pouvez me le corriger et donner vos remarques svp .
Voici l'enonce complet : il est en pdf
et voici aussi ma solution elle est en pdf aussi ET MERCI BEAUCOUP.

[MOH BEN]

Bonjour ; dans ma solution j'ai converti les images au pdf a l'inverse c-a-d la dernière page est la premiere page . Et merci beaucoup .