Test de convexité sur un polygone simple.

[invitea41aab6c]

Bonsoir,

J'essaye de développer un truc pour m'amuser, mais je suis depuis hier face à un problème qui, pour mon plus grand désarroi, me bloque complètement.

J'ai une fonction qui me génère des polygones aléatoires. J'ai besoin, pour continuer mon truc, de déterminer les angles concaves et convexes.

Pour ce faire, mon idée est de tester si mon segment C est assez long pour couper le segment qui relie les sommets de A et B



J'imagine qu'il est possible, en renseignant l'angle séparant A et C, d'obtenir le point correspondant, sur le segment orange.. Et donc son éloignement du centre..

Je crois que je m'exprime très mal. J'en suis navré

J'ai passé beaucoup de temps à faire des séries de tests.. Mais en essayant de dessiner le segment orange (pour voir la validité du calcul..) , avec une boucle couvrant les angles séparants A et B, j'obtiens toute sortes de courbes. Jamais ma ligne droite.

Je suis assez désespéré par mon incompétence. Je suis sûr que la solution est simple... Mais impossible pour moi et mes connaissances vaseuses des mathématiques

Je vous remercie d'avance pour l'aide que vous pourriez m'apporter. Ce serait beaucoup pour moi.
-----

[danyvio]

Il faut reconnaître que c'est clair comme du jus de boudin.
Précise donc de qui est fixe et ce qui est variable sur ta figure. Qu'est-ce que cette courbe ? Je te titille mais c'est pour ton bien

[invitea41aab6c]

Je crois avoir une solution.

Comme on peut facilement avoir la largeur d'une section de cercle
corde = 2*rayon*SIN( angle_centre/2 )
largeur = corde/2*TAN(angle_centre/4)

largeur me donne le plus "grand rayon coupé par la corde". Ce rayon forme un angle droit avec la corde.. Du coups, les autres valeurs dont j'ai besoin sont l’hypoténuse de cet angle droit... Du côté "gauche" et "droit"...

)

Désolé pour mon vocabulaire non-conforme

[RuBisCO]

Bonjour,
Je résume ta situation : prenons par exemple un polygone ABCD.
Soit M le point d'intersection de (AC) et de (BD).
Le test est : si BM<BD, alors l'angle est concave et si BM>BD, l'angle est convexe (j'espère que je me suis pas trompé)

Ta méthode serait donc :
- les équations de (AC) et (BD)
- calculer les coordonnées de M
- calculer les longueurs BM et BD
- comparer ces longueurs
Est-ce que c'est ça ?

[A voir en vidéo sur Futura]

[invitea41aab6c]

Il faut reconnaître que c'est clair comme du jus de boudin.
Précise donc de qui est fixe et ce qui est variable sur ta figure. Qu'est-ce que cette courbe ? Je te titille mais c'est pour ton bien

Bonjour,

Merci de tenter de déchiffrer mon charabia, et de me titiller ( je ne le prends pas mal )


Je crois bien pouvoir dire qu'absolument tout est variable sur cette figure..
La courbe représente un arc imaginaire formé par les segments A et B. Sur le schéma A et B forment un angle droit, mais c'est tout à fait arbitraire. Cet angle aurait put être différent.

Je vais tester mon hypothétique solution, puis je posterai éventuellement un schéma plus clair. En essayant de coller aux formalismes de la géométrie

Merci

[invitea41aab6c]

Ma supposée illumination précédente était fumeuse. Par ce que j'ai deux inconnues..

Bonjour,
Je résume ta situation : prenons par exemple un polygone ABCD.
Soit M le point d'intersection de (AC) et de (BD).
Le test est : si BM<BD, alors l'angle est concave et si BM>BD, l'angle est convexe (j'espère que je me suis pas trompé)

Ta méthode serait donc :
- les équations de (AC) et (BD)
- calculer les coordonnées de M
- calculer les longueurs BM et BD
- comparer ces longueurs
Est-ce que c'est ça ?

Bonjour,

Tout à fait ! Sauf que les choses ne se présentent pas vraiment tout à fait comme sur le schéma.

Les points que je test font partie d'une figure plus grande. Pour chaque sommet de la figure, je prends ses deux points adjacents afin de réaliser le test. L'idée et de savoir si cet angle courant est concave ou convexe.

Je ne sais pas si je me fais comprendre, j'en suis désolé. J'y arrive pourtant très bien de visu, en dessinant le schéma pas à pas..

Bref. Le principe me semble bien là.

J'arrive à connaitre les coordonées de M uniquement si il est au milieu du segment AC.. Ce qui ne m'avance pas beaucoup.


Si vous avez des pistes, je vous serai vraiment reconnaissant

En vous remerciant

[RuBisCO]

Pourquoi pas avec le barycentre ?

[invitea41aab6c]

Pourquoi pas avec le barycentre ?

Pourquoi pas, en effet ... Je ne connais absolument pas cette notion.

Au vu de mes premières recherches ( google ), il va me falloir pas mal de concentration..

Je m'en vais donc essayer de comprendre l'utilité d'un tel point, dans une telle situation. =p

[invitea41aab6c]

Je m'en vais donc essayer de comprendre l'utilité d'un tel point, dans une telle situation. =p

Je ne parviens pas à éditer mon message précédent, j'ignore où se trouve le lien vers l'édition.

Néamoins, cette histoire de point G à l'air d'être exactement ce que je cherchais.

Merci beaucoup ( c'est bien peu de le dire, mais d'ici je ne peux pas faire mieux )

[danyvio]

Attention : Le centre de gravité d'un polygone convexe peut parfaitement se situer sur le polygone lui-même.

[RuBisCO]

Je pensais utiliser une autre propriété : soit un triangle ABC et M un point du plan. Si avec a,b et c des coefficient de même signe, alors M est à l'intérieur de ABC.
Si on choisit de prendre a=1 et b=1, on a qu'a résoudre une équation a une inconnue : si c est positif, c'est gagné !

Sinon j'y pense : pourquoi on calcule pas l'angle directement ? :S/

[ansset]

Sinon j'y pense : pourquoi on calcule pas l'angle directement ? :S/

bonjour, s'il s'agit de montrer la convexité, le centre de gravité ne donnera rien.
pour qu'il soit convexe, il faut qu'il ne soit ni concave , ni croisé.
ni concave :
soit An la suite des sommets dans l'ordre.
si tous les AnA(n+1)^A(n+1)A(n+2) ( produit vectoriel ) sont de même signe ou nuls alors il n'est pas concave.
reste à montrer qu'l n'est pas "croisé".

[danyvio]

Attention : Le centre de gravité d'un polygone convexe peut parfaitement se situer sur le polygone lui-même.

Pardon de me citer mais je voulais dire :
Le centre de gravité d'un polygone NON convexe peut parfaitement se situer sur le polygone lui-même

[invitea41aab6c]

Bonjour à vous,

ansset :

Par chance, je n'ai pas ce genre de questions à me poser.
Les polygones que je tests sont générés par une fonction qui m'épargne des cas de figure compliqués.

J'ai un peu honte de le dire, mais j'ai enfin appris à me servir des vecteurs grâce à ce topic... ( Et je m'en veux d'avoir dédaigné les cours de ce brave M.Gibia, en 4ème )

Voici la solution pour laquelle j'ai opté ( bien que j'ai encore qq problèmes.. ) :

Chacun des sommets du polygone est stocké dans un tableau..
Ces coordonées sont relatives à un point, centre d'un anneau, où les sommets ont étés placés aléatoirement.

Pour chaque sommet j'ai :
Angle ( par rapport au plan orthogonal que forme l'écran.. )
Rayon ( éloignement du "centre" donc)
ainsi que
X,Y ( par rapport au "centre" )


Pour chaque sommet, je prends les valeurs des sommets adjacents. ( je les appelles A et C.. faute de mieux )

Avec
Degres = Valeur absolue de ( Sommet(A)\Angle-Sommet(C)\Angle ) et
Width = Sommet(A)\x - Sommet(B)\x

J'obtiens une fraction Fw = width / Degres

Cette fraction est utile pour obtenir (en plus du coefficiant directeur et des coordonées d'origine de AC ) le point que je cherche à tester, sur le segment AB... en fonction de l'angle sommet(A)\Angle-Sommet(C)\Angle..

J'ignore si je suis clair. Je regrette d'avoir été un cancre. ( en maths )

Je tâtonne (méthode shadock) pour corriger des problèmes assez stranges... Mais dans l'ensemble, j'ai bon espoir.

Ci dessous : tests de la fonction utilisée uniquement sur un angle..

La ligne bordeaux est tracée par une boucle, couvrant tout les angles entre A et C. Le principal est que je soit capable de la dessiner..

Étrangement, quand je calcule la distance du point par rapport au centre ( Rayon = )
Et que je redessine ce point en partant du centre ( X = Rayon * Sin(Angle) et Y = Rayon * Cos(Angle) *-1 )
J'obtiens une "onde", dont l'amplitude augmente plus l'angle ABC augmente...



Et quand je pars d'un Sommet(A)\Angle > 0, n'en parlons pas.. Enfin ça, c'est une piètre boulette.

Enfin bref, je m'amuse bien. Merci beaucoup

[RuBisCO]

Sinon, on peut passer par les complexes :
Soit trois points A, B et C définissant un angle du polygone, l'angle orienté .
On définit les affixes des points :

Soit le nombre complexe , la valeur de l'angle est définie par .
Sinon, on peut observer uniquement le sinus :

Si , l'angle est inférieur à 180°
si , l'angle est plat
si , l'angle est supérieur à 180°.

[ansset]

visblement tu n'aime pas ma solution avec les produits vectoriels.
solution qui consiste uniquement à en calculer les signes ( à condition d'avoir mis les sommets successifs dans l'ordre )

[RuBisCO]

Faudrait peut-être que tu expliques mieux ta démarche.
En fait, je sais si notre ami sait ce qu'est le produit vectoriel

[ansset]

bonjour,
un polygone convexe "tourne" tj dans le même sens ( à gauche ou à droite ) en prenant les sommets dans l'ordre.
le signe du produit vectoriel donne le sens de rotation:
si ABC sont trois sommets successifs et
AB ( a1,b1) et BC ( a2,b2) alors
AB^BC = a1b2-b1a2

j'exclus l cas des polygones croisés ( plus complexes )
par exemple une étoile tourne tj dans l même sens mais le segments se croisent partout.

ps: j'ignore le programme actuel du lycée....

[invitea41aab6c]

visblement tu n'aime pas ma solution avec les produits vectoriels.
solution qui consiste uniquement à en calculer les signes ( à condition d'avoir mis les sommets successifs dans l'ordre )

Oh, pardon, j'ai zappé cette proposition

Mh, les sommets sont testés dans l'ordre des aiguilles d'une montre. C'est tout ce que je peux dire :s
J'ignore en effet ce qu'est un produit vectoriel, mais je vais essayer de m'y intéresser.


Concernant l'utilisation des complexes, il va également falloir que je prenne un peu de temps pour comprendre. Aujourd'hui je suis relativement tranquille, je vais m'y mettre


Bonne journée

[RuBisCO]

Le produit scalaire est vu au lycée, mais pas le produit vectoriel (et c'est dommage).
Dans les bouquins de terminale, on voit les complexes et leurs applications géométriques.

[RuBisCO]

Sinon, si tu as vraiment du temps, il y a une petite vidéo qui est bien pratique pour débuter : le film "Dimensions", regarde la vidéo 5.

[invitea41aab6c]

Sinon, si tu as vraiment du temps, il y a une petite vidéo qui est bien pratique pour débuter : le film "Dimensions", regarde la vidéo 5.

Bonjour, j'ai pratiquement tout regardé C'est assez trippant.
Je vais me faire la suite cet aprèm'

Autrement, j'ai fini par résoudre ce problème il y a quelques jours, et je suis maintenant assez atterré de ne pas y être parvenu plus tôt !



Or donc. Comme j'ai besoin de la valeur de l'angle pour effectuer d'autres tests, je n'ai pas utilisé la solution d'ansset.

Si j'ai mis un peu de temps à trouver comment on obtiens "l'argument d'un vecteur", j'ai fini par tomber sur un site expliquant le "procédé".

Un de mes problèmes ( et je pense que c'est ce qui m'a bloqué, avant de venir ici, quand j'obtenais "avec Al-Kashi" uniquement des angles entre 0 et 180 degrés ), c'est l'histoire des quadrants...

il faut dire que l’explication ne fut pas facile à dénicher.. Et franchement, je ne crois pas que l'on m'ai véritablement expliqué un jour la nature de sinus et cosinus... Et leur "relation" avec l'ordonnée et l'abscisse.. En tout cas pas au collège.

Maintenant, j'espère avoir les idées plus claires.

Merci.

[RuBisCO]

Bon film alors : tu vas voir des ensembles de Julia, des fibrillations de Hopf et pleins d'autres choses.