algo de convexité

**nkd** · 12/01/2005, 17h03

Bonjour les amis

je crée des polygones et je voudrais mettre en place un algo qui permettrait de savoir si ce dernier est convexe.

Comment pourrai-je m'y prendre ?
merci

**Steki-kun** · 12/01/2005, 18h29

un peu bourrinement, tu peux calculer l'enveloppe convexe des points en question (algorithme de Graham en n.logn par exemple), et ensuite qu'il s'agit bien du polygone considéré. Sinon, c'est que celui-ci ne peut être convexe.

attention aux angles plats dans ton polygone, fais en sorte que ton algorithme d'enveloppe convexe ne 'saute' pas le point du milieu si 3 pts sont alignés, sinon tu pourras pas le comparer directement avec ton polygone.

**PINGOUIN_GEANT** · 12/01/2005, 18h35

perso, je testerais les angles pour chaque sommet, dès qu'un est rentrant il n'y a plus de convexité.
avec les produits scalaires et vectoriels cela devrait aller.

**Steki-kun** · 12/01/2005, 18h55

Envoyé par PINGOUIN_GEANT

perso, je testerais les angles pour chaque sommet, dès qu'un est rentrant il n'y a plus de convexité.
avec les produits scalaires et vectoriels cela devrait aller.

sauf s'ils sont tous rentrants

sinon en effet, en tournant le long du polygone, n produits vectoriels de segments consécutifs et les composantes z doivent toutes avoir le même signe.

**PINGOUIN_GEANT** · 12/01/2005, 20h01

Envoyé par Steki-kun

sauf s'ils sont tous rentrants

Donne-moi un angle rentrant sur un polygone et je te trace un segment avec des points à l'extérieur du polygone.

Rq: on peut espérer que le domaine à l'intérieur polygone vérifie la propriété mathématique suivante :
il se situe localement d'un seul côté de sa frontière.

**Steki-kun** · 12/01/2005, 21h13

c juste pour faire remarquer que fondamentalement, tu ne sais pas à priori dans quel sens va tourner ton polygone, donc angle rentrant (= angle entre 180 et 360 degrés par définition mathématique, qu'on sache de quoi on parle au moins) n'implique pas que le polygone n'est pas convexe. Le problème est de trouver, dans un même parcours, au moins un angle <= Pi et un angle plus grand. Ca c'est une CNS de convexité.

**PINGOUIN_GEANT** · 12/01/2005, 21h23

Envoyé par Steki-kun

c juste pour faire remarquer que fondamentalement, tu ne sais pas à priori dans quel sens va tourner ton polygone,

justement si, pour moi cela n'a pas de sens de définir un polygone et de ne pas savoir où est l'intérieur du polygone, comme ton contour sépare l'espace en 2 parties distinctes.
Après il faut voir l'implémentation de nkd.

**Steki-kun** · 12/01/2005, 21h30

manque de pot, il se bien que le polygone, ce soit un tableau (voire une liste) de deux coordonnées à chaque fois, le plan se retrouvant alors orienté par l'ordre de tracé (supposons que c'est un tracé de polygone à la souris dans un paint sommaire par exemple), ce qui peut donner le polygone concave au lieu du convexe

dans le doute j'ai préféré préciser, ça ne coûte rien

**nkd** · 13/01/2005, 07h47

merci les amis pour vos contributions

en effet c'est un polygone tracé depuis la souris dont les sommets sont connus en xy et stockés dans un tableau. il y a bien un sens que je me donne pour le créer.
vu vos post je crois que j'ai une idée, celle de tester si tous les angles intérieurs ne sont pas rentrant et qu'ils sont tous <=180 °

je fait le test et je vous fait signe tout de suite
merci et A+

**sovitec** · 13/01/2005, 09h53

Envoyé par nkd

en effet c'est un polygone tracé depuis la souris dont les sommets sont connus en xy et stockés dans un tableau. il y a bien un sens que je me donne pour le créer.
vu vos post je crois que j'ai une idée, celle de tester si tous les angles intérieurs ne sont pas rentrant et qu'ils sont tous <=180 °

Même sans connaitre le sens de rotation de ton polygone il suffit de vérifier que tous les produits vectoriels Pi-1Pi^PiPi+1 ont même signe (c'est un produit vectoriel de 2 vecteurs, je ne sais pas comment écrire la formule autrement). Ce qui reviens à tester que dans un sens de parcours tous les angles sont soit obtus, soit concaves.

**Nemerle** · 13/01/2005, 10h23

Bein non.... prend un losange aplati... il n'y a que 2 angles obtus...

**sovitec** · 13/01/2005, 10h47

Envoyé par Nemerle

Bein non.... prend un losange aplati... il n'y a que 2 angles obtus...

Arg, grosse bétise de vocabulaire de ma part, je voulais parler de >=180°, ou <= à 180°. Mais le principe énoncé reste valable.

**Trap D** · 13/01/2005, 11h18

Envoyé par Nemerle

Bein non.... prend un losange aplati... il n'y a que 2 angles obtus...

pourquoi "aplati"

:

**Steki-kun** · 13/01/2005, 11h19

Envoyé par sovitec

Même sans connaitre le sens de rotation de ton polygone il suffit de vérifier que tous les produits vectoriels Pi-1Pi^PiPi+1 ont même signe (c'est un produit vectoriel de 2 vecteurs, je ne sais pas comment écrire la formule autrement). Ce qui reviens à tester que dans un sens de parcours tous les angles sont soit obtus, soit concaves.

c'est quand même exactement ce que j'ai écrit au-dessus (en remplacant obtus par rentrant), donc on chippote, on chippote, mais on en revient au même point =)

**sovitec** · 13/01/2005, 11h30

Envoyé par Steki-kun

Envoyé par sovitec

Même sans connaitre le sens de rotation de ton polygone il suffit de vérifier que tous les produits vectoriels Pi-1Pi^PiPi+1 ont même signe (c'est un produit vectoriel de 2 vecteurs, je ne sais pas comment écrire la formule autrement). Ce qui reviens à tester que dans un sens de parcours tous les angles sont soit obtus, soit concaves.

c'est quand même exactement ce que j'ai écrit au-dessus (en remplacant obtus par rentrant), donc on chippote, on chippote, mais on en revient au même point =)

J'avais lu ta contribution un peu trop en diagonale, tu as parfaitement raison. En fait je répondais surtout au dernier post de nkd.